解析二叉搜索树中含两个子节点的节点删除：_delete_recursive函数

首先明确：你当前的_delete_recursive函数没有实现双子女节点的删除逻辑——当待删节点同时存在左右子节点时，代码里的三个条件（无子女、仅左子女、仅右子女）都不满足，会直接跳过处理返回原节点，等于没执行删除操作。

双子女节点删除的核心逻辑 #

二叉搜索树中，删除同时有左右子节点的节点时，必须保证删除后树的BST性质不变，标准做法是：

• 选择后继节点（待删节点右子树中值最小的节点，即右子树的最左节点），或者前驱节点（待删节点左子树中值最大的节点，即左子树的最右节点）
• 用后继/前驱节点的值覆盖待删节点的值
• 递归删除那个后继/前驱节点（因为这类节点最多只有一个子节点，你的现有代码已经能处理这种情况）

分步实现（以后继节点为例） #

1. 新增找后继节点的辅助逻辑 #

在binary类中添加一个辅助函数，用于定位后继节点：

def _find_min(self, node):
    # 找到右子树的最左节点（即右子树的最小值节点）
    current = node
    while current.left is not None:
        current = current.left
    return current

2. 修改_delete_recursive函数的待删分支 #

补全双子女节点的处理逻辑，替换原函数的对应部分：

def _delete_recursive(self, value, node):
    if node is None:
        return node
    if value < node.value:
        node.left  = self._delete_recursive(value,node.left)
    elif value > node.value:
        node.right  = self._delete_recursive(value,node.right)
    else:
        # 无子女节点
        if node.left is None and node.right is None :
            return None
        # 仅左子女
        elif node.right is None:
            return node.left
        # 仅右子女
        elif node.left is None:
            return node.right
        # 同时有左右子女的情况（新增核心逻辑）
        else:
            # 1. 找到待删节点的后继节点（右子树最小值）
            successor = self._find_min(node.right)
            # 2. 用后继节点的值覆盖待删节点的值
            node.value = successor.value
            # 3. 递归删除后继节点（后继节点最多只有右子节点，现有逻辑可处理）
            node.right = self._delete_recursive(successor.value, node.right)
    return node

3. 分步执行流程（以双子女节点为例） #

假设待删节点是N，同时有左子树L和右子树R：

• 第一步：定位到R的最左节点S（后继节点），S的左子节点一定为空，因此S要么无子女，要么只有右子节点
• 第二步：将N的value替换为S的value，此时N的位置完全符合BST的大小规则
• 第三步：递归删除R中的S节点，由于S最多只有右子节点，原有代码会直接用S的右子节点替换它的位置，完成整个删除操作

测试验证 #

构造一个含双子女节点的树进行测试：

tree = binary()
tree.insert(10)
tree.insert(5)
tree.insert(15)
tree.insert(3)
tree.insert(7)
tree.insert(12)
tree.insert(18)
# 删除10（同时有左右子节点）
tree.delete(10)
tree.trans()
# 输出结果：----- 3 ----- 5 ----- 7 ----- 12 ----- 15 ----- 18 

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