Python:计算树的节点数

Question

实际上，我正在编写一个返回树大小的方法:

def size(self):
    count = 0
    hasLeft, hasRight = self.left is not None, self.right is not None
    if hasLeft:
        count += self.left.size()
    if hasRight:
        count += self.right.size()
    if (hasLeft or hasRight) and self.root_value is not None:
        count += 1
    return count

该方法有效，但仅适用于内部节点:(我确信一定有一个非常简单的解决方案来获取树的大小......但是如何呢？例子:如果我打电话:

tree=Tree_Class(2,Tree_Class(1,Tree_Class(3),Tree_Class(20)),Tree_Class(13,Tree_Class(33),Tree_Class(39)))
tree.size()

所需的输出是:7

感谢您的帮助!

Answer 1

问题是你的语句if (hasLeft or hasRight) and self.root_value is not None: ---这个检查是错误的，它只有+=1 if该节点不是叶子。当调用 size 时，该节点必须有效(根据您的逻辑)，因此 count 应始终 += 1。

更简单的代码如下所示

class Tree_Class:
    def __init__(self, t, left=None, right=None):
        self.root_value = t
        self.left = left
        self.right = right

    def size(self):
        count = 1
        if self.left:
            count += self.left.size()
        if self.right:
            count += self.right.size()
        return count

结果:

>>> tree=Tree_Class(2,Tree_Class(1,Tree_Class(3),Tree_Class(20)),Tree_Class(13,Tree_Class(33),Tree_Class(39)))
>>> tree.size()
7