二叉树的 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在节点上并在两个子树上递归。