树

1 树的概念

树作为一种非线性的数据结构，是由n(n ≥ 0)个结点组成的有限集合。 如果 n = 0 称为空树，如果 n > 0，树有且仅有一个特定的结点——根结点。 除根结点外的其他结点划分为互不相交的有限集，每个集合又是一棵树，称为根结点的子树。

---

• 树的度：结点拥有的子树的数量为结点的度，树的度定义为树的所有结点中度的最大值。
• 度为 0 的结点为叶子结点，度不为 0 的结点为分支结点。

---

树的前驱和后继：

• 除根结点没有前驱外，其余每个结点都有唯一的一个前驱结点。
• 除叶子结点没有后继外，每个结点都可以有多个后继结点。
• 结点的直接后继称为结点的孩子，结点的直接前驱称为结点的父亲，同一个双亲的不同结点互称兄弟。

---

树中结点的层次：树中根结点为第 1 层，根结点的孩子为第2层，依次类推。 树的深度（高度）：树中结点的最大层次。（部分题目中根结点为第 0 层）

---

• n 个结点的树，有且仅有 n－1 条边
• 树中任意两个结点之间有且仅有一条简单路径（路径上的结点都不相同的路径）

2 树的存储

2.1 双亲表示法

对父节点进行存储

第一行一个整数 n，表示结点个数 第二行 n－1 个数，第 i 个数是结点 i + 1 的父节点编号（第 1 个数的值是 2 号结点的父结点）

int n, tree[N];
cin >> n;
for(int i = 2; i <= n; i++) cin >> tree[i];

2.2 孩子表示法

对孩子节点进行存储

第一行一个整数 n，表示结点个数 第二行 n－1 个数，第 i 个数是结点 i + 1 的父节点编号（第 1 个数的值是 2 号结点的父结点）

使用 vector 存储每一个结点的所有孩子，因此tree[i] 里存储的是 i 结点的所有孩子结点。

vector<int> tree[N];
int n;
cin >> n;
for(int i = 2; i <= n; i++) {
    int x;
    cin >> x;
    tree[x].push_back(i);
}

3 二叉树

3.1 二叉树的概念

二叉树（Binary Tree，简称BT）是一种度数 最大为 2 的树，即二叉树的每个结点最多有两个子结点。每个结点的子结点分别称为左孩子、右孩子，它的两棵子树称为左子树、右子树。

---

一棵深度为 k 且有 2^k－1 个结点的二叉树称为满二叉树。

---

若二叉树的高度为 k，除第 k 层外，其它各层 1～k－1的结点数都达到最大个数，且第 k 层缺少的结点是从右到左并连续的，这就是完全二叉树。

3.2 二叉树的性质

• 「性质一」 在二叉树的第 i 层上最多有2^i − 1个结点（i >=1）。第 1 层最多 1 个结点，第 2 层最多 2个结点，第 3 层最多 4 个结点。（像二进制位权）

• 「性质二」 深度为 k 的二叉树至多有 2^k − 1 个结点（k >  = 1)（像二进制全 1 的情况）

• 「性质三」 对任意一棵二叉树，如果其叶子结点的数量为 n₀，度为 2 的结点数为 n₂，则一定满足n₀ = n₂ + 1。

证明： 结点总数 n 等于 0 度结点 n₀、1 度结点 n₁，2 度结点 n₂ 之和。即 $\textcolor{red}{n = n_0 + n_1 + n_2}$ (式子1) 1 度结点有 1 个孩子，2 度结点有 2 个孩子，树中只有根结点不是任何结点的孩子，故二叉树中结点总数又可以表示为 $\textcolor{red}{n = n_1 + 2n_2 + 1}$ (式子2) 由式子1和式子2得到 $\textcolor{red}{n_0 = n_2 + 1}$。

• 「性质四」 具有 n(n ≥ 0) 个结点的完全二叉树的深度为 ⌊log₂n⌋ + 1。（⌊⌋表示下取整）
  • 其实就是最多把最后一层填满，为2^k − 1，对于61来说，不足64，2⁶ = 64，6层就够了。

证明： 深度为 k 的完全二叉树，前面 k－1 层一定是满的，所以 n > 2^k − 1－1，同时 n ≤ 2^k − 1，得到 $\textcolor{red}{2^{k-1}－ 1 < n ≤ 2^k－1}$，所以 k = ⌊log₂n⌋ + 1。

