我正在使用ocaml。我有类型：
type 'a bt = Empty | Node of 'a * 'a bt * 'a bt;;
我也有示例BST：
let tree = Node(1,Node(2,Node(4,Empty,Empty),Empty),Node(3,Node(5,Empty,Node(6,Empty,Empty)),Empty));
我需要编写功能：breadthBT : 'a bt -> 'a list，它将是广度优先的搜索遍历。对于上面的示例树，它应返回[1; 2; 3; 4; 5; 6]
如何编写该功能？我只能编写使用 dst 的以下函数：
let rec breadthBT tree =
if tree=Empty then []
else let Node(w,l,r)=tree in (w::breadthBT l)@breadthBT r;;
上面的函数返回（例如树）[1;2;4;3;5;6]。但是我无法编写使用 bfs 的功能。你能帮我吗？
它不是可编译的解决方案。只是一个小费。您应该从顶层根节点到深级节点迭代。让我们的函数接收累加器的答案和节点列表（您的'a bt值）作为第二个参数。您可以通过获得三重元素来映射此列表，并收到答案的下一个部分。另外，您需要评估下一个树的水平。对于每个节点，最多都有两个后代。您可以映射列表并应用_a_function_以接收后代列表。这将是您树的下一个层次。而不是---递归。
A不会指定此_a_function_。尝试研究Google中的内容。
快乐黑客！
想象一下您将鼻子伸到树上。是否可以以广度优先的方式穿越树，而不会在记事本中添加书签位置？不，因为订单可以使您从一个分支跳到另一个无关的分支。因此，您需要一个带有"剩余职位访问"的记事本。您从记事本挑选出剩余的位置，然后盲目跳到它。由于您从记事本删除了访问的位置，因此您处于尚未访问的节点。而且，由于如果没有访问中间节点，您就无法抬起树，因此您现在没有访问过上方的两个节点。但是，您可以抵制直接爬树枝的本能 - 哎呀，这是宽度的第一阶。您不想忘记这两个未访问的节点，因此您想将它们放入笔记本中。您将它们放在笔记本面前或背面的前面？当然，否则您会立即选择其中一个，这就是我们要避免的。et voila：您的记事本是节点的fifo队列，您将其保留为累加器（即通过），但也可以选择访问子树。