树数据结构与遍历算法详解-尧图网络科技

1. 树的基本概念与核心特性

树（Tree）是计算机科学中最基础且重要的非线性数据结构之一，它模拟了自然界中树的层次结构。在程序设计中，树被广泛用于实现文件系统、数据库索引、编译器语法分析等场景。一棵标准的树由若干个节点（Node）组成，其中：

根节点（Root）：位于树顶层的唯一节点，是整棵树的起点
父节点与子节点：除根节点外，每个节点有且只有一个父节点，但可以有多个子节点
叶子节点（Leaf）：没有子节点的末端节点
边（Edge）：连接两个节点的线段，表示节点间的关联关系

树的几个关键属性决定了它的行为特征：

高度（Height）：从根节点到最远叶子节点的最长路径边数
深度（Depth）：从某节点到根节点的唯一路径边数
度（Degree）：节点拥有的子节点数量
层次（Level）：根节点为第1层，其子节点为第2层，以此类推

实际应用中常使用二叉树（Binary Tree）这种特殊形态，其每个节点最多有两个子节点（左子节点和右子节点）。二叉树又衍生出多种变体，如二叉搜索树、AVL树、红黑树等，它们通过特定的约束条件来优化不同场景下的操作效率。

2. 树的存储结构与实现方式

2.1 链式存储结构

最直观的实现方式是使用节点对象和指针：

typedef struct TreeNode { int data; struct TreeNode *left; struct TreeNode *right; } TreeNode;

这种结构的优势在于：

动态内存分配，灵活处理树形变化
直观反映树的逻辑关系
插入/删除节点时只需修改指针

2.2 顺序存储结构

对于完全二叉树，可以使用数组紧凑存储：

根节点存储在array[0]
对于任意节点array[i]：
- 左子节点为array[2i+1]
- 右子节点为array[2i+2]
- 父节点为array[(i-1)/2]

这种实现节省了指针的存储开销，适合已知最大节点数的场景。

3. 深度优先遍历（DFS）详解

3.1 前序遍历（Pre-order）

遍历顺序：根节点 → 左子树 → 右子树
典型应用：复制树结构、前缀表达式

def preorder(root): if root: print(root.val) # 访问根节点 preorder(root.left) # 递归左子树 preorder(root.right) # 递归右子树

3.2 中序遍历（In-order）

遍历顺序：左子树 → 根节点 → 右子树
二叉搜索树的中序遍历会产生有序序列

def inorder(root): if root: inorder(root.left) # 递归左子树 print(root.val) # 访问根节点 inorder(root.right) # 递归右子树

3.3 后序遍历（Post-order）

遍历顺序：左子树 → 右子树 → 根节点
典型应用：释放树内存、后缀表达式计算

def postorder(root): if root: postorder(root.left) # 递归左子树 postorder(root.right) # 递归右子树 print(root.val) # 访问根节点

非递归实现通常借助栈结构。以前序遍历为例：

def preorder_iterative(root): stack = [root] while stack: node = stack.pop() if node: print(node.val) stack.append(node.right) # 右子节点先入栈 stack.append(node.left) # 左子节点后入栈

4. 广度优先遍历（BFS）实现

广度优先遍历按层次访问节点，需要借助队列实现：

from collections import deque def level_order(root): if not root: return queue = deque([root]) while queue: node = queue.popleft() print(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right)

实际工程中的几个优化技巧：

批量处理层级：记录每层节点数，实现分层输出
双向队列：使用deque替代list提升出队效率
内存预分配：预估最大宽度可减少动态扩容开销

5. 遍历算法的应用场景对比

遍历方式	时间复杂度	空间复杂度	典型应用场景
递归DFS	O(n)	O(h)	简单实现、小规模数据
迭代DFS	O(n)	O(h)	避免栈溢出、大规模数据
BFS	O(n)	O(w)	最短路径、层次关系分析
Morris遍历	O(n)	O(1)	严格空间限制环境