二叉树广度优先搜索

我正在使用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的功能。你可以帮帮我吗？

来源

2012-10-19 Paul

我同意上一次ocaml问题的评论：“我认为通常的家庭作业规则是你应该显示一些你已经尝试过的代码，没有什么可以评论的，如果不解决问题就很难提供帮助“。 – jrouquie

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

A不会指定这个_a_function_。尝试研究谷歌中的concatMap。

快乐黑客！

来源

2012-10-19 22:27:08 Kakadu

谢谢，明天我会检查 – Paul

想象一下，你把你的鼻子插在树上。没有在记事本中添加书签位置，是否有可能以广度优先的方式遍历树？不，因为订单可以让你从一个分支跳到另一个不相关的分支。所以你需要一个记事本和“剩余位置访问”。你从记事本中选择下一个剩余的位置并盲目地跳到它。由于您从记事本中删除了访问位置，因此您尚未访问过的节点。既然你不能在没有访问中间节点的情况下起床树，你还没有访问你上面的两个节点。但你抵制本能直接攀登分支 - 哎，这是宽度第一顺序。你不想忘记这两个未访问的节点，所以你想把它们放到笔记本中。你把它们放在笔记本前面或背面？当然，否则你会立即选择其中一个，这就是我们想要避免的。 Et瞧：你的记事本是一个FIFO队列的节点，你保持（即通过）作为一个累加器，但也消耗挑选一个子树访问。

来源

2012-10-20 09:56:07 lukstafi

二叉树广度优先搜索

回答

相关问题