在Erlang中，如何编写BFS Tree Search来查找特定节点

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）。