二叉树的 Erlang 泛型 foldl/3 等价物

Question

我需要为二叉树编写 lists:foldl/3 的等价物。

每个节点表示为：

[Value, LeftNode, RightNode]

因此，一棵树的根为 2，叶子为 1 和 3，如下所示： [2, [1, [], []], [3, [], []]]

以后我想用那个函数来进行操作，比如把那棵树中的所有正值求和等等

这是我写的函数：

tree_foldl(_, Acc, []) -> Acc;
tree_foldl(Fun, Acc, [V, L, R]) ->
X1 = tree_foldl(Fun, Fun(V, Acc), L),
X2 = tree_foldl(Fun, Fun(L, X1), R),
X2.

问题是它不是真正通用的，当我们有时，假设一棵只有根的树，例如： [2, [], []]

它同时调用 Fun(2, 0) 和 Fun([], 2)，当尝试对第二种情况下的值求和时，它会尝试执行 [] + 2，这是一个无效的表达式。它也会在更复杂的情况下中断。

对于修复此功能的任何帮助，我将不胜感激。谢谢。

Answer 1

首先，在这种情况下，您应该使用元组而不是列表作为节点。列表是其元素之间的链表，而元组使用连续内存（您可以访问元组的单个元素而无需处理结构的前导元素）。

不需要Fun(L, X1):

tree_foldl(_, Acc, []) -> Acc;
tree_foldl(Fun, Acc, [V, L, R]) ->
    Acc0 = Fun(V, Acc),
    Acc1 = tree_foldl(Fun, Acc0, L),
    Acc2 = tree_foldl(Fun, Acc1, R),
    Acc2.

如果节点为空，什么都不做，否则运行节点上的Fun并在两个子树上递归。

二叉树的 Erlang 泛型 foldl/3 等价物

Erlang generic foldl/3 equivalent for binary trees

erlang

binary-tree