python - 计算二叉树中的节点数

Question

我正在尝试编写一个函数，该函数使用递归来查找节点数，即二叉树的大小。如果树是空的，则没有节点。如果它不为空，则节点数为 1(根)加上左子树的节点数和右子树的节点数。

我打算使用提供给我的二叉树类来执行此操作。

这是我的二叉树类:

class BinaryTree:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insert_left(self, new_data):
        if self.left == None:
            self.left = BinaryTree(new_data)
        else:
            t = BinaryTree(new_data)
            t.left = self.left
            self.left = t

    def insert_right(self, new_data):
        if self.right == None:
            self.right = BinaryTree(new_data)
        else:
            t = BinaryTree(new_data)
            t.right = self.right
            self.right = t

    def get_left(self):
        return self.left


    def get_right(self):
        return self.right

    def set_data(self, data):
        self.data = data

    def get_data(self):
        return self.data

这是我计算大小的递归函数:

def size(my_tree):
    count = 0
    if my_tree.get_data() is None:
        return 0
    else:
        count += 1 + size(my_tree.get_left()) + size(my_tree.get_right())
    return count

但是，当我用这个程序运行它时:

 a = BinaryTree(1)
 a.insert_left(2)
 a.insert_right(3)
 print(size(a))

我收到以下错误:

Original exception was:
Traceback (most recent call last):
    File "prog.python3", line 57, in <module>
        print(size(a))
    File "prog.python3", line 41, in size
        count += 1 + size(my_tree.get_left()) + size(my_tree.get_right())
    File "prog.python3", line 38, in size
        if my_tree.get_data() is None:
AttributeError: 'NoneType' object has no attribute 'get_data'

什么时候输出应该是:

3

我根本不明白我做错了什么，但我很确定这一定与 if 语句有关。

Answer 1

只需将您的if 语句修改为

if my_tree is None:
    return 0

出现此错误是因为您在对二叉树的叶节点进行递归调用时试图访问 NULL 数据对象的 get_data 属性。

相反，当您到达 NoneType 节点时，您实际需要做的是返回 0。