Python实现BST删除函数出现意外额外删除问题排查

问题场景 #

构造BST t = BinaryTree([100, 50, 200, 25, 75, 350]) 后，执行删除根节点100的操作，发现节点350被意外删除。存在问题的删除函数代码如下：

def delete(node, key):
  if not node: return None 

  # Wrong node, search correct child
  if key < node.data:
    delete(node.left, key)
  elif key > node.data:
    delete(node.right, key)

  # Correct node found
  else: 
    #1. node has no children 
    if not (node.left and node.right): return None
    #2. node has only left child 
    if node.left and not node.right: return node.left
    #3. node has only right child
    if not node.left and node.right: return node.right
    
    #4. node has both left & right children
      ## Need to replace current value with next biggest value
      ## So go right once then all left to end
      ## Once this value is found, assign to appropriate position
      ## Then remove this val from its previous position 
    temp = node.right 
    while temp.left: temp = temp.left 
    node.data = temp.data 
    node.right = delete(node.right, temp.data) 

Bug原因分析 #

1. 递归结果未赋值：搜索目标节点时，调用delete(node.left, key)和delete(node.right, key)后，没有将返回的新子树赋值回node.left或node.right，导致子树的修改无法被上层节点感知，最终丢失部分节点。
2. 无子女节点判断错误：if not (node.left and node.right): return None 会把只有一个子女的节点误判为无子女（只要左/右任意一个为空，node.left and node.right就为False），导致后续单子女分支逻辑永远不会执行，直接返回None删除整个子树。

修复后的代码 #

def delete(node, key):
    if not node:
        return None

    # 搜索目标节点，将递归结果赋值回父节点指针
    if key < node.data:
        node.left = delete(node.left, key)
    elif key > node.data:
        node.right = delete(node.right, key)
    else:
        # 1. 叶子节点（无子女）
        if not node.left and not node.right:
            return None
        # 2. 只有左子女
        elif not node.right:
            return node.left
        # 3. 只有右子女
        elif not node.left:
            return node.right
        # 4. 有左右两个子女，找右子树最小节点替换
        temp = node.right
        while temp.left:
            temp = temp.left
        node.data = temp.data
        node.right = delete(node.right, temp.data)
    
    return node

关键修改点 #

• 搜索阶段：新增node.left = 和node.right = ，将递归修改后的子树赋值回原节点指针，确保修改生效。
• 无子女判断：改为if not node.left and not node.right，仅当左右子女都为空时才判定为叶子节点，避免误判单子女节点。
• 单子女分支优化：简化为elif逻辑，减少冗余判断。

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