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