golang-cookbook

Appearance

tree ​

在 Go 中，树是一种常见的层级数据结构，通常用于表示具有父子关系的数据。树形结构有许多不同的变体，常见的有二叉树、平衡树、B+ 树、堆等。在 Go 中实现树结构通常需要递归和结构体。

树的基础知识 ​

树是由节点组成的，每个节点包含数据以及指向其子节点的指针。树的主要特点包括：

  • 根节点：树的顶部节点，唯一一个没有父节点的节点。
  • 叶节点：没有子节点的节点。
  • 子节点：直接由父节点连接的节点。
  • 深度：节点到根节点的路径长度。
  • 高度：树中最长路径的长度。

1. 二叉树 ​

二叉树是最常见的树形数据结构。每个节点最多有两个子节点，通常称为左子节点和右子节点。

1.1 二叉树节点定义 ​

go
package main

import "fmt"

// 定义二叉树节点
type TreeNode struct {
	Value int
	Left  *TreeNode
	Right *TreeNode
}

// 插入节点
func insert(root *TreeNode, value int) *TreeNode {
	if root == nil {
		return &TreeNode{Value: value}
	}

	if value < root.Value {
		root.Left = insert(root.Left, value)
	} else {
		root.Right = insert(root.Right, value)
	}
	return root
}

// 中序遍历（递归）
func inorder(root *TreeNode) {
	if root != nil {
		inorder(root.Left)
		fmt.Print(root.Value, " ")
		inorder(root.Right)
	}
}

// 查找节点
func search(root *TreeNode, value int) *TreeNode {
	if root == nil || root.Value == value {
		return root
	}

	if value < root.Value {
		return search(root.Left, value)
	}
	return search(root.Right, value)
}

func main() {
	// 创建根节点并插入其他节点
	var root *TreeNode
	root = insert(root, 5)
	root = insert(root, 3)
	root = insert(root, 7)
	root = insert(root, 4)
	root = insert(root, 6)

	// 中序遍历
	inorder(root) // 输出: 3 4 5 6 7
	fmt.Println()

	// 查找节点
	node := search(root, 4)
	if node != nil {
		fmt.Println("Found:", node.Value) // 输出: Found: 4
	} else {
		fmt.Println("Not Found")
	}
}

1.2 二叉树的遍历方式 ​

  • 中序遍历：左 -> 根 -> 右
  • 前序遍历：根 -> 左 -> 右
  • 后序遍历：左 -> 右 -> 根

2. 平衡二叉搜索树（AVL 树） ​

AVL 树是一种自平衡的二叉搜索树，插入和删除操作会根据节点的平衡因子来进行旋转操作，以确保树的高度保持在对数级别，从而保证查找的效率。

2.1 AVL 树的节点结构 ​

go
package main

import "fmt"

// AVL 树的节点
type AVLNode struct {
	Value  int
	Height int
	Left   *AVLNode
	Right  *AVLNode
}

// 获取树的高度
func height(node *AVLNode) int {
	if node == nil {
		return 0
	}
	return node.Height
}

// 计算平衡因子
func balanceFactor(node *AVLNode) int {
	return height(node.Left) - height(node.Right)
}

// 右旋转
func rightRotate(y *AVLNode) *AVLNode {
	x := y.Left
	T := x.Right

	// 旋转
	x.Right = y
	y.Left = T

	// 更新高度
	y.Height = max(height(y.Left), height(y.Right)) + 1
	x.Height = max(height(x.Left), height(x.Right)) + 1

	return x
}

// 左旋转
func leftRotate(x *AVLNode) *AVLNode {
	y := x.Right
	T := y.Left

	// 旋转
	y.Left = x
	x.Right = T

	// 更新高度
	x.Height = max(height(x.Left), height(x.Right)) + 1
	y.Height = max(height(y.Left), height(y.Right)) + 1

	return y
}

// 获取较大值
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 插入节点并保持平衡
func insertAVL(root *AVLNode, value int) *AVLNode {
	if root == nil {
		return &AVLNode{Value: value, Height: 1}
	}

	if value < root.Value {
		root.Left = insertAVL(root.Left, value)
	} else if value > root.Value {
		root.Right = insertAVL(root.Right, value)
	} else {
		return root // 重复元素不插入
	}

	// 更新节点高度
	root.Height = 1 + max(height(root.Left), height(root.Right))

	// 平衡树
	bf := balanceFactor(root)
	if bf > 1 && value < root.Left.Value {
		return rightRotate(root)
	}
	if bf < -1 && value > root.Right.Value {
		return leftRotate(root)
	}
	if bf > 1 && value > root.Left.Value {
		root.Left = leftRotate(root.Left)
		return rightRotate(root)
	}
	if bf < -1 && value < root.Right.Value {
		root.Right = rightRotate(root.Right)
		return leftRotate(root)
	}

	return root
}

