二叉树节点删除方法逻辑修复求助（双节点场景问题）

你当前的二叉树删除逻辑在处理有两个子节点的节点时，核心问题是：仅将待删除节点替换为右子树的最小节点，但没有清理该最小节点在原右子树中的位置，也未正确继承原节点的右子树（该最小节点可能存在右孩子），导致树结构混乱。

修正后的删除方法代码 #

将delete方法移到Tree类中（更符合职责划分），并修正case3的逻辑：

class Tree
  # ... 保留原有方法 ...

  def delete(root, value)
    return root if root.nil?

    if value < root.value
      root.left = delete(root.left, value)
    elsif value > root.value
      root.right = delete(root.right, value)
    else
      # 找到待删除节点
      # case1: 无子女
      if root.left.nil? && root.right.nil?
        root = nil
      # case2: 只有一个子女
      elsif root.left.nil?
        root = root.right
      elsif root.right.nil?
        root = root.left
      # case3: 有两个子女，用右子树最小值节点替换
      else
        # 找到右子树的最小节点
        min_node = min_value(root.right)
        # 继承原节点的左子树
        min_node.left = root.left
        # 关键：删除右子树中的最小节点，并将处理后的右子树赋值给min_node的右指针
        min_node.right = delete(root.right, min_node.value)
        # 用min_node替代原节点
        root = min_node
      end
    end
    root
  end
end

关键修正点说明 #

1. 清理原位置的最小节点：通过递归调用delete(root.right, min_node.value)，移除右子树中的最小节点，避免树中出现重复节点，同时处理该最小节点可能存在的右孩子（最小节点无左孩子，但可能有右孩子）。
2. 正确继承右子树：将处理后的右子树赋值给min_node.right，而非直接保留原root的右子树（原右子树仍包含min_node本身）。
3. 语法修正：移除冗余的else root.value == value判断，前面的分支已覆盖value小于/大于root的情况，else必然是相等的情况。

通用代码优化建议 #

• 明确职责划分：二叉树的操作（删除、查找等）应放在Tree类中，Node仅负责存储节点数据和子节点指针。
• 简化递归逻辑：当前递归写法已足够清晰，保持即可；若追求性能可考虑迭代实现，但递归更易读。
• 修正Tree类构建逻辑：Tree.build_balanced_tree当前创建新Tree实例返回，建议统一逻辑，直接调用Node.build_balanced_tree初始化Tree。
• 添加可选边界提示：删除不存在的节点时，可添加日志提示辅助调试（非必需）。

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