• 「性质五」 如将一棵有 n 个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号 1，2，…，n，则有以下关系：
  • 若 i = 1，则结点 i 为根，无父结点
  • 若 i > 1，则 i 的父结点编号为 ⌊i/2⌋
  • 若 2 × i > n，则 i 无左孩子，否则其左孩子编号为 2 × i
  • 若 2 × i + 1 > n，则 i 无右孩子，否则其右孩子编号为２ × ｉ + 1

4 二叉树遍历

先中后由根的位置决定 ## 4.1 先序遍历 先序遍历也叫做先根遍历。 顺序：根 → 左 → 右 首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树，如果二叉树为空则返回。

1. 输出当前结点的值
2. 递归去处理左子树
3. 递归去处理右子树

struct tree {
    int value;
    int left;
    int right;
} t[N];

void pre_order(int id) {  // 访问id节点
    cout << t[id].value << " ";  // 输出当前节点的值
    if(t[id].left) pre_order(t[id].left); // 有左孩子访问左孩子
    if(t[id].right) pre_order(t[id].right);  // 有右孩子访问右孩子
}

// 完全二叉树
void dfs(int id) {  // 访问id节点
    cout << tree[id] << " ";  // 输出当前节点
    if(id * 2 <= n) dfs(id * 2); // 有左孩子访问左孩子
    if(id * 2 + 1 <= n) dfs(id * 2 + 1);  // 有右孩子访问右孩子
}

4.2 中序遍历

中序遍历也叫做中根遍历。 顺序：左 → 根 → 右 首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树，若二叉树为空则结束返回。

1. 递归去处理左子树
2. 输出当前结点的值
3. 递归去处理右子树

void dfs(int id) {  // 访问id节点
    if(id * 2 <= n) dfs(id * 2); // 有左孩子访问左孩子  
    cout << tree[id] << " ";  // 输出当前节点
    if(id * 2 + 1 <= n) dfs(id * 2 + 1);  // 有右孩子访问右孩子
}

4.3 后序遍历

后序遍历也叫做后根遍历。 顺序：左 → 右 → 根 首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点，若二叉树为空则结束返回。

1. 递归去处理左子树
2. 递归去处理右子树
3. 输出当前结点的值

void dfs(int id) {  // 访问id节点
    if(id * 2 <= n) dfs(id * 2);  // 有左孩子访问左孩子  
    if(id * 2 + 1 <= n) dfs(id * 2 + 1);   // 有右孩子访问右孩子
    cout << tree[id] << " "; // 输出当前节点
}

4.4 层次遍历

二叉树的层次遍历，就是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按照从左到右的顺序对结点逐个访问。

5 二叉树重建

5.1 重建思路

二叉树有三种不同的遍历方式：先序遍历，中序遍历和后序遍历。 中序遍历+另外任意一种遍历方式，可以唯一确定一颗二叉树。先序遍历与后序遍历不一定能唯一确定一个二叉树。

操作步骤：

1. 通过先序/后序，判断根结点
2. 通过根结点在中序里判断左右子树
3. 在先序/后序中找到左右节点，重复操作，画出树的结构。

5.2 重建代码

5.2.1 求先序

已知中序和后序，求先序。 后序遍历的最后一个是根节点，由这个根节点可以在中序遍历中确定左子树和右子树的大小和元素，然后递归的去处理左子树和右子树，由于是求先序序列，所以是先输出，再递归左子树，再递归右子树。

• 中序
  • 左子树：0 开始，id 个元素
  • 右子树：id + 1 开始，len - id - 1 个元素
• 后序
  • 左子树：0 开始，id 个元素
  • 右子树：id 开始，len - id - 1 个元素

void dfs_pre(string in, string post) {  
    int len = in.size();  
    if(len == 0) return;  // 长度为0，返回
    // 查找在中序中的根节点下标，作为分割点划分左子树、右子树
    int id = in.find(post.back());  
    cout << in[id];  // 先序，先输出根节点，再递归左子树和右子树
    string in_left = in.substr(0, id), post_left = post.substr(0, id);  
    string in_right = in.substr(id + 1, len - id - 1), post_right = post.substr(id, len - id - 1);  
    dfs_pre(in_left, post_left);  // 递归左子树
    dfs_pre(in_right, post_right);  // 递归右子树
}

