二叉树的广度优先搜索

Question

我是一个OCaml用户，我有一个类型：

type 'a bt = Empty | Node of 'a * 'a bt * 'a bt;;

此外，我有一个二叉搜索树的示例：

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的函数。你能帮我吗？

- Paul

---

我同意最后一个OCaml问题的评论：“我认为作业的通常规则是你应该展示一些你尝试过的代码。如果没有东西可以评论，那么仅仅解决问题是很难帮助到你的。” - jrouquie

Answer 1

这不是一个可编译的解决方案，只是一条提示。你应该从顶层根节点到深层节点进行迭代。让我们的函数接收答案的累加器和节点列表（您的'a bt values'）作为第二个参数。您可以通过获取三元组的第一个元素来映射此列表，然后您将获得下一个答案部分。此外，您需要评估树的下一级。对于每个节点，最多有两个后代。您可以映射您的列表并应用_a_function_以获取后代列表。这将是您的树的下一级，然后进行递归。

A不会指定此_a_function_。请尝试在Google中学习concatMap是什么。

快乐编程！

- Kakadu

Answer 2

想象一下，你把鼻子贴在树上。如果不在记事本中标记位置，是否可能以广度优先的方式遍历整棵树？不可能，因为顺序可能会使你跳到另一个无关的分支。所以你需要一个带有“待访问位置”的记事本。你从记事本中选择下一个待访问位置并盲目地跳转到它。由于你从记事本中删除了已访问的位置，所以你现在处于一个未访问过的节点。由于你不能在访问中间节点之前就爬上树，所以你还没有访问到你现在所在的两个节点。但是你抵制了直接爬上分支的冲动——该死，这是广度优先顺序。你不想忘记这两个未访问的节点，所以你想把它们放进笔记本里。你把它们放在笔记本的前面还是后面？当然是放在后面，否则你会立即选择其中一个，而这正是我们要避免的。Et voila：你的记事本是一个FIFO节点队列，你将其保留（即传递）作为累加器，但也消耗它来选择要访问的子树。

- lukstafi