在 BST 中插入时超过最大递归深度

Question

我正在尝试实现二叉搜索树，我相信我的插入方法逻辑非常好，但是当我运行它时，我的代码抛出 'maximum recursion depth exceeded in comparison' 错误。

更新：我编辑了我的代码以修复最大递归深度，但现在我得到了一个不同的 AttributeError。

以下是我更新后的代码：

class BSTNode:
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.left = None
        self.right = None
        
class BST:
    def __init__(self):
        self.root = None
        self.size = 0
        
    def insert(self, key, value):
        if self.root is None:
            self.root = BSTNode(key, value)
        elif key < self.root.key:
            if self.root.left is None:
                self.root.left = BSTNode(key, value)
            else:
                self.root.left.insert(key, value)
        elif key > self.root.key:
            if self.root.right is None:
                self.root.right = BSTNode(key, value)
            else:
                self.root.right.insert(key, value)
                
        return self.root
    
if __name__ == '__main__':
    T = BST()
    T.insert(5, 'Mujeeb')
    T.insert(4, 'Hamza')
    T.insert(7, 'Ayesha')
    T.insert(9, 'Mahnoor')
    T.insert(11, 'Ali')
    print(T.root.right.key)

我遇到的错误：

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
<ipython-input-29-1eef6d5c8be5> in <module>
     23     T = BST()
     24     T.insert(5, 'Mujeeb')
---> 25     T.insert(4, 'Hamza')
     26     T.insert(7, 'Ayesha')
     27 

<ipython-input-29-1eef6d5c8be5> in insert(self, key, value)
     15             self.root = BSTNode(key, value)
     16         elif key < self.root.key:
---> 17             self.root.left = self.insert(key, value)
     18         elif key > self.root.key:
     19             self.root.right = self.insert(key, value)

... last 1 frames repeated, from the frame below ...

<ipython-input-29-1eef6d5c8be5> in insert(self, key, value)
     15             self.root = BSTNode(key, value)
     16         elif key < self.root.key:
---> 17             self.root.left = self.insert(key, value)
     18         elif key > self.root.key:
     19             self.root.right = self.insert(key, value)

RecursionError: maximum recursion depth exceeded in comparison

更新后的代码出现的新错误：

AttributeError                            Traceback (most recent call last)
<ipython-input-23-8ebfd3bbaceb> in <module>
     30 if __name__ == '__main__':
     31     T = BST()
---> 32     T.insert(5, 'Mujeeb')
     33     T.insert(4, 'Hamza')
     34     T.insert(7, 'Ayesha')

<ipython-input-23-8ebfd3bbaceb> in insert(self, key, value)
     14         if self.root is None:
     15             self.root = BSTNode(key, value)
---> 16             self.root.insert(key, value)
     17         elif key < self.root.key:
     18             if self.root.left is None:

AttributeError: 'BSTNode' object has no attribute 'insert'

如果您能提供任何指示说明我哪里出了问题，我将不胜感激，谢谢。

Answer 1

您的“插入”节点始终在树的根节点上操作。它应该在它插入的任何节点上运行。

如果您对节点使用单个 class 而不是 class 而对树使用另一个 class 可能会更容易，那样的话，每个节点都会有自己的“插入”方法会做正确的事。

class BSTNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.left = None
        self.right = None
        
    def insert(self, key, value):
        
        if key <= self.key:
            if not self.left:
                self.left = BSTNode(key, value)
            else:
                self.left.insert(key, value)
        elif key > self.key:
            if not self.right:
                self.right = BSTNode(key, value)
            else:
                self.right.insert(key, value)

在 BST 中插入时超过最大递归深度

Maximum recursion depth exceeded when inserting in BST

python

recursion

binary-search-tree

data-structures

python-3.x