第二十二章：树——层次结构的数据¶
你好！欢迎来到第二十二章！在前面的章节，我们学习了线性结构（数组、链表）和图。这一章我们将学习一种非常重要的非线性结构——树。树就像你家里的家谱，或者电脑里的文件夹，一层一层地组织数据。树在计算机科学中无处不在：文件系统、HTML文档、数据库索引、人工智能决策树……这一章我们就来揭开树的神秘面纱！
22.1 什么是树？¶
22.1.1 树的定义¶
树是由节点和连接节点的边组成的一种数据结构，它具有以下特点：
- 有一个特殊的节点叫做根节点。
- 除了根节点外，每个节点有且只有一个父节点。
- 没有父节点的节点是根节点。
- 没有子节点的节点称为叶子节点。
- 树中没有环（即不会出现 A→B→C→A 的情况）。
直观地说，树就像一棵倒长的树——根在上，叶子在下。
22.1.2 基本术语¶
- 根：最顶层的节点，整棵树的起点。
- 父节点：某个节点的直接上层节点。
- 子节点：某个节点的直接下层节点。
- 兄弟节点：具有相同父节点的节点。
- 祖先：从根到该节点路径上的所有节点。
- 子孙：该节点以下的所有节点。
- 深度：从根到该节点的层数（根深度为0或1）。
- 高度：从该节点到最远叶子的层数。
- 子树：树中任何一个节点和它的所有后代构成的集合也是一棵树。
22.2 树的存储¶
在程序中，我们需要用某种方式把树的结构存下来。常见的存储方法有：
22.2.1 父亲表示法¶
用一个数组 parent[i] 表示节点 i 的父节点。根节点的父节点可以设为 -1 或 0。这种方法找父亲很快，但找孩子需要遍历。
int parent[100];
// 初始化
parent[0] = -1; // 节点0是根
parent[1] = 0; // 节点1的父节点是0
parent[2] = 0;
parent[3] = 1;
22.2.2 孩子表示法¶
每个节点用一个列表（vector）存储它的所有孩子。这是最常用的方法。
#include <vector>
using namespace std;
vector<int> children[100];
// 添加一条父子关系
children[0].push_back(1);
children[0].push_back(2);
children[1].push_back(3);
22.2.3 左孩子右兄弟表示法¶
将一棵普通树转化为二叉树，每个节点存两个指针：左孩子（第一个孩子）和右兄弟（下一个兄弟）。这种方法常用于将树转化为二叉树处理。
22.3 二叉树¶
22.3.1 什么是二叉树？¶
二叉树是每个节点最多有两个子节点的树，分别称为左孩子和右孩子。二叉树是最简单、最常用的树结构。
特殊形态：
- 满二叉树：所有层都是满的（每个节点都有两个子节点）。
- 完全二叉树：除了最后一层，其他层都是满的，且最后一层的节点都靠左排列。堆就是用完全二叉树实现的。
22.3.2 二叉树的存储¶
链式存储（最常用）¶
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
顺序存储（用数组，适合完全二叉树）¶
对于完全二叉树，可以用数组下标关系：
- 根节点下标为 1（或0）
- 节点 i 的左孩子下标为 2i
- 节点 i 的右孩子下标为 2i + 1
- 节点 i 的父节点下标为 i/2
这样存省空间，访问方便。
22.3.3 二叉树的遍历¶
遍历就是按某种顺序访问树中的所有节点。主要有四种遍历方式：
前序遍历（根左右）¶
先访问根节点，再遍历左子树，最后遍历右子树。
void preorder(TreeNode* root) {
if (root == NULL) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
中序遍历（左根右）¶
先遍历左子树，再访问根节点，最后遍历右子树。对于二叉搜索树，中序遍历得到升序序列。
void inorder(TreeNode* root) {
if (root == NULL) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
后序遍历（左右根）¶
先遍历左子树，再遍历右子树，最后访问根节点。
void postorder(TreeNode* root) {
if (root == NULL) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
层序遍历（广度优先）¶
从上到下，从左到右一层一层地遍历。用队列实现。
#include <queue>
void levelOrder(TreeNode* root) {
if (root == NULL) return;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* cur = q.front(); q.pop();
cout << cur->val << " ";
if (cur->left) q.push(cur->left);
if (cur->right) q.push(cur->right);
}
}
22.4 编程实例讲解¶
实例1：构建二叉树并遍历¶
题目：输入一棵二叉树的先序遍历（用 -1 表示空节点），构建二叉树，然后输出它的中序遍历。
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 根据先序输入构建二叉树（-1表示空）
TreeNode* build() {
int x;
cin >> x;
if (x == -1) return NULL;
TreeNode* node = new TreeNode(x);
node->left = build();
node->right = build();
return node;
}
void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
int main() {
cout << "请输入先序遍历序列（-1表示空节点）：" << endl;
TreeNode* root = build();
cout << "中序遍历结果：";
inorder(root);
cout << endl;
return 0;
}
输入示例：1 2 -1 -1 3 4 -1 -1 5 -1 -1 对应一棵树：
1
/ \
2 3
/ \
4 5
输出：2 1 4 3 5
实例2：求二叉树的高度¶
高度定义为从根到最远叶子的节点数（通常根高度为1）。
int height(TreeNode* root) {
if (root == NULL) return 0;
int leftH = height(root->left);
int rightH = height(root->right);
return max(leftH, rightH) + 1;
}
实例3：求二叉树的叶子节点数¶
int leafCount(TreeNode* root) {
if (root == NULL) return 0;
if (root->left == NULL && root->right == NULL) return 1;
return leafCount(root->left) + leafCount(root->right);
}
实例4：二叉搜索树（BST）¶
二叉搜索树是一棵二叉树，满足：对于任意节点，左子树所有节点的值小于它，右子树所有节点的值大于它。中序遍历得到升序序列。
插入操作：
TreeNode* insert(TreeNode* root, int val) {
if (root == NULL) return new TreeNode(val);
if (val < root->val) root->left = insert(root->left, val);
else if (val > root->val) root->right = insert(root->right, val);
return root;
}
查找操作：
bool search(TreeNode* root, int val) {
if (root == NULL) return false;
if (root->val == val) return true;
if (val < root->val) return search(root->left, val);
else return search(root->right, val);
}
实例5：堆（优先队列）¶
堆是一种完全二叉树，常用于实现优先队列。大根堆：每个节点的值大于等于其子节点的值。
这里不展开全部代码，但可以简单展示用数组实现的堆。
22.5 阶段性编程练习¶
- 练习1：手动构建一棵二叉树（如 1 左子2 右子3，2 左子4 右子5），写出它的前序、中序、后序遍历结果。
- 练习2：用代码实现二叉树的层序遍历（用队列）。
- 练习3：给定一棵二叉树，判断它是否对称（左右镜像）。
- 练习4：实现二叉搜索树的删除操作（选做，可以研究一下）。
- 练习5：用数组实现一个小根堆，支持插入和弹出最小值。
22.6 第22章编程作业¶
作业1：二叉树的最大宽度¶
给定一棵二叉树，求它的最大宽度。宽度定义为某一层最左非空节点到最右非空节点之间的节点数（包括空节点）。例如：
1
/ \
2 3
/ \
4 5
第3层宽度为 4（因为位置：4，空，空，5）。提示：可以用层序遍历，给每个节点编号。
作业2：重建二叉树¶
给定一棵二叉树的前序遍历和中序遍历序列，重建这棵树。例如前序 [1,2,4,5,3,6,7]，中序 [4,2,5,1,6,3,7]，重建并输出后序遍历。
作业3：二叉树的最近公共祖先¶
给定一棵二叉树和两个节点，求它们的最近公共祖先（LCA）。
作业4：判断一棵树是否是二叉搜索树¶
给定一棵二叉树，判断它是否是一棵有效的二叉搜索树（注意，需要保证整个子树满足大小关系，不能只判断当前节点）。
作业5：堆排序¶
用堆实现排序：先构建一个堆，然后不断弹出堆顶元素，得到排序结果。
恭喜你完成了第二十二章的学习！树是计算机科学中极其重要的数据结构，尤其是二叉树及其变种。掌握树的遍历和基本操作，将为后续学习平衡树、红黑树、B树等打下坚实基础。加油！🚀