树与二叉树

由 树 的 节点数（对应位置）范围，求解出对应位置所在 二叉树的 深度

$2^{k-1}\le n<2^k$

二叉树的遍历

线索树 （除了笔试，没任何用处） 核心就是 将二叉树的空余节点 合理利用

没有 左孩子 就指向 遍历顺序 前驱，没有 右孩子 就指向 遍历顺序 后继

本题的 中序遍历： $debxac$

$x$ 的 前驱 和 后继就是 $b、a$

前序遍历 和 后序遍历 可以 构造 唯一二叉树，除非 前序 第一个子树根节点 不在后序中间位置时（在 父节点的邻接左边）

普通树的遍历

对于 普通树 来说遍历只有 前序 和 后序，中序 你不知道 根 应该放在哪里（不唯一）

树和森林的转换（Forest 和 Tree）

只存父节点

并查集

用于寻找最近公共祖先

邻接表

此处 每一个 非叶节点 对应的 孩子，都被存在一个邻接表中

后期上机题的 各类 图算法 中，存储节点用的都是 邻接表（经常用到）

左儿子右兄弟 （二叉树存储）

一个 左儿子右兄弟 表示的 二叉树， 其左儿子的右链（包括左儿子）就是该点邻接表内容

左儿子右兄弟存储的是 有序多叉树，孩子之间只有顺序（第1个、第2个…）没有左右之分

上机考的非常少

[做题总结]

1. 原树中叶子节点数 = 转换后的树中有右儿子的节点数 + 1

使用数学归纳法（删除法：分情况讨论）得证

2. F的前序遍历就是T的前序遍历

3. F的后序遍历就是T的中序遍历

二叉搜索树

Binary Search Tree 特征是 中序遍历有序 的一种 动态维护 数据结构，

如果 二叉树 中 有相同的节点，有三种处理办法

1. 数据结构中开一个 计数器

2. 等于的节点 放到 左子树

3. 等于的节点 放到 右子树

BST 总共三种操作： 插入 删除 查找

每个操作的 时间复杂度 都和 树高 $h$ 成 线性关系

插入

struct TreeNode  {
 
	int val;
	TreeNode *left , *right;
	
	TreeNode(int _val): val(_val), left(NULL), right(NULL) {}
	
}*root;
 
 
void insert(TreeNode* &root, int x) {
 
	if (!root) root = new TreeNode(x);
	
	else if (x < root->val) insert(root->left, x);
	
	else insert(root->right, x);
 
}

删除

void remove(TreeNode* &root, int x)
{
    if (!root) return;
    
    if (x < root->val)  remove(root->left, x);
    
    else if (x > root->val)  remove(root->right, x);
    
    else  //  x == root->val
    {
        if (!root->left && !root->right)  root = NULL;
        
        else if (!root->left)  root = root->right;
        
        else if (!root->right) root = root->left;
 
        else 
        {
            auto p = root->left;
            
            while(p->right) p = p->right;
            
            root->val = p->val;
            
// p = NULL;
// 这一行不起任何作用，只是把局部变量消除，要消除 root 上的节点必须用 root 才行
            
// remove(root, p->val);  
// 使用 root 也不对，因为 当前 root 节点的值就是 p-val,会陷入死循环
            
            remove(root->left, p->val);  
        }
    }
}

查找

int get_pre(TreeNode* &root, int x)     // 找前驱 即 val < x
{
    if (!root) return -INF;
    
    if (root->val >= x) return get_pre(root->left, x);
    
    return max(root->val, get_pre(root->right, x));    
}
 
 
 
 
int get_suc(TreeNode* &root, int x)   // 找后继 即 val > x  
{
    if (!root) return INF;
    
    if (root->val <= x) return get_suc(root->right, x); 
    
    // 一直迭代， 直到找到一个 可能的 答案
     
    return min(root->val, get_suc(root->left, x));   
    
    // 如果 root->val > x  右子树肯定不是该节点的对手   查找左子树中是否有遗漏的后继
}

平衡树（算法复杂度——树高）

动态维持 二叉排序树 中序遍历（ 保证树高是 $h=O(\log n)$ ）

