Go语言二叉树的删除操作详解（手把手教你实现二叉搜索树节点删除）

删除操作的三种情况

在Go实现二叉树时，删除一个节点需要考虑以下三种情况：

1. 叶子节点（无子节点）：直接删除即可。
2. 只有一个子节点：用其子节点替代它。
3. 有两个子节点：找到右子树中的最小值（或左子树中的最大值）作为后继节点，用后继节点的值替换当前节点，再删除后继节点。

Go语言实现代码

下面是一个完整的数据结构教程级实现，包含节点定义和删除函数：

package mainimport "fmt"type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}func deleteNode(root *TreeNode, key int) *TreeNode {    // 情况1：根为空，直接返回    if root == nil {        return nil    }    if key < root.Val {        root.Left = deleteNode(root.Left, key)    } else if key > root.Val {        root.Right = deleteNode(root.Right, key)    } else {        // 找到要删除的节点        // 情况2：没有左子树        if root.Left == nil {            return root.Right        }        // 情况3：没有右子树        if root.Right == nil {            return root.Left        }        // 情况4：有两个子树        // 找到右子树的最小节点（中序后继）        minNode := findMin(root.Right)        root.Val = minNode.Val        // 删除右子树中的最小节点        root.Right = deleteNode(root.Right, minNode.Val)    }    return root}func findMin(node *TreeNode) *TreeNode {    for node.Left != nil {        node = node.Left    }    return node}func inorderTraversal(root *TreeNode) {    if root != nil {        inorderTraversal(root.Left)        fmt.Print(root.Val, " ")        inorderTraversal(root.Right)    }}func main() {    // 构建测试树:       5    //                /   \    //               3     6    //              / \     \    //             2   4     7    root := &TreeNode{Val: 5}    root.Left = &TreeNode{Val: 3}    root.Right = &TreeNode{Val: 6}    root.Left.Left = &TreeNode{Val: 2}    root.Left.Right = &TreeNode{Val: 4}    root.Right.Right = &TreeNode{Val: 7}    fmt.Print("删除前中序遍历: ")    inorderTraversal(root)    fmt.Println()    root = deleteNode(root, 3)    fmt.Print("删除节点3后中序遍历: ")    inorderTraversal(root)    fmt.Println()}

代码解析

deleteNode 函数采用递归方式实现：

• 首先通过比较 key 与当前节点值，决定向左或向右递归。
• 当找到目标节点后，处理三种删除情况。
• 对于有两个子节点的情况，调用 findMin 找到右子树最小值，并递归删除该最小节点。

运行结果

执行上述代码，输出如下：

删除前中序遍历: 2 3 4 5 6 7 删除节点3后中序遍历: 2 4 5 6 7

小结

通过本教程，你已经掌握了在 Go 语言中实现Go语言二叉树删除的核心逻辑。记住，关键在于正确处理三种删除场景，并保持二叉搜索树的性质不变。多加练习，你就能熟练运用这一重要数据结构教程中的经典操作！

继续深入学习 Go 语言与数据结构，构建更强大的程序吧！