Python: 树递归问题

Question

我在处理树结构时遇到了一些问题。这个树结构很简单，只有一个节点和一系列子节点。

class Tree (object):
    __slots__ = "node","children"
    def __init__(self,node,children=[]):
        self.node = node
        self.children = children

通过一种线性化的方法，我们需要找出一个特定分支结束了多少个（子）树。比如，如果我们这样构建一个树：

t = Tree(1, [Tree(2, [Tree(5), Tree(3, [Tree(4)])])])

那么 t.linearize() 应该输出 1 2 5 NIL 3 4 NIL NIL NIL NIL。这里的每个 NIL 代表一个（子）树的结束。

但我现在的版本只输出了 1 2 5 NIL 3 4 NIL，没有多个 NIL。你们觉得我漏掉了什么吗？

def linearize(self):
    print self.node,
    if self.children == []:
        print "NIL",
    for child in self.children:
        child.linearize()

Answer 1

如果我理解正确，你其实想要的是：

def linearize(self):
    print self.node,
    for child in self.children:
        child.linearize()
    print "NIL",

这样可以得到：

In [5]: t.linearize()
1 2 5 NIL 3 4 NIL NIL NIL NIL

现在，当有子元素时，你并没有打印 "NIL"。 （正如评论中提到的，你其实想要 children=None，然后用 self.children = children if children is not None else [] 这样的方式来处理。）

你可能还想把这个改成用 yield 来逐个输出每个元素，而不仅仅是打印它们，不过这当然取决于你自己。