二叉搜索树(BST)删除方法异常：删除节点2后仍存在

常见失效原因 #

• 根节点删除未更新root引用：如果要删除的是根节点，却没修改树的root属性，原根节点会一直存在。比如你的案例中节点2是根节点，删除后root没更新，导致打印仍能看到它。
• 父节点指针未正确修改：删除节点时，没有将父节点的左/右指针指向被删节点的子节点，原节点仍会留在树的结构中。
• 双子女节点的后继处理错误：当被删节点有两个子节点时，若未正确找到后继节点（右子树最小节点）并完成替换、删除操作，会导致原节点残留。

修复后的完整代码 #

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

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

    def insert(self, key):
        if self.root is None:
            self.root = Node(key)
        else:
            self._insert_recursive(self.root, key)

    def _insert_recursive(self, node, key):
        if key < node.val:
            if node.left is None:
                node.left = Node(key)
            else:
                self._insert_recursive(node.left, key)
        else:
            if node.right is None:
                node.right = Node(key)
            else:
                self._insert_recursive(node.right, key)

    def delete(self, key):
        # 关键：通过递归返回值更新root及父节点指针
        self.root = self._delete_recursive(self.root, key)

    def _delete_recursive(self, node, key):
        if node is None:
            return node

        # 递归查找目标节点
        if key < node.val:
            node.left = self._delete_recursive(node.left, key)
            return node
        elif key > node.val:
            node.right = self._delete_recursive(node.right, key)
            return node
        else:
            # 情况1：节点无左/右子节点
            if node.left is None:
                return node.right
            elif node.right is None:
                return node.left
            
            # 情况2：节点有两个子节点，找右子树最小节点（后继）
            successor_parent = node
            successor = node.right
            while successor.left is not None:
                successor_parent = successor
                successor = successor.left
            
            # 替换当前节点值为后继节点值
            node.val = successor.val
            # 删除后继节点
            if successor_parent == node:
                successor_parent.right = successor.right
            else:
                successor_parent.left = successor.right
            return node

    def print_tree(self):
        self._print_recursive(self.root)

    def _print_recursive(self, node):
        if node is not None:
            self._print_recursive(node.left)
            print(node.val, end=' ')
            self._print_recursive(node.right)

# 测试验证
tree = BST()
nodes = [2,5,7,10,20,35]
for num in nodes:
    tree.insert(num)

print("初始树：")
tree.print_tree()  # 输出：2 5 7 10 20 35

tree.delete(2)
print("\n删除2后：")
tree.print_tree()  # 输出：5 7 10 20 35

# 删除所有节点
for num in nodes:
    tree.delete(num)
print("\n删除所有节点后：")
tree.print_tree()  # 无输出

核心修复点说明 #

1. 更新root引用：delete方法中通过self.root = self._delete_recursive(...)确保根节点被删除时，树的根指针会被正确替换。
2. 递归维护父节点指针：在递归查找过程中，将父节点的left/right赋值为递归返回的节点，保证删除操作后树的结构正确。
3. 正确处理双子女节点：找到后继节点后，用后继节点的值替换被删节点的值，再删除后继节点，避免原节点残留。

内容的提问来源于stack exchange，提问作者Muhammad Olamide