Python实现BST删除节点时误删整棵子树的问题排查

你遇到的问题核心是处理含两个子节点的目标节点时逻辑出错，导致误删整个右子树。BST 删除节点的关键是严格分三种场景处理，尤其是第三种场景（节点有左右子树），必须通过「替换值+删除替代节点」的方式操作，而非直接砍掉子树。

正确删除逻辑拆解 #

BST 删除节点分三种核心场景：

• 场景1：目标节点是叶子节点：直接将其父节点指向它的指针设为None。
• 场景2：目标节点只有一个子节点：用该子节点直接替换目标节点（让父节点指向子节点）。
• 场景3：目标节点有两个子节点：
  1. 找到右子树的最小节点（后继节点），或左子树的最大节点（前驱节点）；
  2. 将后继节点的值复制到目标节点中；
  3. 删除这个后继节点（它必然是叶子节点或只有一个右子节点，符合前两种场景）。

正确实现代码 #

以下是完整的 BST 类实现，包含delNode方法及测试逻辑：

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

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

    # 插入节点（用于构建测试树）
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
            return
        curr = self.root
        while True:
            if val < curr.val:
                if not curr.left:
                    curr.left = TreeNode(val)
                    break
                curr = curr.left
            else:
                if not curr.right:
                    curr.right = TreeNode(val)
                    break
                curr = curr.right

    # 中序遍历（验证BST结构正确性）
    def inorder(self, node):
        if not node:
            return []
        return self.inorder(node.left) + [node.val] + self.inorder(node.right)

    # 删除节点核心方法（递归实现）
    def delNode(self, root, key):
        if not root:
            return root
        
        # 定位目标节点
        if key < root.val:
            root.left = self.delNode(root.left, key)
        elif key > root.val:
            root.right = self.delNode(root.right, key)
        else:
            # 场景1：只有右子节点或无子女
            if not root.left:
                return root.right
            # 场景2：只有左子节点
            elif not root.right:
                return root.left
            # 场景3：有两个子女，找右子树最小节点（后继）
            curr = root.right
            while curr.left:
                curr = curr.left
            # 复制后继节点值到目标节点
            root.val = curr.val
            # 删除后继节点（递归处理，符合前两种场景）
            root.right = self.delNode(root.right, curr.val)
        return root

测试验证 #

# 构建测试树：
#        5
#      /   \
#     3     8
#    / \   / \
#   2   4 7   9
bst = BST()
for val in [5,3,8,2,4,7,9]:
    bst.insert(val)

print("删除前中序遍历：", bst.inorder(bst.root))  # 输出 [2,3,4,5,7,8,9]
bst.root = bst.delNode(bst.root, 8)
print("删除后中序遍历：", bst.inorder(bst.root))  # 正确输出 [2,3,4,5,7,9]

错误排查关键点 #

对比你的代码，重点检查以下几点：

• 是否正确区分了三种删除场景？
• 处理双子女节点时，是否是复制后继节点的值，再递归删除后继节点，而非直接用后继节点替换整个右子树？
• 递归返回时，是否正确更新了父节点的左/右指针？

比如常见错误写法是直接替换节点，导致右子树其他节点丢失：

# 错误示例：直接替换节点，破坏原有子树结构
root.right = curr

内容的提问来源于stack exchange，提问作者Nick H