将BST模块映射到列表

Question

我正在尝试使用Map.Make函数将BST实现映射到列表。我设法创建了映射，但我不知道如何将通用树添加到具有映射的模块中。在下面的代码中，我将空树(Leaf(映射到空列表[]。我想将任何类型为Node of int * tree * tree的树映射到包含节点[v1;...;vn]中的值的列表。最后一行有一个例子，我想对一个节点值为2的树做些什么。

let m = 
let open TreeMap in
empty
|> add Leaf [] 
|> add (Node (2, Leaf, Leaf)) [2]

谢谢，Federico

Answer 1

映射是一个有限的数据结构，有无限多的树。不能将所有成对的树和列表存储到地图中。

您可以使用递归函数将树折叠到列表中。

Answer 2

如果您被要求"地图"；从BST到列表，我真的不确定你是否打算使用映射数据结构，而不仅仅是用函数映射这两者。

类似以下内容。

# type 'a tree = Leaf of 'a | Node of 'a * 'a tree * 'a tree;;
type 'a tree = Leaf of 'a | Node of 'a * 'a tree * 'a tree
# let rec tree_to_list = function
| Leaf v -> [v]
| Node (v, l, r) -> tree_to_list l @ [v] @ tree_to_list r;;
val tree_to_list : 'a tree -> 'a list = <fun>
# tree_to_list (Node (4, Leaf 3, Node (6, Leaf 5, Leaf 7)));;
- : int list = [3; 4; 5; 6; 7]