广度首先使用队列搜索OCaml中的二叉树

Question

我想使用队列在OCaml中创建一个广度优先的二叉树搜索，但我无法让它工作。

当节点没有任何“邻居”时，似乎函数卡住了。

let rec enque v l = 
    match l with
        [] -> [v]
    |   h::t -> h::(enque v t)



let rec qhd l =
    match l with
        h::[] -> h
    |   h::t -> qhd t



let deque l =
    match l with
        [] -> []
    |   h::t -> t



let notempty l = (l != [])


let rec breadthFirstHelp l =
    if notempty l
    then
        let cur = qhd l in
            match cur with
                Empty -> []
           |   (Node(Empty, node, Empty)) -> node::(breadthFirstHelp (deque l))
           |   (Node(left, node, right)) ->
               let l = enque right l in
               let l = enque left l in 
                   node::(breadthFirstHelp (deque l))
    else []

这是我正在测试的树。

[tree =
  Node
   (Node
     (Node (Empty, "A", Empty), "B",
      Node (Node (Empty, "C", Empty), "D", Empty)),
    "E", Node (Empty, "F", Node (Empty, "G", Node (Empty, "O", Empty))))]

用我的代码：[“E”; “B”; “一个”; “一个”; “一个”]

预期结果：[“E”; “B”; “F”; “一个”; “d”; “G”; “C”; “O”]

Answer 1

您的代码中存在三个问题：

首先，你的qhd函数与你的deque和enque函数不兼容。实际上，对于非空队列q和值any，可以预期在队列末尾添加元素不会更改顶部的元素：

 qhd q = qhd (enque any q)

而你的队列q的实现，使deque q不是空的，你有

 qhd q = qhd (deque q)

其次，在你的breadthFirstHelp函数中，即使[]中有待处理的子树，空案例也总是返回l。

修复这两个问题应该会给你正确的结果，但是最后一个性能问题是：enque函数非常广泛，因为它需要遍历整个队列。

一个简单的解决方案是将列表分成两部分

  type 'a queue = { top: 'a list; bottom: 'a list }

当底部列表以相反的顺序保持时。因此，附加到队列是附加在底部列表顶部的问题。而弹出队列只需要获取top列表的第一个元素（如果它不为空），或者从底部列表中重新填充它。