樹叢探索與遞迴

假設我們有以下樹：

root
- A
  - AA
  - AB
- B
  - BA
  - BB
    - BBA

現在，如果我們希望列出元素的所有名稱，我們可以通過簡單的 for 迴圈來完成。我們假設有一個函式 get_name() 返回節點名稱的字串，函式 get_children() 返回樹中給定節點的所有子節點的列表，函式 get_root() 返回根節點。

root = get_root(tree)
for node in get_children(root):
    print(get_name(node))
    for child in get_children(node):
        print(get_name(child))
        for grand_child in get_children(child):
            print(get_name(grand_child))
# prints: A, AA, AB, B, BA, BB, BBA

這種方法執行良好而且速度很快，但如果子節點有自己的子節點呢？那些子節點可能有更多的子節點……如果你事先不知道會有多少個子節點怎麼辦？解決此問題的方法是使用遞迴。

def list_tree_names(node):
    for child in get_children(node):
        print(get_name(child))
        list_tree_names(node=child)

list_tree_names(node=get_root(tree))
# prints: A, AA, AB, B, BA, BB, BBA

也許你希望不列印，但返回所有節點名稱的平面列表。這可以通過將滾動列表作為引數傳遞來完成。

def list_tree_names(node, lst=[]):
    for child in get_children(node):
        lst.append(get_name(child))
        list_tree_names(node=child, lst=lst)
    return lst

list_tree_names(node=get_root(tree))
# returns ['A', 'AA', 'AB', 'B', 'BA', 'BB', 'BBA']