Go语言中理解指针接收器与多级指针更新数据结构

package main

import "fmt"

// Node 定义二叉树节点
type Node struct {
    key         int
    left, right *Node
}

// NewNode 创建新节点
func NewNode(key int) *Node {
    return &Node{key, nil, nil}
}

// BST 定义二叉搜索树
type BST struct {
    root *Node
}

// NewBinarySearchTree 创建新的二叉搜索树
func NewBinarySearchTree() *BST {
    return &BST{nil}
}

// Insert 方法：正确地向BST中插入一个键
func (t *BST) Insert(key int) {
    if t.root == nil {
        t.root = NewNode(key) // 直接更新 t.root
        return
    }
    var node = t.root // node 复制了 t.root 的指针值
    for {
        if key < node.key {
            if node.left == nil {
                node.left = NewNode(key) // 直接更新 node.left
                return
            } else {
                node = node.left // node 复制了 node.left 的指针值
            }
        } else {
            if node.right == nil {
                node.right = NewNode(key) // 直接更新 node.right
                return
            } else {
                node = node.right // node 复制了 node.right 的指针值
            }
        }
    }
}

// inorder 中序遍历打印节点
func inorder(node *Node) {
    if node == nil {
        return
    }
    inorder(node.left)
    fmt.Print(node.key, " ")
    inorder(node.right)
}

func main() {
    tree := NewBinarySearchTree()
    tree.Insert(3)
    tree.Insert(1)
    tree.Insert(2)
    tree.Insert(4)
    fmt.Print("Inorder traversal (Insert): ")
    inorder(tree.root) // 输出: 1 2 3 4
    fmt.Println()
}

// Insert2 方法：错误的插入实现，无法更新树结构
func (t *BST) Insert2(key int) {
    var node *Node
    node = t.root // node 复制了 t.root 的指针值
    for node != nil {
        if key < node.key {
            node = node.left // node 复制了 node.left 的指针值
        } else {
            node = node.right // node 复制了 node.right 的指针值
        }
    }
    node = NewNode(key) // 仅更新局部变量 node，不影响 t.root 或其他节点的子指针
}

// Insert3 方法：使用二级指针正确地插入节点
func (t *BST) Insert3(key int) {
    node := &t.root // node 现在是一个 **Node 类型，指向 t.root 的内存地址
    for *node != nil { // 解引用 node，获取当前 *Node 的值（例如 t.root），检查它是否为 nil
        if key < (*node).key { // 解引用 node，访问其指向的 Node 的 key
            node = &(*node).left // node 现在指向当前节点的 left 指针的内存地址
        } else {
            node = &(*node).right // node 现在指向当前节点的 right 指针的内存地址
        }
    }
    *node = NewNode(key) // 解引用 node，将新节点赋值给它所指向的那个指针（t.root, node.left 或 node.right）
}

func main() {
    tree := NewBinarySearchTree()
    tree.Insert(3)
    tree.Insert(1)
    tree.Insert(2)
    tree.Insert(4)
    fmt.Print("Inorder traversal (Insert): ")
    inorder(tree.root) // 输出: 1 2 3 4
    fmt.Println()

    tree2 := NewBinarySearchTree()
    tree2.Insert2(3)
    tree2.Insert2(1)
    tree2.Insert2(2)
    tree2.Insert2(4)
    fmt.Print("Inorder traversal (Insert2 - Fails): ")
    inorder(tree2.root) // 输出: (空，因为树未更新)
    fmt.Println()

    tree3 := NewBinarySearchTree()
    tree3.Insert3(3)
    tree3.Insert3(1)
    tree3.Insert3(2)
    tree3.Insert3(4)
    fmt.Print("Inorder traversal (Insert3 - Correct): ")
    inorder(tree3.root) // 输出: 1 2 3 4
    fmt.Println()
}