Python中二叉搜索树节点的删除

Question

Python中二叉搜索树节点的删除

6

以下是我实现的二叉搜索树代码，我希望能够实现删除节点的方法。以下是我的实现，但是当我执行时：

bst = BSTRee()
bst.insert(5)
bst.insert(11)
bst.insert(3)
bst.insert(4)
bst.insert(12)
bst.insert(2)
bst.delete(3)

当我调用delete方法时，它什么也没做。有人能帮我解决这个问题吗？下面的链接是我在github上的代码。非常感谢您的帮助。 https://github.com/hly189/sort/blob/master/tree/BST.py

class BSTreeNode
    def ____init__(self, value): 
        self.value = value 
        self.left = None 
        self.right = None

   def insert(self,key): 
        if self.value == key: 
            print ("the node already exists")
            return False 
        elif self.value > key: 
            if self.left is not None: 
               return self.left.insert(key)
            else: 
               self.left = BSTreeNode(key)
               return True
        else: 
             if self.right is not None: 
               return self.right.insert(key)
            else: 
               self.right = BSTreeNode(key)
               return False

    def delete(self, node, k):
            if node == None: 
               return None
            elif node.value == k: 
               if node.left is None and node.right is None: 
               return None
            elif node.left is None: 
                return node.right
            elif node.right is None: 
                return node.left 
            else: 
                node.value = get_min(node.right)
                node.right.delete(node.right,node.value)
            elif k < node.value: 
                node.left.delete(node.left,k)
            else: 
                node.right.delete(node.right,k)
            return node

class BSTree: 
    def __init__(self): 
           self.root = None 

    def delete(self,key): 
           self.root.delete(self.root,key)

    def insert(self,data): 
           if self.root: 
               self.root.insert(data)
           else: 
               self.root = BSTreeNode(data)
               return True 
    def find_min(self,node):
           current_node = node
           while current_node.left: 
               current_node = current_node.left
           return current_node


def get_min(node): 
    current_node = node
    while current_node.left: 
        current_node = current_node.left
    return str(current_node.value)

def print_helper(root, indent):
    if root is not None:
        print_helper(root.right, indent + "   ")
        print (indent + str(root.value))
        print_helper(root.left, indent + "   ")

def print_tree(root):
     print_helper(root, "")

- Alexander

BSTreeNode.delete()看起来好像什么都没做。它在四处嗅探并返回一些东西，但我没有看到任何实际修改你的树的地方。 - Tom Karzes

你能帮我修复一下吗？因为我已经在这上面工作了4个小时了。 - Alexander

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Prashant Shukla · Accepted Answer

def delete(self, key):
    """ delete the node with the given key and return the 
    root node of the tree """

    if self.key == key:
        # found the node we need to delete

        if self.right and self.left: 

            # get the successor node and its parent 
            [psucc, succ] = self.right._findMin(self)

            # splice out the successor
            # (we need the parent to do this) 

            if psucc.left == succ:
                psucc.left = succ.right
            else:
                psucc.right = succ.right

            # reset the left and right children of the successor

            succ.left = self.left
            succ.right = self.right

            return succ                

        else:
            # "easier" case
            if self.left:
                return self.left    # promote the left subtree
            else:
                return self.right   # promote the right subtree 
    else:
        if self.key > key:          # key should be in the left subtree
            if self.left:
                self.left = self.left.delete(key)
            # else the key is not in the tree 

        else:                       # key should be in the right subtree
            if self.right:
                self.right = self.right.delete(key)

    return self

def _findMin(self, parent):
    """ return the minimum node in the current tree and its parent """

    # we use an ugly trick: the parent node is passed in as an argument
    # so that eventually when the leftmost child is reached, the 
    # call can return both the parent to the successor and the successor

    if self.left:
        return self.left._findMin(self)
    else:
        return [parent, self]

这可能有所帮助。欲获取完整代码和更好的理解，请访问以下代码链接：Python中的二叉搜索树。

欲了解详细解释，请参考以下说明链接：Python中的BST笔记。据我所知，它的运行良好。