erlang - 在 Erlang 中，如何编写 BFS 树搜索来查找特定节点

Question

我想编写一个函数来在 BFS 树搜索中查找特定节点。

如何在 Erlang 中实现？

Answer 1

假设一个简单的结构:

node() :: {Key :: term(), Left :: node(), Right :: node()} | undefined.

此函数将对树执行广度优先搜索并返回找到的第一个元素的深度(如果未找到节点，则返回 false):

find(_Key, undefined) -> false;
find(Key,  Tree)      -> find(Key, [Tree], [], 0).

find(_Key, [], [], _Depth) -> % No more children
    false;
find(Key, [], Children, Depth) -> % Next level, increase depth
    find(Key, Children, [], Depth + 1);
find(Key, [{Key, _, _}|_Rest], _Children, Depth) -> % Found it!
    Depth;
find(Key, [{_, Left, Right}|Rest], Children, Depth) -> % Add children to search
    find(Key, Rest, add(Right, add(Left, Children)), Depth).

add(undefined, List) -> List;
add(E,         List) -> [E|List].

(空树只是undefined)。