Python实现二叉搜索树（BST）删除操作详解（小白也能学会的BST删除算法）

一、BST删除的三种情况

删除BST中的一个节点时，需要考虑以下三种情况：

1. 被删除节点是叶子节点（没有子节点）：直接删除即可。
2. 被删除节点只有一个子节点：用其子节点替代该节点。
3. 被删除节点有两个子节点：找到它的中序后继（右子树中的最小值）或中序前驱（左子树中的最大值），用该值替换当前节点，然后删除那个后继/前驱节点。

二、Python代码实现

首先，我们定义BST的节点类：

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

接下来，我们实现删除函数。核心思路是递归地查找目标节点，并根据上述三种情况进行处理：

def deleteNode(root, key):    # 基本情况：如果根为空，说明没找到要删除的节点    if not root:        return root        # 如果key小于当前节点值，去左子树找    if key < root.val:        root.left = deleteNode(root.left, key)    # 如果key大于当前节点值，去右子树找    elif key > root.val:        root.right = deleteNode(root.right, key)    # 找到了要删除的节点    else:        # 情况1：没有左子树，返回右子树        if not root.left:            return root.right        # 情况2：没有右子树，返回左子树        elif not root.right:            return root.left                # 情况3：左右子树都存在        # 找到右子树中的最小值（中序后继）        min_node = findMin(root.right)        # 用后继节点的值替换当前节点的值        root.val = min_node.val        # 删除后继节点        root.right = deleteNode(root.right, min_node.val)        return rootdef findMin(node):    # 找到以node为根的子树中的最小值节点    while node.left:        node = node.left    return node

三、代码解析

- 当 key < root.val 时，递归处理左子树；当 key > root.val 时，递归处理右子树。

- 如果找到了要删除的节点（key == root.val）：

• 若无左子树，直接返回右子树作为新的子树根。
• 若无右子树，直接返回左子树。
• 若左右都有，则找到右子树的最小值（即中序后继），将其值赋给当前节点，再递归删除那个后继节点（此时后继节点最多只有一个右子树，可归约为前两种情况）。

四、使用示例

# 构建一个简单的BSTroot = TreeNode(5)root.left = TreeNode(3)root.right = TreeNode(6)root.left.left = TreeNode(2)root.left.right = TreeNode(4)root.right.right = TreeNode(7)# 删除节点3（有两个子节点）root = deleteNode(root, 3)# 此时树中不再有3，而是用4替换了3的位置

五、总结

通过本文，你已经掌握了用Python实现BST删除操作的核心逻辑。无论是面试还是实际开发，二叉搜索树删除操作都是数据结构中的经典问题。

记住三种删除情况，并熟练使用递归思想，你就能轻松应对这类问题。希望这篇教程能帮助你深入理解Python BST删除的实现细节！

关键词回顾：Python BST删除、二叉搜索树删除操作、Python实现BST删除、数据结构BST删除。