时间戳

首页 > 解决方案 > 二叉树的 Erlang 通用 foldl/3 等效项

erlang - 二叉树的 Erlang 通用 foldl/3 等效项

问题描述

我需要为二叉树编写相当于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)andFun([], 2)和 ，当试图对值求和时，它会尝试执行 [] + 2，这是一个无效的表达式。它也将打破更复杂的情况。

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

标签： erlangbinary-tree

解决方案

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

不需要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在节点上运行并在两个子树上递归。

推荐阅读