树与二叉树基础
说实话，很多初学者一听到「树」这个数据结构，脑子里就浮现出家里那棵歪脖子树。其实编程里的树，更像是一个倒挂的家族谱——根在上，枝叶在下。我当年刚接触时也绕了好一阵子，后来发现，只要抓住几个核心概念，树其实比链表还直观。
树的定义与术语
树是一种非线性的数据结构。它由 n（n≥0）个节点组成，节点之间有明确的层次关系。如果 n=0，我们叫它空树。
来看几个关键术语，这些你在面试和项目中都会频繁碰到：
- 根节点：树的最顶层节点，一棵树只有一个根。就像公司的CEO，所有人都向他汇报。
- 父节点与子节点：如果节点 A 指向节点 B，A 就是父节点，B 就是子节点。注意，一个父节点可以有多个子节点，但一个子节点只能有一个父节点。
- 叶子节点：没有子节点的节点，也叫终端节点。就像公司里的一线员工。
- 兄弟节点：拥有同一个父节点的节点之间互称兄弟。
- 节点的度：一个节点拥有的子节点个数。比如一个节点有3个子节点，它的度就是3。
- 树的度：树中所有节点的度的最大值。
- 深度与高度：深度是从根节点往下数，高度是从叶子节点往上数。我习惯用「深度」表示层数，根节点深度为1。
一个小经验：我在做文件系统解析时，经常需要计算目录的深度。如果你用递归实现，记得控制递归深度，否则栈溢出会让你头疼一整天。
二叉树的定义与性质
二叉树是树家族里最常用的结构。它的特点是：每个节点最多有两个子节点，分别叫左孩子和右孩子。说白了，就是每个节点最多生两个娃。
为什么二叉树这么火？因为它的结构简单，存储和遍历都容易实现。我做过一个表达式求值引擎，就是用二叉树来存储运算符和操作数的，跑起来特别稳。
二叉树有几个重要性质，我建议你记牢：
| 性质 | 说明 |
|---|---|
| 性质1 | 第 i 层最多有 2^(i-1) 个节点（i≥1） |
| 性质2 | 深度为 k 的二叉树最多有 2^k - 1 个节点 |
| 性质3 | 叶子节点数 = 度为2的节点数 + 1 |
| 性质4 | 具有 n 个节点的完全二叉树深度为 ⌊log₂n⌋ + 1 |
嗯，这里要注意性质3。我曾经在调试红黑树时，用这个性质来验证树的平衡性，帮了大忙。
二叉树的存储结构
二叉树怎么存？主要有两种方式：
1. 顺序存储（数组）
用数组来存二叉树，根节点放在下标1（或0），左孩子放在 2i，右孩子放在 2i+1。这种方式适合完全二叉树，空间利用率高。但如果是斜树，数组里会空出大量位置，浪费内存。
// 顺序存储示例
// 假设二叉树：根节点值为'A'，左孩子'B'，右孩子'C'
char tree[10];
tree[1] = 'A'; // 根节点
tree[2] = 'B'; // 左孩子
tree[3] = 'C'; // 右孩子
// 访问左孩子：tree[2*i]，右孩子：tree[2*i+1]2. 链式存储（链表）
这是最常用的方式。每个节点包含数据域、左指针和右指针。我个人习惯用这种方式，因为它灵活，不浪费空间。
typedef struct TreeNode {
int data; // 数据域
struct TreeNode *left; // 左孩子指针
struct TreeNode *right; // 右孩子指针
} TreeNode;
// 创建一个节点
TreeNode* createNode(int data) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}避坑指南：我曾经在嵌入式项目中用链式存储二叉树，忘了释放内存，结果系统跑了三天就崩了。记住：malloc 和 free 要成对出现，尤其是树这种递归结构，释放时要用后序遍历。
二叉树的遍历
遍历，说白了就是把树里的每个节点都访问一遍。根据访问根节点的时机，分为三种：
前序遍历（根左右）
先访问根节点，再遍历左子树，最后遍历右子树。我常用前序来复制一棵树。
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); // 访问根
}注意：递归遍历虽然代码简洁，但如果树很深（比如超过1000层），递归会导致栈溢出。我在嵌入式裸机开发中遇到过这个问题，后来改成了非递归（用栈模拟）才解决。
知识体系总览
下面这张图帮你理清本章的核心脉络：
你看，树的知识点其实就这么多。从定义到性质，从存储到遍历，每一步都环环相扣。我个人觉得，学树的关键在于动手画图——你拿张纸，画一棵二叉树，然后用手模拟遍历过程，比看十遍代码都管用。
好了，这一章就到这里。记住：树是递归定义的，所以递归思维很重要。但也要警惕递归的陷阱，该用栈模拟时就果断用栈。