# 共递归

## 注释

1. ^ Not validating input data.
2. ^ More elegantly, one can start by placing the root node itself in the structure and then iterating.
3. ^ Post-order is to make "leaf node is base case" explicit for exposition, but the same analysis works for pre-order or in-order.
4. ^ Breadth-first traversal, unlike depth-first, is unambiguous, and visits a node value before processing children.
5. ^ Technically, one may define a breadth-first traversal on an ordered, disconnected set of trees – first the root node of each tree, then the children of each tree in turn, then the grandchildren in turn, etc.
6. ^ Assume fixed branching factor (e.g., binary), or at least bounded, and balanced (infinite in every direction).
7. ^ First defining a tree class, say via:
class Tree:
def __init__(self, value, left=None, right=None):
self.value = value
self.left  = left
self.right = right

def __str__(self):
return str(self.value)


and initializing a tree, say via:

t = Tree(1, Tree(2, Tree(4), Tree(5)), Tree(3, Tree(6), Tree(7)))


In this example nodes are labeled in breadth-first order:

    1
2     3
4 5   6 7

8. ^ Intuitively, the function iterates over subtrees (possibly empty), then once these are finished, all that is left is the node itself, whose value is then returned; this corresponds to treating a leaf node as basic.
9. ^ Here the argument (and loop variable) is considered as a whole, possible infinite tree, represented by (identified with) its root node (tree = root node), rather than as a potential leaf node, hence the choice of variable name.

## 参考文献

1. ^ Barwise and Moss 1996.
2. ^ Moss and Danner 1997.
3. ^ Smyth and Plotkin 1982.
4. ^ Gibbons and Hutton 2005.
5. ^ Doets and van Eijck 2004.
6. ^ Leclerc and Paulin-Mohring, 1994
7. ^ Hettinger 2009.
8. ^ Allison 1989; Smith 2009.
9. ^ Jones and Gibbons 1992.