Go语言指针接收器未按预期更新：二叉搜索树节点删除失败求助

问题场景 #

我在实现Go语言的BST节点删除功能时，算法逻辑看起来没问题，但实际运行后树结构完全没变化。测试删除节点3后，中序遍历结果和删除前一致。

BST定义 #

type Node struct {
    Data  int
    Left  *Node
    Right *Node
}

已测试通过的辅助方法 #

// New 返回新节点的指针（类似Go中的new构造）
func New(data int) *Node {
    return &Node{Data: data}
}

// Find 检查数据是否存在于BST中并返回对应节点
func (bst *Node) Find(data int) *Node {
    if bst == nil {
        return bst
    }
    if bst.Data == data {
        return bst
    }
    if data < bst.Data {
        return bst.Left.Find(data)
    }
    return bst.Right.Find(data)
}

// Min 返回BST中的最小元素节点
func (bst *Node) Min() *Node {
    if bst == nil {
        return nil
    }
    current := bst
    for current.Left != nil {
        current = current.Left
    }
    return current
}

存在问题的Delete方法 #

// Delete 从二叉树中删除指定键值的节点
func (bst *Node) Delete(data int) *Node {
    if bst == nil {
        return bst
    }
    current := bst
    toDelete := current.Find(data)
    if toDelete == nil {
        return current
    }
    if toDelete.Right == nil && toDelete.Left != nil {
        toDelete = toDelete.Left
        return current
    }
    if toDelete.Right != nil && toDelete.Left == nil {
        toDelete = toDelete.Right
        return current
    }
    inOrderSuccessor := toDelete.Right.Min()
    toDelete = inOrderSuccessor
    return current
}

测试代码与输出 #

func main() {
    root := bst.New(8)
    root.Left = bst.New(3)
    root.Right = bst.New(10)
    root.Left.Left = bst.New(1)
    root.Left.Right = bst.New(6)
    fmt.Println(root.InOrder())
    root = root.Delete(3)
    fmt.Println(root.InOrder())
}

输出：

1->3->6->8->10->
1->3->6->8->10->

问题核心分析 #

你的Delete方法存在致命错误：所有节点替换操作都只是修改了局部变量toDelete的指针指向，并没有修改二叉树中父节点的Left/Right引用。

比如执行toDelete = toDelete.Left时，只是把函数内的toDelete变量指向了左子节点，但原来的父节点（比如root.Left，也就是指向节点3的指针）仍然指向原节点，树的结构根本没被修改。

另外，处理双生子节点的情况时，仅把toDelete指向中序后继节点，既没有将后继节点的值赋给待删除节点，也没有清理后继节点在原位置的引用，完全不符合BST删除的逻辑。

修复后的Delete实现 #

正确的做法是通过递归遍历，在找到待删除节点时，返回新的子树节点让父节点的Left/Right引用更新，或直接修改当前节点值并删除后继节点：

// Delete 从二叉树中删除指定键值的节点
func (bst *Node) Delete(data int) *Node {
    if bst == nil {
        return nil
    }

    // 递归查找待删除节点，同步更新父节点的子树引用
    if data < bst.Data {
        bst.Left = bst.Left.Delete(data)
        return bst
    } else if data > bst.Data {
        bst.Right = bst.Right.Delete(data)
        return bst
    }

    // 当前节点即为待删除节点
    // 情况1：仅右子节点或为叶子节点
    if bst.Left == nil {
        return bst.Right
    }
    // 情况2：仅左子节点
    if bst.Right == nil {
        return bst.Left
    }

    // 情况3：左右子节点均存在，找到中序后继（右子树最小节点）
    minNode := bst.Right.Min()
    // 将后继节点的值赋给当前节点
    bst.Data = minNode.Data
    // 递归删除后继节点（此时后继节点必然是叶子或仅右子节点）
    bst.Right = bst.Right.Delete(minNode.Data)
    return bst
}

修复逻辑说明 #

1. 递归遍历树时，同步更新当前节点的Left/Right引用，确保父节点能指向删除后的子树结构。
2. 找到待删除节点时：
   • 若只有单个子节点，直接返回该子节点，让父节点的引用指向它，等价于删除当前节点。
   • 若有双子节点，通过中序后继节点的值覆盖当前节点，再递归删除后继节点，既保证BST性质，又完成删除操作。

修复后运行测试代码，删除节点3的中序遍历结果会变为1->6->8->10->，符合预期。

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