树丛探索与递归

假设我们有以下树：

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']