左旋 右旋 不改变中序遍历的结果

最小不平衡子树

平衡因子：$左子树高度-右子树高度$ 平衡因子是 任意节点的固有属性

如何构造？

“找、拆、插”，直击痛点

点击跳转🖱️

从下往上，找距离最近的一个 平衡因子 大于 1 的 子树（三个节点）

将该子树上 每个节点 挂载的子树 拆开

平衡完三个节点，将拆下来的子树 根据大小 重新挂回去

表达式树

递归构造

前缀编码

编码总长只和各编码长度 有关 和 其所在位置无关

解码（从前往后，一旦匹配就可以译码）是 唯一的，所以前缀编码是 无损压缩数据的

所有编码均对应叶节点，因此 一组编码 就是 一颗二叉树

带权路径长度

$$WPL=\sum _{i=0}^n{W}_i{L}_i$$

前缀编码可以表示为一棵二叉树：

• 字符对应叶节点
• 叶节点深度等于编码长度
• 左右边分别标记 0、1

可以通过计算二叉树的总权值替代计算编码的 $WPL$

哈夫曼编码

定义： 根据符号出现频率构造哈夫曼树，生成平均码长尽可能短的前缀编码

哈夫曼编码 ⊂ 前缀编码

构造

1. 将每个字符及其频率作为一个叶节点；

2. 每次选取频率最小的两个节点合并成新节点，新节点频率为二者之和；

3. 重复该操作，直到只剩一个根节点，形成哈夫曼树；

4. 从根到叶的边分别标记为 0 和 1，所得路径就是对应字符的哈夫曼编码。

哈夫曼树节点度数一定不为 1

存在一个平均码长最短的解，其中最小的两个节点互为兄弟节点

任意节点的两条边 标记不用遵循 左零右一 的规则，左右标记 不同即可

证明

采用 闫式集合分析法（适用于贪心，dp）可以证明 哈夫曼编码 求出 $WPL$ 是最小的

1. 贪心选择

   设当前权值最小的两个节点为 $x,y$

   在一棵最优树中，可以将权值较小的节点交换到更深的位置，$WPL$ 不会增大。因此，一定存在一个最优解，使 $x,y$ 位于最深层且互为兄弟节点。

2. 问题转化

   将 $x,y$ 合并为一个权值为 $x+y$ 的新节点 $z$，则原来的 $n$ 个节点问题转化为 $n-1$ 个节点的问题。

   设合并前后的树分别为 $T,T^{\prime }$，$z$ 在 $T^{\prime }$ 的深度为 $d$ ，插入 $x、y$ 后 ， $x,y$ 对应深度为 $d+1$ ，则：

   $$WPL(T)=WPL(T^{\prime })+x+y$$

3. 递归求解

   由前两步可知，原问题一定存在一个最优树 $T$，使得 $x,y$ 互为兄弟。将 $x,y$ 合并为 $z=x+y$ 后，$T$ 唯一对应一棵 $n-1$ 个节点的树 $T^{\prime }$，且：

   $$WPL(T)=WPL(T^{\prime })+x+y$$

   下面用反证法证明 $T^{\prime }$ 必须是 $n-1$ 个节点问题的最优解。

   假设 $T^{\prime }$ 不是最优解，则存在另一棵树 $S^{\prime }$，使得：

   $$WPL(S^{\prime })<WPL(T^{\prime })$$

   将 $S^{\prime }$ 中的节点 $z$ 展开为 $x,y$，得到原问题的一棵树 $S$，则：

   $$WPL(S)=WPL(S^{\prime })+x+y<WPL(T^{\prime })+x+y=WPL(T)$$

   这与 $T$ 是原问题的最优解矛盾，故 $T^{\prime }$ 必须是 $n-1$ 个节点问题的最优解。

   因此，只需递归求解 $n-1$ 个节点的问题，再展开 $z$ 为 $x,y$，即可得到原问题的最优树。不断合并权值最小的两个节点，最终得到的哈夫曼树具有最小 $WPL$。

K 进制编码

