Что не так с моим кодом обхода дерева? - PullRequest
Новая
       22

Что не так с моим кодом обхода дерева?

2 голосов
/ 26 февраля 2011

У меня есть простое дерево, определенное так: 

type BspTree =
    | Node of Rect * BspTree * BspTree
    | Null

Я могу получить коллекцию листовых узлов (комнат в моем дереве "подземелье"), вот так, и это похоже на работу: 

let isRoom = function
    | Node(_, Null, Null) -> true
    | _ -> false

let rec getRooms dungeon =
    if isRoom dungeon then
        seq { yield dungeon }
    else
        match dungeon with
        | Node(_, left, right) ->
            seq { for r in getRooms left -> r
                  for r in getRooms right -> r }
        | Null -> Seq.empty

Но теперь я пытаюсь получить комнаты с сестринскими узлами, чтобы я мог соединить их с коридорами, и я терплю неудачу (как это часто бывает). Вот моя попытка: 

let rec getCorridors dungeon =
    match dungeon with
    | Null -> failwith "Unexpected null room"
    | Node(_, left, right) ->
        match left, right with
        | Null, Null -> Seq.empty
        | Node(leftRect, _, _), Node(rightRect, _, _) ->
            if isRoom left && isRoom right
            then seq { yield makeCorridor leftRect rightRect }
            else seq { for l in getCorridors left -> l
                       for r in getCorridors right -> r }
        | _ -> failwith "Unexpected!"

Я просто получаю пустой seq. Во всяком случае, все это вредит моему мозгу, и я знаю, что вряд ли кто-нибудь пробьет это, но я подумал, что не мешало бы спросить.

1 Ответ

4 голосов
/ 26 февраля 2011

Как прокомментировал Роберт, возможно, вашей функции makeCorridor требуется некоторое внимание.Я адаптировал ваш код, создав собственную функцию makeCorridor и заменив Rect на int.

Я использовал активный шаблон, чтобы определить, когда BspTree является комнатой.Я также использовал yield! sequence вместо for x in sequence -> x.Эти модификации приводят к тому же поведению.Я просто хотел показать, на что способен активный шаблон: 

type BspTree =
    | Node of int * BspTree * BspTree
    | Null

let (|IsRoom|_|) dungeon = 
    match dungeon with
    | Node(_,Null,Null) -> Some dungeon
    | _ -> None

let rec getRooms = function
    | IsRoom dungeon -> Seq.singleton dungeon
    | Null -> Seq.empty
    | Node (_, left, right) -> seq { yield! getRooms left
                                     yield! getRooms right }

let makeCorridor leftNode rightNode =
    match leftNode, rightNode with
    | Node(left,Null,Null), Node(right,Null,Null) -> 
        sprintf "(%d) -> (%d)" left right
    | _ -> failwith "Illegal corridor!"

let rec getCorridors = function
    | Null -> failwith "Unexpected null room"
    | Node(_, Null, Null) -> Seq.empty
    | Node(_, IsRoom left, IsRoom right) -> seq { yield makeCorridor left right }
    | Node(_, left, right) -> seq { yield! getCorridors left
                                    yield! getCorridors right }

Пример: 

let dungeon = 
    Node(1, Node(2, Node(4,Null,Null), 
                    Node(5,Node(8,Null,Null),
                           Node(9,Null,Null))),
            Node(3, Node(6,Null,Null), 
                    Node(7,Null,Null)))

Результат в FSI: 

> getCorridors dungeon;;
val it : seq<string> = seq ["(8) -> (9)"; "(6) -> (7)"]
...