AttributeError: 'NoneType' object has no attribute height in BST pythons height

Question

这是我在 python 中创建 BST 的代码，一切正常，但是当我访问高度函数时，它给出了类似 "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 .

在代码中 height -

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 ，并根据它从中获取高度。

Answer 2

如果您收到这样的错误，则表示您尝试使用 None 的字段。因为您的树是有限的，所以您的叶子没有任何数据。我看到你在代码中有一个地方 self.data 字段被分配了一个值，但 self.left 和 self.right 没有。同时，你在height方法中获取字段的值，你只检查self.data。这对我来说没有意义。

此外，我建议尝试 pdb 或其他调试工具。

AttributeError: 'NoneType' object has no attribute height in BST pythons height

AttributeError: 'NoneType' object has no attribute height in BST pythons height

python

tree

height

binary-search-tree

data-structures