构造方式同哈夫曼编码，每次选最小的 $K$ 个树求和，再将原 $K$ 个树删除，加上新生成的树

若 $K>2$ ，则有 补充零节点 的问题，因为要满足 完全 $K$ 叉树的定义

补充零节点

完全 $K$ 叉树中，设叶节点数为 $n_0$，内部节点数为 $n_k$，对边数计数：

$$K\cdot n_k=n_0+n_k-1$$

化简得：

$$\boxed{n_k=\frac{n_0-1}{K-1}}$$

因此，$n_0-1$ 必须能被 $K-1$ 整除（其中 $n_0=n$），即：

$$(n-1)\mathrm{mod}(K-1)=0$$

---

1. 若 $\frac{n-1}{k-1}$ 不能整除，需补充权值为 0 的 $m$ 个虚节点，直到满足：

$$(n+m-1)\mathrm{mod}(k-1)=0$$

while ((heap.size() - 1) % (k - 1)) heap.push({0, 0});

2. 权值为 0 的节点对 WPL 无贡献，因此补零不影响最终编码长度。

3. 为使最长编码尽量短，零节点应尽量放在最深层，即最先参与合并。由于零是最小权值，堆会自动优先取出零节点，无需额外处理。

应用

合并果子 如何搬运可以最省体力？

代码：

// Problem: 合并果子
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/150/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
const int N = 1e6 + 10;
 
 
signed main() {
    ios::sync_with_stdio(false),  cin.tie(0),  cout.tie(0);
	int n;
	cin >> n;
	
	// 	维护小根堆
	priority_queue <int, vector<int>, greater<int>> pq;
	
	// 输入加排序
	for (int i = 0; i < n; i ++ )
	{
		int ai;
		cin >> ai;
		pq.push(ai);
	}
	LL res = 0;		// LL 必须定义大小
	while (pq.size() - 1)		// 果堆数大于 1 合并
	{
		int first = pq.top();
		pq.pop();
		int second = pq.top();
		pq.pop();
		int merge = first + second;
		res += merge;
		pq.push(merge);	
	}
	cout << res;
    return 0;
}

荷马史诗 $k$ 进制编码，如何取得 最短码长 （同时 求出最短树高）

每个单词构成一个节点：
(weight, height) = (wi, 0)
 
如果不满足满 k 叉树条件：
    加入若干个 (0, 0)
 
for 循环（重复直到只剩一个节点）：
    取出 k 个最小节点
    sum = 这些节点的权值之和
    height = 1 + 这些节点高度的最大值
    答案加上 sum
    将 (sum, height) 放回堆中
 
最终：
    第一个答案 = 最小总码权 WPL
    根节点 height = 所有解中 `最短的` 最长码长

代码：

// Problem: 荷马史诗
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/151/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 1e6 + 10;
 
int n, k;
 
signed main() {
	priority_queue<PLI, vector<PLI>, greater<PLI>> heap; 
	// 小根堆 维护 字典树
	scanf("%d%d", &n, &k);
	
	while (n --) {
		LL w; // 权值大小w 超过 int 可表示范围
		scanf("%lld", &w);
		heap.push({w, 0});
	}
	
	while ((heap.size() - 1) % (k - 1)) heap.push({0, 0}); 
	
	// 补充：权值为 0 的节点
	
	LL ans = 0;
	
	while (heap.size() > 1) {
	    LL sum = 0;
	    int height = 0;
	
	    for (int i = 0; i < k; i++) {
	        auto [weight, h] = heap.top();
	        heap.pop();
	
	        sum += weight;
	        height = max(height, h);
	    }
	
	    ans += sum;
	    heap.push({sum, height + 1});
	}
	
	printf("%lld\n%d", ans, heap.top().second);
	
	return 0;
}

普通哈夫曼只需要比较 $\text{权值}$

这道 $k$ 叉哈夫曼题需要按以下顺序比较：

$$\boxed{\text{先最小化 WPL，再最小化最大编码长度}}$$

因此堆中的节点需要保存 $(\text{权值},\text{子树高度})$ ，并按 $\text{权值优先，高度次优先}$ 进行排序。