Python递归二叉搜索树

Question

我正试图使用节点类和树类在python中递归地实现一个二进制搜索树

# MAKE CUSTOM ERROS
class Error(Exception):
    pass

class InvalidKeyError(Error):
    pass

# TREE NODE CLASS
class TreeNode():
    def __init__(self, inKey, inValue): # eahc node has a key with an associated value
        self._key = inKey
        self._value = inValue
        self._left = None
        self._right = None

    def __str__(self): # Used for printing
        return ("Key: " + str(self._key) + " Value: " + str(self._value))

# SEARCH TREE CLASS
class BinarySearchTree():
    def __init__(self):
        self._root = None # start with an empty tree

    # Wrapper method
    def find(self, key):
        return self._findRec(key, self._root)

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

    # Wrapper method
    def insert(self, key, data):
        return self._insertRec(key, data, self._root)

    def _insertRec(self, key, data, cur):
        updateNode = cur
        if cur == None:
            updateNode = TreeNode(key, data)
        elif key == cur._key: # in the tree
            raise InvalidKeyError("Key " + str(key) + " is already in the tree")
        elif key < cur._key:
            cur._left = self._insertRec(key, data, cur._left)
        else:
            cur._right = self._insertRec(key, data, cur._right)
        return updateNode
    
# TESTING
if __name__ == "__main__":
    myTree = BinarySearchTree()
    myTree.insert(9, "nine")
    myTree.insert(5, "five")
    myTree.insert(13, "thirteen")

    print(myTree.find(13))

在树中插入键/值时，我没有收到任何错误，但在尝试查找树中的节点时收到错误。
InvalidKeyError:找不到键13

我的insert方法中是否存在逻辑错误？谢谢大家!

Answer 1

递归插入的东西不能工作。当您注意到节点为空时，您就不再有要修改的内容了。这似乎有效：

    def _insertRec(self, key, data, cur):
        newnode = TreeNode(key, data)
        if not self._root:
            self._root = newnode
            return

        while key != cur._key:
            if key < cur._key:
                if not cur._left:
                    cur._left = newnode
                    return
                cur = cur._left
            else:
                if not cur._right:
                    cur._right = newnode
                    return
                cur = cur._right
                
        raise InvalidKeyError("Key " + str(key) + " is already in the tree")