删除二进制搜索树python中的节点 [英] delete node in binary search tree python

问题描述

下面的代码是我的二进制搜索树的实现，并且我想实现delete方法以删除该节点.以下是我的实现，但是当我执行

The code below is my implement for my binary search tree, and I want to implement delete method to remove the node. Below is my implementation, but when I perform

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

when I call delete method, it did nothing. Can someone help me to fix it. The link below is my code on github. Thank you so much for your help. 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, "")

推荐答案

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中的二进制搜索树

This might help. For complete code and better understanding go to For code Binary search Tree in Python

说明 关于Python中BST的注意事项 据我所知，它工作正常.

For explanation Notes on BST in Python As per my knowledge its working fine.

这篇关于删除二进制搜索树python中的节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！