前言

这篇 blog 可能只能讲理论了。（只因这两个都太难了）

---

哈夫曼树

哈夫曼树的概念。

哈夫曼树可以使用 优先队列 实现。所以要先将优先队列。

优先队列

优先队列其实是提高组的内容。

优先队列是 STL 的容器之一。它实际上是一个——用 D 老师的话来说——类似栈的“麻袋”，内部使用二叉树实现，和队列一点关系都没有。如图：

先说优先队列的一些信息：

1. 优先队列实际上类似栈；
2. 优先队列内部使用二叉树（还是二叉堆？）实现；
3. 正因为（2），所以优先队列能够自动排序；
4. 优先队列默认从大到小排序。

头文件

和队列一样。

#include <queue>

定义

这个就很长了。

priority_queue <int> 队列名;

插入

这些都和栈一样了。

q.push(x);

弹出

q.pop();

队首

q.top()

从小到大

这有两种方法：

1. 压入负数，弹出 -负数；
2. 正规方法。

方法1： 只需要在压入和弹出时都加上负号：

#include <queue>
#include <iostream>
using namespace std;

priority_queue <int> q;
int n, x;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		q.push(-x);
	}
	while (!q.empty())
	{
		cout << -q.top() << "\n";
		q.pop();
	}
	return 0;
}

方法2： 需要自定义比较函数或用 greater<> ；

自定义比较函数： 这部分比较困难，也不像 sort 的比较函数。所以这里只用比较器。

比较器： 这只需要把定义改一下：

#include <queue>
#include <iostream>
using namespace std;

priority_queue <int, vector <int>, greater<int>> q;
int n, x;

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> x;
		q.push(x);
	}
	while (!q.empty())
	{
		cout << q.top() << "\n";
		q.pop();
	}
	return 0;
}

使用优先队列实现 hfm

1. 先把所有东西（结构体{权值，序号等}）压入priority_queue；
2. 弹出前两个最小的；
3. 根据最小的生成new node；
4. 递归2、3步
5. DFS每一个节点，用string存储编码；

---

二叉查找树/二叉搜索树（BST）

查找

二叉查找树的中序遍历是有序的 ，它的查找和二分查找类似。

1. 如果树为空，返回-1
2. 将根节点和x对比
3. 如果x==T->data，说明找到了，返回根节点
4. 如果x < T->data，递归查找左子树
5. 反之递归查找右子树。

平均查找时间 $O(logn)$

插入

1）如果二叉查找树为空，创建新节点 2）如果不为空：

1. 如果x<T-data，往左边插
2. 反之往右边插

创建

相当于不停地插入

删除

有三种情况（要删除节点的）：

1. 左子树为空
2. 右子树为空
3. 左右子树都不为空

左/右子树为空

直接覆盖要删除的节点

都不为空

选择要删除的左儿子的最右后代或右儿子的最左后代代替这个节点。

卡特兰数

有n个节点，可以构造成多少中二叉树（或 n 个节点入栈，有多少中出站顺序）：1，1， 2，5，14，42，132，429……