遍历多路树

Question

我正在尝试遍历多路树，并像 List.map 那样映射它的值。

这是我的尝试

type 'a tree = Node of 'a * ('a tree list);;

let tree_map f t = 
  let rec aux acc tr =
    match tr with
    | Node(v, []) -> Node(f v, []) :: acc
    | Node(v, sub) -> let r = List.fold_left aux acc sub in Node(f v, r) :: acc
  in aux [] t
;;

let t = Node (1, [Node (2, [Node (1, [])]); 
                  Node (3, []);
                  Node (1, [Node (5, []); 
                            Node (2, [])])]);;
;;

let res = tree_map (succ) t;;

我尝试了 this 答案中的建议。无法成功实施。

我的函数returns这个明显不对

val res : int tree list =
  [Node (2,
    [Node (2,
      [Node (3, []); Node (6, []); Node (4, []); Node (3, [Node (2, [])])]);
     Node (4, []); Node (3, [Node (2, [])])])]

有什么问题吗？

Answer 1

我看到的一个问题是您只是按原样使用 List.fold_left 的结果。但是左边的折叠将 return 一个反向列表。

# List.fold_left (fun acc n -> (n + 1) :: acc) [] [1;2;3];;
- : int list = [4; 3; 2]

第二个问题是您在同一个表达式的两个地方使用了 acc：

let r = List.fold_left aux acc sub in Node(f v, r) :: acc

这将复制树的一部分。在我看来，其中一个地方应该使用 [] 而不是 acc。

Answer 2

您所指的答案是关于折叠迭代器的，即当您将某些函数应用于树的每个节点以构建一些值时。地图迭代器有点不同，更容易实现。对于每个节点，您应该 return 映射节点。

请务必记住，map 迭代器应保留数据的结构，例如，当您拥有叶节点时，您需要 return 映射的叶节点，例如,

| Node (v, []) -> Node (f v, [])

一般情况也是如此，即不使用折叠迭代器，而是需要使用map迭代器，例如

| Node(v, sub) -> Node (f v, List.map (aux f) sub)

事实上，您甚至不需要空节点情况，因为一般情况对所有节点都适用。这将使你 tree_map 成为一个微不足道的单行者:)

并且不要忘记从 aux 中删除 acc 参数，您不需要它。

Answer 3

聚会有点晚了，但由于我已经完成了工作并向您展示了可以简化多少功能：

let rec tree_map f (Node (v, sub)) =
  Node(f v, List.map (tree_map f) sub)

遍历多路树

Traverse a multiway tree

ocaml