可以帮助我了解我在 BST 的插入和搜索操作中的错误吗？

Question

我正在 Python 中实施 BST。我已经编写了用于在 BST 中插入数据和搜索数据的函数。问题是，我已经尝试了很多次来找出我犯了什么错误，但我一直没能改正。我请求一些帮助。请帮助我。

class Node:

    def __init__(self, data):
        self.data = data
        self.left_ptr = None
        self.right_ptr = None

class BinarySearchTree:

    def __init__(self):
        self.ptr_to_root = None


    def insert(self, data):
        '''
        This feature/function helps the users to insert data into a Binary 
        Search Tree.
        '''
        # To insert, the first thing we have to do is
        # creating a node :-
        node = Node(data)
        
        # We create a temperory pointer as we
        # won't move ptr_to_root.
        temp_ptr = self.ptr_to_root

        # CASE 1 > If ptr_to_root is None i.e. If BST
        # is empty :
        if temp_ptr == None:
            temp_ptr = node
        

        # CASE 2 > If BST is not empty already : 
        while temp_ptr != None:
             
            # Below is the pointer which will remain behind
            # temp_ptr by one step.
            r = temp_ptr
            
            # If we already have the data present in BST, we
            # cannot re-enter it. Hence, we simply exit the 
            # function.
            if data == temp_ptr.data:
                return
            
            # If the data is having lesser value then temp_ptr's data, 
            # then we move the temp_ptr to its left, or else the right.
            if data < temp_ptr.data:
                temp_ptr = temp_ptr.left_ptr
            else:
                temp_ptr = temp_ptr.right_ptr
        
        # r is the tail pointer, which follows the temp_ptr. 
        # Eventually, we will compare if the value that we wanrt to insert
        # is less or more then r.data, and accordingly insert the data desired.
        if data < r.data:
            r.left_ptr = node
        else:
            r.right_ptr = node

    

    def search(self, data):
        
        # If the BST is empty, then we do not 
        # have the element present in the BST for sure:
        temp_ptr = self.ptr_to_root
        
        # If BST is empty, then :
        if temp_ptr == None:
            return None

        
        # If BST is not empty, we may or may not be 
        # finding the element in the tree :
        while temp_ptr != None:

            if data == temp_ptr.data:
                return temp_ptr
            
            elif data < temp_ptr.data:
                temp_ptr = temp_ptr.left_ptr
            
            else:
                temp_ptr = temp_ptr.right_ptr
        
        # If the element is not present in BST :
        return None

当我运行上面的代码插入一个元素然后搜索它；它 returns 'None' 即使我搜索我插入的元素。请帮忙！

Answer 1

您的问题实际上非常简单，使用调试器只需几分钟便可解决。您永远不会创建根节点。当你试图向一棵空树中插入一些东西时，你设置了节点，但你没有保存它，所以树总是空的。改变这个：

        # CASE 1 > If ptr_to_root is None i.e. If BST
        # is empty :
        if temp_ptr == None:
            temp_ptr = node
            self.ptr_to_root = node    # <<< add this line

一切正常。

可以帮助我了解我在 BST 的插入和搜索操作中的错误吗？

Can I be helped in knowing my mistake in the insertion and searching operations of a BST?

python

data-structures

binary-search-tree