Erlang 二叉树函数

Question

我有一个完美二叉树，每个节点都是这样表示的

[Value, LeftNode, RightNode]

Value是节点值和每个 LeftNode 和 RightNode 都是节点的儿子，它们递归地也是二叉树。最后一个节点（叶子）是这样表示的

[Value, [], []]

示例：

L1=[4, [], []], 
L2=[5, [], []], 
L3=[6, [], []], 
L4=[7, [], []], 
L5=[2, L1, L2], 
L6=[3, L3, L4], 
Tree=[1,L5 , L6].

所以我有returns最后一个左边的叶子

的功能

lastLeftLeaf([H, [], []]) ->H;
lastLeftLeaf([H, Left, Right]) ->lastLeftLeaf(Left).

在我们的例子中 returns 4 :L1 的值。并且 returns 树没有最后离开的功能 leaf:it 将此叶子替换为 []

withoutLastLeftLeaf([H, [], []]) ->[] ;
withoutLastLeftLeaf([H, Left, Right]) ->[H, withoutLastLeftLeaf(Left), Right].

在我们的示例中，它 returns 没有 L1 的树：替换为 []

这两个函数进行相同的浏览并获得结果我必须进行两次浏览，为了提高性能和效率我想创建一个只用一次浏览的函数 returns 两个结果：最后一个左边的叶子没有那片叶子的树有任何帮助，谢谢大家。

Answer 1

您可以组合您编写的两个函数，并使新函数 return 成为 {Value, NewTree} 形式的结果。对于你已经在叶子的情况，很简单：

take_last_left_leaf([H, [], []]) -> {H, []};

然后，在树中的任何其他点，您将递归到左分支，获取值和新的左分支，然后 return 值以及修改后的树：

take_last_left_leaf([H, Left, Right]) ->
    {Value, NewLeft} = take_last_left_leaf(Left),
    {Value, [H, NewLeft, Right]}.

Erlang Binary Tree function