第1章：树与二叉树基础

树这种数据结构，说实话，我刚开始学的时候也觉得挺抽象的。链表、栈、队列好歹是线性的，树突然就分叉了。但后来在实际项目中写文件系统、做表达式解析，才发现树无处不在。今天我们就从最基础的东西聊起。

1.1 树的定义与基本术语

树是一种非线性的数据结构。它由 n（n≥0）个节点组成，节点之间有明确的层次关系。n=0 时叫空树，这跟空链表一个道理。

树的定义是递归的：一棵树由根节点和若干棵互不相交的子树构成。嗯，这里要注意——子树之间不能有交集，否则就变成图了。

举个例子：一个文件目录就是典型的树。根目录是根节点，子文件夹是子节点，空文件夹就是叶子节点。我在做嵌入式文件系统时，就经常用树来管理目录结构，遍历起来特别直观。

1.2 二叉树的定义与性质

二叉树是树里最常用的一种。说白了，就是每个节点最多只有两个子节点，分别叫左孩子和右孩子。为什么二叉树这么火？因为它的结构简单，存储和操作都方便。

二叉树有五个重要性质，我建议你记牢：

1. 性质一：第 i 层最多有 2^(i-1) 个节点（i≥1）。
2. 性质二：深度为 k 的二叉树最多有 2^k - 1 个节点。
3. 性质三：叶子节点数 = 度为2的节点数 + 1。这个我经常用来验证树的构建是否正确。
4. 性质四：n 个节点的完全二叉树深度为 ⌊log₂n⌋ + 1。
5. 性质五：完全二叉树按层序编号，父节点 i 的左孩子是 2i，右孩子是 2i+1。

二叉树还有两种特殊形态：满二叉树和完全二叉树。满二叉树就是每一层都塞满了节点；完全二叉树则是除了最后一层，其他层都满，最后一层的节点都靠左排列。这两种树用顺序存储特别省空间。

1.3 二叉树的存储结构

存储二叉树有两种方式，我分别说说我的使用心得。

顺序存储（数组实现）

用数组存二叉树，核心就是利用性质五的下标关系。适合存完全二叉树或满二叉树，不然会浪费大量空间。

// 顺序存储示例：用数组存完全二叉树
#define MAX_SIZE 100
int tree[MAX_SIZE];  // tree[1] 存根节点，tree[0] 不用

// 访问左孩子：下标 2*i
// 访问右孩子：下标 2*i + 1
// 访问父节点：下标 i/2

链式存储（链表实现）

链式存储更灵活，每个节点包含数据域和两个指针域。这是最常用的方式，我90%的项目都用它。

// 二叉树的链式存储结构
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;
}

你想想看，链式存储每个节点只存自己的数据和孩子指针，想怎么挂就怎么挂。唯一的缺点就是多花了两个指针的内存，但现在的硬件基本不在乎这点开销。

1.4 二叉树的遍历

遍历是二叉树最核心的操作。说白了，就是把树里所有节点都访问一遍。根据访问根节点的时机，分为前序、中序、后序。另外还有按层遍历的层次遍历。

下面这张图展示了四种遍历的核心逻辑：

递归遍历（代码实现）

// 前序遍历：根 → 左 → 右
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;
    
    // 简单队列实现（实际项目建议用循环队列）
    TreeNode *queue[100];
    int front = 0, rear = 0;
    
    queue[rear++] = root;  // 根节点入队
    
    while (front < rear) {
        TreeNode *cur = queue[front++];  // 出队
        printf("%d ", cur->data);        // 访问当前节点
        
        if (cur->left)  queue[rear++] = cur->left;   // 左孩子入队
        if (cur->right) queue[rear++] = cur->right;  // 右孩子入队
    }
}

层次遍历的应用场景很多。比如打印树的图形结构、求树的宽度、找某一层的所有节点。我在做UI控件树的渲染时，就用层次遍历来逐层绘制界面元素。

1.5 遍历的应用场景

不同的遍历方式有各自的用武之地：

• 前序遍历：复制一棵树、序列化二叉树。先复制根，再复制左右子树，逻辑很顺。
• 中序遍历：二叉搜索树的排序输出。BST的中序遍历结果就是有序序列，这个特性我经常用来做数据校验。
• 后序遍历：删除整棵树、计算表达式树的值。先处理孩子再处理根，符合依赖关系。
• 层次遍历：求树的高度、宽度、判断是否为完全二叉树。

好了，树与二叉树的基础就聊到这里。这些概念是后续学习二叉搜索树、平衡树、堆、哈夫曼树的基石。建议你亲手把代码敲一遍，跑几个测试用例，感受一下递归的调用过程。相信我，动手写过一遍，比看十遍都管用。

---

公众号：蓝海资料掘金营，微信 deep3321