I need to write the equivalent of lists:foldl/3 for binary trees.
Every node is represented as:[Value, LeftNode, RightNode]
So a tree with a root 2 and leaves 1 and 3 would look like this: [2, [1, [], []], [3, [], []]]
Later I want to use that function to perform operations, such as summing up all positive values in that tree etc.
This is the function I wrote:
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.the problem is that it's not truly generic, and when we have, let's say a tree with only a root, e.g.: [2, [], []]
it calls both Fun(2, 0) and Fun([], 2) and when trying to sum up the values in the second case it tries to do [] + 2, which is an invalid expression. It also would break on more complicated cases.
I would greatly appreciate any help with fixing this function. Thank you.
1条答案
按热度按时间c2e8gylq1#
First of all, you should use tuples as nodes in this case instead of lists. Lists are linked lists between their elements while tuples use contiguous memory (you can access a single element of a tuple without processing the leading elements of structure).
There's no need for
Fun(L, X1):If the node is empty, do nothing, else run the
Funon the node and recurse on both subtrees.