树（一）：从线性到非线性的跨越
说实话，学数据结构这么久，前面链表、栈、队列都是线性结构。说白了就是一根绳子串到底。但现实世界哪有这么简单？你想想看，公司的组织架构、文件系统的目录、甚至你电脑里的文件夹，哪个不是分叉的？
这就是树结构存在的意义。我个人习惯把树叫做“有层次感的链表”。它解决了线性结构无法表达“一对多”关系的问题。
树的基本概念
树是一种非线性的数据结构。它由节点和边组成。每个节点可以有多个子节点，但只有一个父节点（根节点除外）。
几个关键术语你得记住：
- 根节点：没有父节点的节点，一棵树只有一个根
- 叶子节点：没有子节点的节点
- 度：一个节点拥有的子节点数量
- 深度：从根节点到该节点的路径长度
- 高度：从该节点到最远叶子节点的路径长度
核心要点：树的定义是递归的。每个子树本身也是一棵树。这个递归思想在后面遍历时会反复用到。
我在项目中遇到过一个问题：用链表存储组织架构，结果查找某个部门的所有下属部门时，需要遍历整个链表。换成树结构后，直接递归遍历子树就搞定了。性能提升不是一星半点。
二叉树定义与性质
二叉树是树中最常见的一种。每个节点最多有两个子节点，分别叫左孩子和右孩子。你想想看，为什么是“最多两个”？因为计算机底层很多操作都是二元的，比如比较大小、真假判断。
二叉树有几个重要性质：
- 第 i 层最多有 2^(i-1) 个节点（i≥1）
- 深度为 k 的二叉树最多有 2^k - 1 个节点
- 叶子节点数 = 度为2的节点数 + 1
我的经验：这些性质看起来是数学公式，但在计算内存占用、判断树是否平衡时非常实用。我曾经用这些公式估算过一棵满二叉树需要多少内存，避免了内存溢出的坑。
二叉树的存储结构
二叉树的存储有两种方式：顺序存储和链式存储。
顺序存储
用数组来存。根节点放在下标1（或0），左孩子在下标2i，右孩子在下标2i+1。这种方式适合完全二叉树，但普通二叉树会浪费大量空间。
// 顺序存储示例
int tree[100]; // tree[1] 是根节点
// tree[2] 是左孩子，tree[3] 是右孩子链式存储
每个节点包含数据域和两个指针域。这是最常用的方式。
typedef struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;注意：链式存储时，一定要记得初始化左右指针为NULL。我曾经因为忘记初始化，导致遍历时访问了野指针，程序直接崩溃。排查了半天才发现是这个问题。
二叉树的遍历
遍历是二叉树最核心的操作。说白了就是按照某种顺序访问每个节点一次。一共有四种遍历方式。
前序遍历（根左右）
先访问根节点，再遍历左子树，最后遍历右子树。
void preOrder(TreeNode *root) {
if (root == NULL) return;
printf("%d ", root->data); // 访问根
preOrder(root->left); // 遍历左子树
preOrder(root->right); // 遍历右子树
}中序遍历（左根右）
先遍历左子树，再访问根节点，最后遍历右子树。对于二叉搜索树，中序遍历得到的是有序序列。
void inOrder(TreeNode *root) {
if (root == NULL) return;
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}后序遍历（左右根）
先遍历左子树，再遍历右子树，最后访问根节点。常用于删除树或计算表达式。
void postOrder(TreeNode *root) {
if (root == NULL) return;
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}层序遍历
从上到下，从左到右，一层一层地访问。需要借助队列来实现。
void levelOrder(TreeNode *root) {
if (root == NULL) return;
Queue q;
initQueue(&q);
enqueue(&q, root);
while (!isEmpty(&q)) {
TreeNode *node = dequeue(&q);
printf("%d ", node->data);
if (node->left) enqueue(&q, node->left);
if (node->right) enqueue(&q, node->right);
}
}避坑指南：我曾经在层序遍历时忘记判断左右孩子是否为NULL，结果把NULL节点也入队了。循环直接死掉。记住：入队前一定要判空。
四种遍历对比
| 遍历方式 | 访问顺序 | 典型应用 |
|---|---|---|
| 前序 | 根 → 左 → 右 | 复制树、序列化 |
| 中序 | 左 → 根 → 右 | 二叉搜索树排序 |
| 后序 | 左 → 右 → 根 | 删除树、表达式求值 |
| 层序 | 逐层从左到右 | 求树宽度、最短路径 |
本章知识体系
下面这张图帮你理清本章的核心脉络。我建议你把它保存下来，复习时对照着看。
个人建议：学树的时候，一定要动手画图。我当年学二叉树时，每道题都先在纸上画出树结构，然后用手模拟遍历过程。画上几十棵树，你自然就懂了。
嗯，树的内容就讲到这里。记住：树是递归的，遍历是递归的，存储也是递归的。把这个递归思想吃透了，后面的图、堆、红黑树都会轻松很多。