ocaml - 二叉树广度优先搜索

Question

我正在使用 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]
那个函数怎么写？我只能编写以下使用 的函数夏令时 :

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 .你可以帮帮我吗？

Answer 1

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

A 不会指定这个 _a_function_ .尝试研究一下google中的concatMap是什么。

快乐黑客!