05.数据结构——二叉树

数据结构—二叉树

相关数据结构实现用go语言实现

相关代码做题合集：https://github.com/longpi1/algorithm-pattern

在计算机科学中，树形结构是一种非常重要且直观的数据组织方式，它模拟了自然界中许多分层关系。而二叉树（Binary Tree）是其中最基础、最常用的一种，因其结构简单却能衍生出众多高效的算法和数据结构（如二叉搜索树、堆等），在数据存储、检索、算法优化等领域扮演着核心角色。

本文将深入探讨二叉树的理论基础、常见种类、存储方式、节点定义，以及最关键的遍历顺序，并提供详尽的Go语言实现示例。

一、二叉树理论基础 (Binary Tree Theory)

二叉树是一种特殊的树形数据结构，其最核心的特点是：每个节点最多只有两个子节点，通常称为左子节点（Left Child）和右子节点（Right Child）。

基本概念：

• 节点 (Node)： 二叉树的基本组成单元，包含数据域和指向子节点的指针。
• 根节点 (Root Node)： 树的最顶端节点，没有父节点。
• 父节点 (Parent Node)： 拥有子节点的节点。
• 子节点 (Child Node)： 由父节点派生出的节点。
• 兄弟节点 (Sibling Nodes)： 拥有相同父节点的节点。
• 叶子节点 (Leaf Node / External Node)： 没有子节点的节点。
• 内部节点 (Internal Node)： 至少有一个子节点的节点（非叶子节点）。
• 边 (Edge)： 连接两个节点的线。
• 路径 (Path)： 从一个节点到另一个节点所经过的边的序列。
• 深度 (Depth)： 从根节点到某个节点所经过的边的数量。根节点的深度为0。
• 高度 (Height)： 从某个节点到其最远叶子节点的最长路径上的边数。叶子节点的高度为0。整个树的高度是根节点的高度。
• 层 (Level)： 节点的深度加1。根节点在第1层。
• 子树 (Subtree)： 树中任意一个节点和它的所有后代节点组成的树。

二、二叉树的种类 (Types of Binary Trees)

根据节点分布和结构特性，二叉树可以分为多种类型：

1. 满二叉树 (Full Binary Tree / Strict Binary Tree)：

   • 定义：除了叶子节点外，所有内部节点都有两个子节点。

   • 特点：所有节点度数要么是0（叶子），要么是2（内部节点）。

   • 示例：

         A
        / \
       B   C
      / \ / \
     D  E F  G

2. 完全二叉树 (Complete Binary Tree)：

   • 定义：除了最后一层外，其他所有层都是完全填充的。最后一层从左到右填充，不足的节点都在右侧缺失。

   • 特点：叶子节点只可能出现在最后两层，且最后一层的叶子节点都靠左排列。

   • 示例：

         A
        / \
       B   C
      / \ /
     D  E F

   • 重要性： 堆（Heap）就是一种特殊的完全二叉树，其数组存储效率高。

3. 完美二叉树 (Perfect Binary Tree / Proper Binary Tree)：

   • 定义：满二叉树且所有叶子节点都位于同一层。

   • 特点：节点总数为 2h−12h−1 (h为高度)，每一层都是满的。

   • 示例：

         A
        / \
       B   C
      / \ / \
     D  E F  G

   • 注意： 完美二叉树既是满二叉树也是完全二叉树。

4. 斜树 (Skewed Binary Tree)：

   • 定义：所有节点都只有左子节点（左斜树）或只有右子节点（右斜树）。

   • 特点：失去了二叉树的优点，退化成了链表结构。

   • 示例 (右斜树):

     A
      \
       B
        \
         C
          \
           D

5. 二叉搜索树 (Binary Search Tree - BST)：

   • 定义：一种特殊的二叉树，对于树中的每个节点：

     • 其左子树中所有节点的值都小于该节点的值。
     • 其右子树中所有节点的值都大于该节点的值。
     • 左右子树本身也都是二叉搜索树。

   • 特点：支持高效的查找、插入和删除操作（平均时间复杂度O(logN)）。

   • 示例：

         8
        / \
       3   10
      / \    \
     1   6    14
        / \   /
       4   7 13

   • 自平衡二叉搜索树 (Self-Balancing BST)： 为了防止BST在最坏情况下退化成链表（O(N)），出现了AVL树、红黑树等，它们在插入和删除操作时会自动调整树的结构以保持平衡。

三、二叉树的存储方式 (Storage Methods)

二叉树主要有两种存储方式：

3.1 链式存储 (Linked Representation)

