BST树错误：“int”和“Node”实例之间不支持“<=”类型错误

Question

我正在尝试实现BST。我在Python中的代码如下：

class Node: 
    def __init__(self, val):
        self.val = val
        self.leftChild = None
        self.rightChild = None

    def get(self):
        return self.val

    def getleftChild(self):
        return self.leftChild

    def getrightChild(self):
        return self.rightChild

    def set(self, val):
        self.val = val

    def getChildren(self):
        children = []
        if self.leftChild != None:
            children.append(self.leftChild)
        if self.rightChild != None:
            children.append(self.rightChild)
        return children

class BST: 
    def __init__(self):
        self.root = None

    def setRoot(self, val):
        self.root = Node(val)

    def insert(self, val):
        if self.root == None:
            self.setRoot(val)
        else:
            self.insertNode(self.root, val)

    def insertNode(self, CurrentNode, val):
        if val <= CurrentNode.get(): 
            if CurrentNode.leftChild:
                self.insertNode(CurrentNode.leftChild, val)
            else:
                CurrentNode.leftChild = Node(val)
        elif val < CurrentNode.get():
            if CurrentNode.rightChild:
                self.insertNode(CurrentNode.rightChild, val)
            else:
                CurrentNode.rightChild = Node(val)

new_BST = BST()

root_node = Node(2)
new_BST.setRoot(root_node)

array = [4,5,2,1,6,3]

for element in array:
    new_BST.insert(element)

我不断收到一个类型错误：'<；='“int”和“Node”实例之间不支持 在insertNode部分的第41行，我不知道为什么。我正在调用.get（），它应该返回一个int，所以我不确定为什么比较不起作用

Answer 1

类型注释使查找以下错误变得更加容易：

from typing import List, Optional


class Node:
    def __init__(self, val: int):
        self.val = val
        self.leftChild: Optional['Node'] = None
        self.rightChild: Optional['Node'] = None

    def get(self) -> int:
        return self.val

    def getleftChild(self) -> Optional['Node']:
        return self.leftChild

    def getrightChild(self) -> Optional['Node']:
        return self.rightChild

    def set(self, val: int) -> None:
        self.val = val

    def getChildren(self) -> List['Node']:
        children: List['Node'] = []
        if self.leftChild is not None:
            children.append(self.leftChild)
        if self.rightChild is not None:
            children.append(self.rightChild)
        return children


class BST:
    def __init__(self):
        self.root: Optional[Node] = None

    def setRoot(self, val: int) -> None:
        self.root = Node(val)

    def insert(self, val: int) -> None:
        if self.root is None:
            self.setRoot(val)
        else:
            self.insertNode(self.root, val)

    def insertNode(self, CurrentNode: Node, val: int) -> None:
        if val <= CurrentNode.get():
            if CurrentNode.leftChild:
                self.insertNode(CurrentNode.leftChild, val)
            else:
                CurrentNode.leftChild = Node(val)
        elif val < CurrentNode.get():
            if CurrentNode.rightChild:
                self.insertNode(CurrentNode.rightChild, val)
            else:
                CurrentNode.rightChild = Node(val)


new_BST = BST()

root_node = Node(2)
new_BST.setRoot(root_node)

array = [4, 5, 2, 1, 6, 3]

for element in array:
    new_BST.insert(element)

对代码进行注释时，可以使用静态类型检查器，如mypy，此处显示错误：

tree.py:57: error: Argument 1 to "setRoot" of "BST" has incompatible type "Node"; expected "int"

这似乎确实是问题所在，你正在创建一个Node，它的val是一个Node，而不是一个int

直到稍后insertNode尝试比较这两个值时，您才会看到该错误，这可能会使运行时调试变得困难。但是，如果预先声明setRoot使用了int参数，那么mypy甚至在实际运行代码之前就可以让您知道错误（以及错误的确切位置）

有关mypy和类型检查的详细信息，请参见此处：https://mypy.readthedocs.io/en/stable/