为什么我最初为 BST 将 root 设置为 None 时会出现错误

Question

当我最初将 root 设置为 None（参见代码）

时，我收到 TypeError: '<' not supported between 'BST' and 'int'

class BST:
    def __init__(self,key):
        self.key = key
        self.lchild = None
        self.rchild = None

    def insert(self,data):
        if self.key is None:
            self.key = BST(data)
            return
        if self.key < data:
            if self.lchild:
                self.lchild.insert(data)
            else:
                self.lchild = BST(data)
        else:
            if self.rchild:
                self.rchild.insert(data)
            else:
                self.rchild = BST(data)
    
    def preorder(self):
        print(self.key)
        if self.lchild:
            self.lchild.preorder()
        if self.rchild:
            self.rchild.preorder()



root = BST(None)

list1 = [20,34,1,3,4,78]
for i in list1:
    root.insert(i)

root.preorder()

当我将 root 设置为 int 时，它工作正常

Answer 1

刚开始设置root = None。

并检查插入方法中的if root == None。

Answer 2

评论说你应该调试。他们并没有错，但当你不理解错误时，可能很难看出如何做到这一点。

该错误通常意味着您在某处将 BST 与 int 进行比较，而这未定义。

让我们通过添加

来看看类型

print(f"{type(self.key)=},\t{type(data)=}")

到 insert 函数的开头。

我们得到：

type(self.key)=<class 'NoneType'>,  type(data)=<class 'int'>
type(self.key)=<class '__main__.BST'>,  type(data)=<class 'int'>
Traceback (most recent call last):
  File "tmp.py", line 36, in <module>
    root.insert(i)
  File "tmp.py", line 12, in insert
    if self.key < data:
TypeError: '<' not supported between instances of 'BST' and 'int'

所以显然我们首先正确执行函数一次 key 是 None 然后再次 key 是一个 BST 对象。 data 始终是 int.

但是您还没有定义如何比较 int 和 BST。

你想这样做吗？可能不会。因为您的密钥应该是 int，对吗？你有一个 BST 但 BST 中的键应该是 int。因此，在 none 的情况下，分配密钥时不需要 BST(data)。相反：

if self.key is None:
    self.key = data
    return

为什么我最初为 BST 将 root 设置为 None 时会出现错误

Why do I get error when I set root to None initially for BST

python

binary-search-tree