第九章 树与二叉树：从混乱到有序
说实话，我刚开始学数据结构时，最头疼的就是树。链表好歹是线性的，顺着走就行。树呢？分叉、递归、遍历……脑子容易绕进去。但后来做项目多了，才发现树结构无处不在——文件系统、编译器语法树、网络路由表，甚至你手机里的联系人分组，本质上都是树。
这一章，我们就来把树和二叉树彻底讲透。我会结合我实际踩过的坑，帮你少走弯路。
9.1 树的基本概念
树是一种非线性的数据结构。它由节点和边组成，有一个根节点，其他节点往下分叉，不能形成环。
我个人习惯用「家谱」来理解树：
- 根节点：老祖宗，唯一没有父节点的节点
- 叶子节点：没有孩子的节点，相当于家族里的末代
- 父节点/子节点：上下级关系
- 兄弟节点：同一个父节点的孩子
- 深度：从根到某个节点的层数（根深度为0或1，看约定）
- 度：一个节点拥有的子树个数
9.2 二叉树性质
二叉树是每个节点最多有两个子树的树结构。说白了，就是每个节点最多生两个娃，左娃和右娃。
几个重要性质，我建议你背下来，面试常考：
| 性质 | 描述 |
|---|---|
| 性质1 | 第 i 层最多有 2^(i-1) 个节点（i≥1） |
| 性质2 | 深度为 k 的二叉树最多有 2^k - 1 个节点 |
| 性质3 | 叶子节点数 = 度为2的节点数 + 1 |
| 性质4 | 完全二叉树可以用数组顺序存储 |
嗯，这里要注意：性质3在笔试中经常用来推导节点数量。我曾经在面试时被问到「已知二叉树有100个叶子节点，问度为2的节点有多少个？」——答案就是99个。
9.3 二叉树的存储结构
存储二叉树，主流有两种方式：
9.3.1 顺序存储（数组）
适合完全二叉树。根节点放下标1，左孩子放2i，右孩子放2i+1。浪费空间？是的，如果是斜树，数组会空一大半。
// 顺序存储示例
#define MAXSIZE 100
int tree[MAXSIZE]; // tree[1] 为根节点
// 访问左孩子：tree[2*i]
// 访问右孩子：tree[2*i+1]9.3.2 链式存储（指针）
最常用。每个节点包含数据域、左指针、右指针。我项目中99%的情况都用这种。
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 创建节点
TreeNode* createNode(int val) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = val;
node->left = NULL;
node->right = NULL;
return node;
}9.4 二叉树的遍历
遍历是二叉树最核心的操作。你想想看，树结构没法像数组那样直接循环，必须用递归或栈来模拟。
四种遍历方式，我按「根的位置」来记：
9.4.1 前序遍历（根左右）
先访问根，再左子树，最后右子树。常用于复制一棵树。
void preOrder(TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->data); // 访问根
preOrder(root->left); // 遍历左
preOrder(root->right); // 遍历右
}9.4.2 中序遍历（左根右）
先左子树，再根，最后右子树。对二叉搜索树做中序遍历，得到的就是有序序列。
void inOrder(TreeNode* root) {
if (root == NULL) return;
inOrder(root->left);
printf("%d ", root->data);
inOrder(root->right);
}9.4.3 后序遍历（左右根）
先左子树，再右子树，最后根。常用于删除树——先删孩子，再删自己。
void postOrder(TreeNode* root) {
if (root == NULL) return;
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}9.4.4 层序遍历（广度优先）
从上到下，从左到右，一层一层走。需要借助队列实现。
void levelOrder(TreeNode* root) {
if (root == NULL) return;
Queue* q = createQueue();
enqueue(q, root);
while (!isEmpty(q)) {
TreeNode* cur = dequeue(q);
printf("%d ", cur->data);
if (cur->left) enqueue(q, cur->left);
if (cur->right) enqueue(q, cur->right);
}
}为什么递归能搞定遍历？因为树本身就是递归定义的——每个子树又是一棵树。你只要写好「当前节点做什么」，剩下的交给递归。
我个人习惯在写递归遍历时，先画一棵小树，手动走一遍流程。代码写完后，用这棵小树验证。这个方法帮我抓出过不少逻辑错误。
好了，树和二叉树的核心内容就这些。概念、性质、存储、遍历——四块拼图拼起来，你就能应对绝大多数场景了。代码多写几遍，尤其是递归遍历，写到形成肌肉记忆为止。