实现二进制搜索树时，最大递归深度超过了Python的误差

Question

我正在使用python学习BST，并尝试实现插入和查找方法。但是我获得了最大的递归深度，超过了插入方法的误差。我是BST数据结构的新手，因此努力实施Python中的方法。我尝试研究和制作与互联网上的代码相似的代码，但是我仍会遇到错误。

class Node:
def __init__(self,data):
    self.data = data
    self.left = None
    self.right = None
class BST:
    def __init__(self):
        self.root = None  
    def insert(self,data):
        temp = Node(data)
        if self.root is None:
            self.root = temp
        else:
            self.insertNode(self.root,data)  
    def insertNode(self,root,data):
        temp = Node(data)
        if data < self.root.data:
            if self.root.left is None:
                self.root.left = temp
            else:
                self.insertNode(self.root.left,data)
        elif data > self.root.data:
            if self.root.right is None:
                self.root.right = temp
            else:
                self.insertNode(self.root.right,data)
    def findinTree(self,root,data):
        if self.root is None:
            return False
        if data == self.root.data:
            return True
        if data < self.root.data:
            self.findinTree(self.root.left,data)
        else:
            self.findinTree(self.root.right,data)
        return False

bst = BST()
bst.insert(30)
bst.insert(10)
bst.insert(50)
bst.insert(90)
bst.insert(100)
bst.insert(15)

请帮助调试错误，以使功能按预期工作。

Answer 1

这些方法可能是 root ;-)问题的原因：

def insertNode(self, root, data):
    if data < root.data:  # <- use the root parameter ...
        if root.left is None:
            root.left = Node(data)
        else:
            self.insertNode(root.left, data)
    else:
        if root.right is None:
            root.right = Node(data)
        else:
            self.insertNode(root.right, data)
def findinTree(self, root, data):
    if root is None:
        return False
    if data == root.data:
        return True
    if data < root.data:
        return self.findinTree(root.left, data)
    else:
        return self.findinTree(root.right, data)

nb 代码未测试

更新：提出了VPFB的建议，并且没有创建不必要的节点。

Answer 2

在insertNode中，您参考了self.root，这是树的根。相反，您应该引用 root，函数参数。

实际上，在创建第一个子级后（bst.insert(50)）之后，树的右分支不再是None，因此它不断调用self.insertNode(self.root.right,data)

def insertNode(self,root,data):                                                                                                                                                                          
    temp = Node(data)                                                                                                                                                                                    
    if data < root.data:                                                                                                                                                                                 
        if root.left is None:                                                                                                                                                                            
            print("Inserting {} on the left branch of {}".format(data, root.data))                                                                                                                       
            root.left = temp                                                                                                                                                                             
        else:                                                                                                                                                                                            
            print("Inserting {} on the left branch of {}".format(data, root.data))                                                                                                                       
            self.insertNode(root.left,data)                                                                                                                                                              
    elif data > root.data:                                                                                                                                                                               
        if root.right is None:                                                                                                                                                                           
            print("Inserting {} on the right branch of {}".format(data, root.data))                                                                                                                      
            root.right = temp                                                                                                                                                                            
        else:                                                                                                                                                                                            
            print("Inserting {} on the right branch of {}".format(data, root.data))                                                                                                                      
            self.insertNode(root.right,data)