Python 递归二叉搜索树

Question

我正在尝试使用节点 class 和树 class.

在 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))

我在将 keys/values 插入我的树时没有收到任何错误，但我在尝试在树中查找节点时收到错误。
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")

Python 递归二叉搜索树

Python Recursive Binary Search Tree

python

class

recursion

data-structures

binary-search-tree