这是最常用、最灵活的存储方式。每个节点是一个独立的对象，包含数据域和指向其左右子节点的指针。

• 优点： 动态分配内存，插入和删除操作灵活方便，不浪费空间（除非树非常稀疏）。
• 缺点： 内存开销相对较大（每个节点需要额外的指针空间），不支持随机访问，只能通过遍历来查找节点，对于完成二叉树，访问节点的时间复杂度可能高于顺序存储。

3.2 顺序存储 (Array Representation)

将二叉树的节点值存储在一个一维数组（或切片）中。通常用于完全二叉树，因为它们结构紧密，可以有效利用数组空间。

• 规则：
  • 根节点存储在数组的 index 0 (或 index 1，取决于约定)。
  • 如果父节点位于index i：
    • 其左子节点位于 2 * i + 1 (如果根节点在 index 0)。
    • 其右子节点位于 2 * i + 2 (如果根节点在 index 0)。
  • 如果子节点位于index j：
    • 其父节点位于 (j - 1) / 2 (整数除法)。
• 优点： 节省空间，适合完全二叉树。内存紧凑，无指针开销，支持随机访问（通过索引直接计算父子关系），利用CPU缓存。
• 缺点： 不适用于稀疏的二叉树也就是非完全二叉树（会浪费大量数组空间），插入和删除操作复杂，可能需要大量的数据移动。

四、二叉树节点定义 (Binary Tree Node Definition - Go)

在Go语言中，我们可以使用结构体（struct）来定义二叉树的节点：

在链式存储中，二叉树的节点通常包含以下部分：

• 数据域：存储节点的值。
• 左子节点指针：指向左子树。
• 右子节点指针：指向右子树。

// TreeNode 定义了二叉树的节点结构
type TreeNode struct {
	Val   int         // 节点的值
	Left  *TreeNode   // 指向左子节点的指针
	Right *TreeNode   // 指向右子节点的指针
}

• Val: 存储节点的数据。这里我们使用 int 类型作为示例，实际应用中可以是任何类型。
• Left, Right: 都是 *TreeNode 类型，表示指向 TreeNode 结构体的指针。如果一个子节点不存在，对应的指针将为 nil。

五、二叉树的遍历顺序 (Binary Tree Traversal Orders)

遍历是访问树中所有节点的一种系统性方法。二叉树主要有两种遍历方式：深度优先遍历（DFS）和广度优先遍历（BFS）。

5.1 深度优先遍历 (Depth-First Search - DFS)

深度优先遍历沿着树的深度方向进行，直到到达叶子节点，然后回溯。根据访问根节点的时机不同，又分为三种：

5.1.1 前序遍历 (Pre-order Traversal)：

• 顺序： 根节点 -> 左子树 -> 右子树
• 应用场景： 复制二叉树、表达式树的前缀表示（波兰式）。
• Go语言实现 (递归)：

// PreorderTraversal 前序遍历
func PreorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	fmt.Printf("%d ", root.Val)     // 访问根节点
	PreorderTraversal(root.Left)  // 递归遍历左子树
	PreorderTraversal(root.Right) // 递归遍历右子树
}

5.1.2 中序遍历 (In-order Traversal)：

• 顺序： 左子树 -> 根节点 -> 右子树
• 应用场景： 对于二叉搜索树（BST），中序遍历会得到一个升序排列的节点值序列；表达式树的中缀表示。
• Go语言实现 (递归)：

// InorderTraversal 中序遍历
func InorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	InorderTraversal(root.Left)   // 递归遍历左子树
	fmt.Printf("%d ", root.Val)     // 访问根节点
	InorderTraversal(root.Right)  // 递归遍历右子树
}

5.1.3 后序遍历 (Post-order Traversal)：

• 顺序： 左子树 -> 右子树 -> 根节点
• 应用场景： 删除二叉树（先删除子节点，再删除父节点）、表达式树的后缀表示（逆波兰式）。
• Go语言实现 (递归)：

// PostorderTraversal 后序遍历
func PostorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	PostorderTraversal(root.Left)   // 递归遍历左子树
	PostorderTraversal(root.Right)  // 递归遍历右子树
	fmt.Printf("%d ", root.Val)     // 访问根节点
}

5.2 广度优先遍历 (Breadth-First Search - BFS) / 层序遍历 (Level Order Traversal)

广度优先遍历是按层级从上到下、从左到右地访问树中的节点。它通常需要借助队列（Queue）来实现。

• 应用场景： 查找最短路径（在无权图中），按层处理节点（如打印每层节点）。
• Go语言实现 (迭代，使用切片模拟队列)：