5.2.2 求后序

已知先序和中序，求后序。 先序遍历的第一个是根节点，由这个根节点可以在中序遍历中确定左子树和右子树的大小和元素，然后递归的去处理左子树和右子树，由于是求后序序列，所以是先递归左子树，再递归右子树，再输出。

• 先序
  • 左子树：1 开始，id 个元素
  • 右子树：id + 1 开始，len - id - 1 个元素
• 中序
  • 左子树：0 开始，id 个元素
  • 右子树：id + 1 开始，len - id - 1 个元素

void dfs_post(string pre, string in) {  
    int len = in.size();  
    if(len == 0) return;  // 长度为0，返回
    // 查找在中序中的根节点下标，作为分割点划分左子树、右子树
    int id = in.find(pre.front());  
    string pre_left = pre.substr(1, id), in_left = in.substr(0, id);  
    string pre_right = pre.substr(id + 1, len - id - 1), in_right = in.substr(id + 1, len - id - 1);  
    dfs_post(pre_left, in_left);  // 递归左子树
    dfs_post(pre_right, in_right);  // 递归右子树
    cout << in[id];  // 后序，先递归左子树和右子树，再输出根节点
}

6 二叉搜索树

二叉搜索树（Binary Search Tree，BST）是一种应用非常广泛的二叉树，又称二叉查找树，二叉排序树，可以用二叉树进行组织。一般用亲子结构表示一个结点，即一个树结点中，除了数据 data 以外，还包含 left，right 和 parent。 二叉搜索树具有的性质：

• 若左子树不空，则左子树上所有结点的值均小于它根结点的值。
• 若右子树不空，则右子树上所有结点的值均大于它根结点的值。
• 左右子树也是一棵二叉搜索树。

搜索过程总结：

• 比根结点数据大，且右子树不空，则向右子树搜索，若右子树空则数据不存在。
• 比根结点数据小，且左子树不空，则向左子树搜索，若左子树空则数据不存在。

根据二叉搜索树的性质和图示，可以得出二叉搜索树中的最大值在树的最右侧，最小值在树的最左侧。

由于二叉搜索树可以用二叉树进行组织，因此，该搜索的过程可以用二叉树递归遍历实现。搜索效率平均O(log₂N)。 但存在这样的一种特殊情况，此时的二叉搜索树退化为一条单链，搜索效率降为 O(n)。

7 哈夫曼树

7.1 基本概念

哈夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度最短的二叉树，广泛应用于数据压缩（如 ZIP、JPEG、MP3 等编码技术）。它由 David A. Huffman 在 1952 年提出，权值越大的节点越靠近根结点，越小的节点就越远离根节点，是贪心算法（Greedy Algorithm）的经典应用。

• 权值（Weight）：每个叶子节点可以赋予一个权值（Weight），通常表示字符出现的频率或概率。
• 路径长度（Path Length）：从根节点到某个节点所经过的边的数量。
• 带权路径长度（Weighted Path Length）：树中所有叶子节点的权值乘以其路径长度的总和。

哈夫曼树的目标：构造 WPL 最小的二叉树，以提高编码效率。

7.2 构建步骤

1. 初始化：将所有节点视为独立的树，每个树仅含一个节点。
2. 选择最小权值的两棵树：从森林中选出权值最小的两棵树（节点）。
3. 合并两棵树：把这两棵树作为左右子树构成一个新节点，其权值为两个子树的权值之和。
4. 重复步骤 2~3，直到森林中只剩一棵树，即为哈夫曼树。

在判别树中，若带权路径长度越小，说明判别次数越少，在底层的执行效率上也会相应更高，这也是体现最优二叉树“优”的地方之一。

7.3 哈夫曼编码

哈夫曼编码是从哈夫曼树中生成的一种变长编码：

• 高频字符用短编码，低频字符用长编码。
• 无前缀冲突（任何编码都不是另一个编码的前缀）。
• 从根节点出发，左边编码为0，右边编码为1。
• 从根节点到叶子节点的路径就是该字符的编码。