В Erlang, как написать BFS Tree Search, чтобы найти определенный узел

Question

Я хочу написать функцию для поиска определенного узла в BFS Tree Search.

Как это сделать в 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).