Python实现BST递归插入节点失败：_root始终为空问题求助

你的递归插入逻辑存在两个核心问题，导致节点无法正确存储：

问题1：根节点未被更新 #

insert方法调用insertRec时，没有将返回值赋值给self._root。第一次插入时，curNode是None，insertRec会创建新节点，但这个新节点没有被同步回根节点，导致self._root始终保持None。

问题2：递归函数未返回节点 #

insertRec函数在完成节点创建或递归插入后，没有返回当前节点。这会导致父节点的_left或_right无法正确指向新插入的节点，所有插入操作都无法在树中留下痕迹。

修正后的代码 #

class DSATreeNode:
    def __init__(self, inKey, inValue):
        self._key = inKey
        self._value = inValue
        self._left = self._right = None

class DSABinarySearchTree:
    def __init__(self):
        self._root = None

    def find(self, key):
        return self._findRec(key, self._root)
    
    def _findRec(self, key, cur):
        value = None
        if cur == None: # Base case: not found
            raise Exception("Key " + str(key) + " not found")
        elif key == cur._key: # Base case: found
            value = cur._value
        elif key < cur._key: # Go left (recursive)
            value = self._findRec(key, cur._left)
        else: # Go right(recursive)
            value = self._findRec(key, cur._right)
        
        return value

    def insert(self, inKey, inValue):
        # 将递归插入的结果赋值给根节点，完成首次插入的根节点初始化
        self._root = self.insertRec(inKey, inValue, self._root)

    def insertRec(self, key, value, curNode):
        if curNode == None:
            # 仅当当前节点为空时创建新节点，避免不必要的对象实例化
            curNode = DSATreeNode(key, value)
        elif key < curNode._key:
            # 将递归插入的结果绑定到左子节点
            curNode._left = self.insertRec(key, value, curNode._left)
        else:
            # 将递归插入的结果绑定到右子节点
            curNode._right = self.insertRec(key, value, curNode._right)
        # 返回当前节点，让父节点能正确指向它
        return curNode

    def getRoot(self):
        if self._root is None:
            raise Exception("Tree is empty")
        return self._root._key, self._root._value

关键修改说明 #

• insert方法中，将insertRec的返回值赋值给self._root，确保第一次插入时根节点被正确初始化。
• insertRec函数末尾添加return curNode，让每一层递归都能返回当前节点，父节点的左/右子节点可以正确指向新插入的节点。
• 调整新节点创建时机，仅当curNode为空时才创建，避免每次递归都生成无用的节点对象。
• getRoot方法增加空树判断，避免空指针异常。
• _findRec中的异常信息改为str(key)，兼容非字符串类型的key。

内容的提问来源于stack exchange，提问作者Martin Chan