// 中序遍历
func inorderAVL(root *AVLNode) {
	if root != nil {
		inorderAVL(root.Left)
		fmt.Print(root.Value, " ")
		inorderAVL(root.Right)
	}
}

func main() {
	var root *AVLNode
	root = insertAVL(root, 10)
	root = insertAVL(root, 20)
	root = insertAVL(root, 30)
	root = insertAVL(root, 5)
	root = insertAVL(root, 15)

	inorderAVL(root) // 输出: 5 10 15 20 30
}

3. 堆（Heap） ​

堆是一种特殊的完全二叉树，常用来实现优先队列。最常见的堆是 最大堆（父节点的值大于子节点的值）和 最小堆（父节点的值小于子节点的值）。

3.1 最小堆实现 ​

go
package main

import "fmt"

// 最小堆
type MinHeap struct {
	arr []int
}

// 插入元素到最小堆
func (h *MinHeap) Insert(val int) {
	h.arr = append(h.arr, val)
	h.heapifyUp(len(h.arr) - 1)
}

// 上浮操作，维护堆的性质
func (h *MinHeap) heapifyUp(index int) {
	for h.arr[index] < h.arr[parent(index)] {
		h.arr[index], h.arr[parent(index)] = h.arr[parent(index)], h.arr[index]
		index = parent(index)
	}
}

// 返回父节点的索引
func parent(i int) int {
	return (i - 1) / 2
}

// 删除最小值（堆顶）
func (h *MinHeap) ExtractMin() int {
	if len(h.arr) == 0 {
		return -1 // 堆为空
	}
	min := h.arr[0]
	h.arr[0] = h.arr[len(h.arr)-1]
	h.arr = h.arr[:len(h.arr)-1]
	h.heapifyDown(0)
	return min
}

// 下沉操作，维护堆的性质
func (h *MinHeap) heapifyDown(index int) {
	leftChild := left(index)
	rightChild := right(index)

	smallest := index
	if leftChild < len(h.arr) && h.arr[leftChild] < h.arr[smallest] {
		smallest = leftChild
	}
	if rightChild < len(h.arr) && h.arr[rightChild] < h.arr[smallest] {
		smallest = rightChild
	}

	if smallest != index {
		h.arr[index], h.arr[smallest] = h.arr[smallest], h.arr[index]
		h.heapifyDown(smallest)
	}
}

// 获取左子节点的索引
func left(i int) int {
	return 2*i + 1
}

// 获取右子节点的索引
func right(i int) int {
	return 2*i + 2
}

func main() {
	heap := &MinHeap{}
	heap.Insert(10)
	heap.Insert(5)
	heap.Insert(3)
	heap.Insert(8)

	fmt.Println(heap.ExtractMin()) // 输出: 3
	fmt.Println(heap.ExtractMin()) // 输出: 5
}

4. N叉树 ​

N叉树是每个节点可以有多个子节点的树形结构。通常用于表示层级关系更复杂的数据，如文件系统或组织结构。

4.1 N叉树的节点定义 ​

go
package main

import "fmt"

// N叉树的节点结构
type NTreeNode struct

 {
	Value    int
	Children []*NTreeNode
}

// 创建一个节点
func NewNTreeNode(value int) *NTreeNode {
	return &NTreeNode{Value: value}
}

// 添加子节点
func (node *NTreeNode) AddChild(child *NTreeNode) {
	node.Children = append(node.Children, child)
}

// 打印N叉树
func printNTree(node *NTreeNode, level int) {
	if node == nil {
		return
	}

	// 打印当前节点
	for i := 0; i < level; i++ {
		fmt.Print("--")
	}
	fmt.Println(node.Value)

	// 打印子节点
	for _, child := range node.Children {
		printNTree(child, level+1)
	}
}

func main() {
	// 创建根节点和子节点
	root := NewNTreeNode(1)
	child1 := NewNTreeNode(2)
	child2 := NewNTreeNode(3)
	child3 := NewNTreeNode(4)

	// 添加子节点
	root.AddChild(child1)
	root.AddChild(child2)
	root.AddChild(child3)

	// 打印N叉树
	printNTree(root, 0)
}

总结 ​

在 Go 中，树结构可以根据需求设计成不同类型的变体，如二叉树、AVL 树、堆和 N叉树等。每种树形结构都有特定的用途和操作方法，例如搜索、插入、删除、遍历等。通过使用 Go 的结构体和递归，我们可以很容易地实现这些树形数据结构。