在Python中递归遍历树结构

Question

我正在为一个自定义的系统发育树类实现一个长度方法，这样我们就可以对它使用len(TreeObject)来获取树的长度。树的长度是由它有多少个叶子节点来决定的。叶子节点的意思是这个节点没有子节点。'self.children'是一个包含该节点子节点的元组列表，每个元组里有(node, weight)。我觉得我已经很接近了：

 def __len__(self):

# everytime it reaches the base case I should add 1
    if self.isLeaf():
        print('base case - reached leaf!')
        return 1

    for t,w in self.children:  
        print('not leaf so sent through loop')
        numLeaves = len(t)

    return numLeaves

代码正确地进入了if语句的次数，比如说如果长度是3，它会输出'基本情况 - 到达叶子节点！' 3次。我只需要一种方法来把这些结果加在一起，并存储到一个变量中。

Answer 1

你说得很对。你现在只是把 numLeaves 的值覆盖掉了，而不是把它们加起来：

numLeaves = 0
for t,w in self.children:  
    print('not leaf so sent through loop')
    numLeaves += len(t)

这也可以用另一种方式来实现：

sum(len(t) for (t,w) in self.children)