// LevelOrderTraversal 层序遍历 (广度优先遍历)
func LevelOrderTraversal(root *TreeNode) {
	if root == nil {
		return
	}

	// 使用切片模拟队列，存储待访问的节点
	queue := []*TreeNode{root} // 初始队列包含根节点

	for len(queue) > 0 {
		// 1. 从队列头部取出当前节点
		currNode := queue[0]
		queue = queue[1:] // 移除已访问的节点

		// 2. 访问当前节点
		fmt.Printf("%d ", currNode.Val)

		// 3. 将当前节点的非空子节点加入队列尾部
		if currNode.Left != nil {
			queue = append(queue, currNode.Left)
		}
		if currNode.Right != nil {
			queue = append(queue, currNode.Right)
		}
	}
}

5.3 综合示例 (包括树的构建和所有遍历方式的演示)

package main

import (
	"fmt"
)

// TreeNode 定义了二叉树的节点结构
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 辅助函数：构建一个示例二叉树
// 树结构:
//       1
//      / \
//     2   3
//    / \   \
//   4   5   6
func buildExampleTree() *TreeNode {
	root := &TreeNode{Val: 1}
	root.Left = &TreeNode{Val: 2}
	root.Right = &TreeNode{Val: 3}
	root.Left.Left = &TreeNode{Val: 4}
	root.Left.Right = &TreeNode{Val: 5}
	root.Right.Right = &TreeNode{Val: 6}
	return root
}

// PreorderTraversal 前序遍历 (根-左-右)
func PreorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	fmt.Printf("%d ", root.Val)
	PreorderTraversal(root.Left)
	PreorderTraversal(root.Right)
}

// InorderTraversal 中序遍历 (左-根-右)
func InorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	InorderTraversal(root.Left)
	fmt.Printf("%d ", root.Val)
	InorderTraversal(root.Right)
}

// PostorderTraversal 后序遍历 (左-右-根)
func PostorderTraversal(root *TreeNode) {
	if root == nil {
		return
	}
	PostorderTraversal(root.Left)
	PostorderTraversal(root.Right)
	fmt.Printf("%d ", root.Val)
}

// LevelOrderTraversal 层序遍历 (广度优先遍历)
func LevelOrderTraversal(root *TreeNode) {
	if root == nil {
		return
	}

	queue := []*TreeNode{root} // 使用切片模拟队列
	for len(queue) > 0 {
		currNode := queue[0]
		queue = queue[1:] // 出队

		fmt.Printf("%d ", currNode.Val) // 访问节点

		if currNode.Left != nil {
			queue = append(queue, currNode.Left) // 左子入队
		}
		if currNode.Right != nil {
			queue = append(queue, currNode.Right) // 右子入队
		}
	}
}

func main() {
	fmt.Println("构建示例二叉树...")
	root := buildExampleTree()

	fmt.Print("前序遍历 (Pre-order): ")
	PreorderTraversal(root) // 预期: 1 2 4 5 3 6
	fmt.Println()

	fmt.Print("中序遍历 (In-order):  ")
	InorderTraversal(root) // 预期: 4 2 5 1 3 6
	fmt.Println()

	fmt.Print("后序遍历 (Post-order): ")
	PostorderTraversal(root) // 预期: 4 5 2 6 3 1
	fmt.Println()

	fmt.Print("层序遍历 (Level-order): ")
	LevelOrderTraversal(root) // 预期: 1 2 3 4 5 6
	fmt.Println()
}

输出：

构建示例二叉树...
前序遍历 (Pre-order): 1 2 4 5 3 6 
中序遍历 (In-order):  4 2 5 1 3 6 
后序遍历 (Post-order): 4 5 2 6 3 1 
层序遍历 (Level-order): 1 2 3 4 5 6 

六、总结

二叉树作为一种基础而强大的数据结构，在计算机科学中无处不在。理解其核心概念、不同种类、存储方式以及各种遍历算法，是掌握高级数据结构和算法的基石。Go语言通过其简洁的指针和结构体特性，能够非常直观地实现二叉树的链式存储和各种遍历逻辑。

从文件系统的目录结构到数据库的索引，从编译器中的抽象语法树到各种搜索和排序算法，二叉树及其变种都发挥着至关重要的作用。掌握二叉树，就掌握了处理层级数据的基本能力。

在实际开发中，建议根据具体应用场景选择合适的二叉树类型和遍历方式，并结合性能测试优化算法实现。例如，在需要快速查找的场景中，可以使用二叉搜索树；在需要动态平衡的场景中，可以使用 AVL 树或红黑树。希望本文能帮助读者更好地理解和掌握二叉树这一核心数据结构。