python - 二进制搜索树Python，实现删除

我正在尝试在python中实现二进制搜索树，但找不到删除的解决方案。如果该项目在叶子中，那很简单，但是如果我要删除的项目有2个子项又有其他子项，该怎么办？如何找到它的后继者，以便我可以替代它？有没有简单的递归解决方案？

class Node:

    def __init__(self, data=None, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right


class BinarySearchTree:


    def __init__(self, root=None):
        self.root = Node(root)


    def add(self, data, node):

        if node == None:
            node = Node(data)
            return True

        if data < node.data:
            if node.left == None:
                node.left = Node(data)
                return True
            else:
                self.add(data, node.left)
        elif data > node.data:
            if node.right == None:
                node.right = Node(data)
                return True
            else:
                self.add(data, node.right)


    def preorder(self, node):
        if node != None:
            print(node.data)
            self.preorder(node.left)
            self.preorder(node.right)

    def inorder(self, node):
        if node != None:
            self.inorder(node.left)
            print(node.data)
            self.inorder(node.right)

    def postorder(self, node):
        if node != None:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.data)


    def retreive(self,item):

        node = self.root

        while node != None:
            if node.data == item:
                break
            elif item < node.data:
                if node.left != None:
                    if node.left.data == item:
                        node.left = None
                        return True
                node = node.left
            else:
                if node.right != None:
                    if node.right.data == item:
                        node.right= None
                        return True
                node = node.right

        if node == None:
            return False

tree = BinarySearchTree()
root=Node(3)
tree.add(55,root)
tree.add(5,root)
tree.add(13,root)
tree.add(2,root)
tree.add(3,root)
tree.preorder(root)
tree.postorder(root)
tree.inorder(root)

另外，如果您对我到目前为止所写的内容有任何建议，我也将不胜感激。提前致谢。

最佳答案

如果这不是家庭作业，则可以使用以下方法之一：


https://pypi.python.org/pypi/treap/
https://pypi.python.org/pypi/red-black-tree-mod


两者都实现删除。两者都很好地处理了已排序或未排序的输入。

红黑树模块具有RedBlackTree继承的BinaryTree类。

关于python - 二进制搜索树Python，实现删除，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/20156243/