我正在使用 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中研究什么是concatMap。
快乐黑客！
想象一下，你把鼻子贴在树上。是否可以以广度优先的方式遍历树而不在记事本中添加书签位置？不，因为订单可以让你从一个分支跳到另一个不相关的分支。因此，您需要一个带有“要访问的剩余位置”的记事本。您从记事本中选择下一个剩余位置并盲目地跳到它。由于您从记事本中删除了访问过的位置，因此您处于尚未访问过的节点。并且由于您不访问中间节点就无法爬上树，因此您还没有访问您上方的两个节点。但是你抵制了直接爬树枝的本能——哎呀，这就是广度第一个订单。您不想忘记这两个未访问的节点，因此您想将它们放入笔记本中。你把它们放在哪里，笔记本前面还是后面？当然，在背面，否则您会立即选择其中一个，这就是我们想要避免的。瞧：您的记事本是一个 FIFO 节点队列，您将其作为累加器保留（即传递），但也消耗以选择要访问的子树。