在 Python 中从 BST 中删除一个片段

Question

首先post在这里。我应该构建一个 BST（我已经完成了）并创建一个 deleteNode 函数。我一直在尝试运行该功能，但不幸的是它无法正常工作。

#deleteFunction#

def deleteNode(self, data):

    if self is None:                                ##none is left and right val
        return self

    if data < self.data:                             #if input is less than current
        self.left = self.deleteNode(self.left, data)  #go to the left node

    elif (data > self.data):                         #if input is higher, go to right node
        self.right = self.deleteNode(self.right, data)

    else:
        if self.left is None:
            temp = self.right                       #if left is none then assign temp to right
            self.left = None
            return temp

        elif self.right is None:                    #if right is none, assign temp to left
            temp = self.left
            self.left = None
            return temp

        temp = findMinNode(self.right)          ##node with two children, get the smallest right subtree
        self.data = temp.data                   ##copy the right small subtree
        self.right = deleteNode(self.right, temp.data)  #delete smallest right subtree
    return self

##执行代码：##

print("Maximum node in BT: \n", dTree.findMaxNode())
print("Minimum node in BT: \n",dTree.findMinNode())
print("Post Order: \n", dTree.postOrderTrav())
print("Pre Order: \n", dTree.preOrderTrav())
print("In Order: \n", dTree.inOrderTrav())

dTree.deleteNode(4)

print("deletion of one node: ")
print (dTree.inOrderTrav())

我不断收到以下错误：

line 262, in <module> dTree.deleteNode(4)
File "C:/Users", line 215, in deleteNode self.right = self.deleteNode(self.right, data)
TypeError: deleteNode() takes 2 positional arguments but 3 were given
 200

Answer 1

这是我最喜欢的在 BST 中删除节点的版本 - 使用 deleteNode 函数，root 是根节点，key 是要删除的节点值.

class DeletingNodeBST:
    def successor(self, root):
        root = root.right
        while root.left:
            root = root.left
        return root.val
    
    def predecessor(self, root):
        root = root.left
        while root.right:
            root = root.right
        return root.val
        
    def deleteNode(self, root, key):
        if not root:
            return None
        
        if key > root.val:
            root.right = self.deleteNode(root.right, key)
        elif key < root.val:
            root.left = self.deleteNode(root.left, key)
        else:
            if not (root.left or root.right):
                root = None
            elif root.right:
                root.val = self.successor(root)
                root.right = self.deleteNode(root.right, root.val)  
            else:
                root.val = self.predecessor(root)
                root.left = self.deleteNode(root.left, root.val)
                        
        return root

注意root是根节点，可以通过以下方式创建：

class Node: 
    def __init__(self, key): 
        self.key = key  
        self.left = None
        self.right = None

在 Python 中从 BST 中删除一个片段

Delete a segment from BST in Python

python

syntax-error

binary-search-tree

b-tree