如何使用Golang指针和结构体组合实现树结构_节点操作

Go中树结构用指针型结构体实现，如type TreeNode struct{Val int; Left TreeNode; Right TreeNode}，通过&取地址构造节点并建立父子连接，方法接收者需为*TreeNode以支持修改。

用 Go 实现树结构，核心是用结构体定义节点，用指针实现父子连接。Go 没有类和继承，但通过嵌入、指针和方法接收者，能自然表达树的层级关系和操作逻辑。

定义基础树节点结构体

一个通用二叉树节点通常包含值、左子节点和右子节点三个字段。所有字段都用指针类型，便于动态链接和空值表示（nil）：

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

注意：Left 和 Right 是 *TreeNode 类型（指向节点的指针），不是 TreeNode 值类型。这样既能避免无限嵌套（值类型会导致编译错误），又能支持空子树（nil 表示无子节点）。

构造节点与建立父子关系

用字面量或工厂函数创建节点，并通过指针赋值建立连接：

• 直接初始化：root := &TreeNode{Val: 10}
• 设置子节点：root.Left = &TreeNode{Val: 5}；root.Right = &TreeNode{Val: 15}
• 也可封装为构造函数，提升可读性：

  func NewNode(val int) *TreeNode {
      return &TreeNode{Val: val}
  }

关键点：始终用 & 取地址，确保你操作的是堆上分配的、可被多个父节点引用的对象。

为结构体绑定常用操作方法

给 TreeNode 添加方法，比如插入、查找、遍历。接收者必须是指针类型（*TreeNode），才能修改节点自身或其子节点指针：

// 插入值到二叉搜索树
func (n *TreeNode) Insert(val int) {
    if n == nil {
        return // 空节点不能插入，应由父节点调用
    }
    if val < n.Val {
        if n.Left == nil {
            n.Left = &TreeNode{Val: val}
        } else {
            n.Left.Insert(val)
        }
    } else {
        if n.Right == nil {
            n.Right = &TreeNode{Val: val}
        } else {
            n.Right.Insert(val)
        }
    }
}

说明：
- 方法内可安全修改 n.Left 或 n.Right 的指针值；
- 递归调用时传的是子节点指针（如 n.Left），符合接收者类型；
- 初始调用需确保 n 非 nil（建议封装在树容器中统一处理）。

用树容器封装管理逻辑（推荐实践）

单独的节点结构体缺乏根管理和边界控制。建议额外定义 Tree 结构体，持有根节点指针，并提供顶层操作：

type Tree struct {
    Root *TreeNode
}
func (t *Tree) Insert(val int) {
if t.Root == nil {
t.Root = &TreeNode{Val: val}
} else {
t.Root.Insert(val) // 复用上面的方法
}
}
func (t Tree) Inorder() []int {
var result []int
var inorder func(TreeNode)
inorder = func(n *TreeNode) {
if n == nil {
return
}
inorder(n.Left)
result = append(result, n.Val)
inorder(n.Right)
}
inorder(t.Root)
return result
}

好处：
- 根节点生命周期由 Tree 控制，不易丢失；
- 所有操作入口统一，避免裸指针误用；
- 支持扩展字段（如节点数、是否平衡等元信息）。