python - 属性错误: 'NoneType' object has no attribute height in BST pythons height

Question

这是我在 python 中创建 BST 的代码，一切工作正常，但是当我访问 height 函数时，它会给出类似“AttributeError: 'NoneType' object has no attribute height”的错误，我是在 python 中创建数据结构的新手，任何帮助都会受到赞赏

 class Node:
        def __init__(self, data):
            self.left = None
            self.right = None
            self.data = data
        def insert(self, data):
            if self.data:
                if data < self.data:
                    if self.left is None:
                        self.left = Node(data)
                    else:
                        self.left.insert(data)
                elif data > self.data:
                    if self.right is None:
                        self.right = Node(data)
                    else:
                        self.right.insert(data)
            else:
                self.data = data

        def print_tree(self):

            if self.left:
                self.left.print_tree()
            print (self.data)
            if self.right:
                self.right.print_tree()

        def height(self):
            if self.data is None:
                return 0
            else:
                return 1 + max(self.left.height(),self.right.height())

    root = Node(8)
    root.insert(3)
    root.insert(10)
    root.insert(1)
    root.insert(6)
    root.insert(4)
    root.insert(7)
    root.insert(14)
    root.insert(13)
    root.print_tree()
    root.height()

Answer 1

对于树中的叶节点，self.data 将设置为叶节点的值，但 self.left 和 self.right 将是 None。但即使在此之前，也可能存在左子节点或右子节点为 None 的节点，并且由于我们尝试该节点并获取其高度，我们在 NoneType 上得到了 AttributeError .

在高度代码中 -

def height(self):
    if self.data is None:
        return 0
    else:
        return 1 + max(self.left.height(),self.right.height())

当递归到达一个节点时，其中 left 或 right 节点为 None，上面的代码将失败，因为它会尝试访问 self.left .height() 或 self.right.height() ，其中之一是 None。

我们可以添加一个简单的检查来查看 self.left 或 self.right 是否为 None ，并据此得到距离它的高度。