数据结构--哈夫曼树与哈夫曼编码
填坑系列之哈夫曼树
刚开始看哈夫曼树时有点懵懵的,加权是啥子玩意,后面查阅资料后才明白,哈夫曼树以及哈夫曼编码多用在压缩编码中,再配合二倍速食用B站大学的网课,算是把整个算法过了一遍
the main structure
const int Max = 1000;
char **HuffmanCode;
typedef struct Node {
int weight;
int parent, left, right;
} HTNode, *HuffmanTree;
Select
select是来选择剩余结点中权值最小的两颗二叉树(包括新构造的树)的左右子树来构建一个新的二叉树,新根节点权值为其左右子树根节点的权值之和
void Select(HuffmanTree ht, int k, int& id1, int& id2) {
long min1, min2;
min1 = min2 = 99999; // 不能太小
for (int i = 0;i < k;i++) {
if (ht[i].parent == -1 && min1 > ht[i].weight) {
// 选择无双亲的结点
if (min1 < min2) {
// 这里是比大小的操作,规定min1为小
min2 = min1;
id2 = id1;
}
min1 = ht[i].weight; // 这个操作可以把这k个数据都遍历一遍,可以选出两个最小的结点
id1 = i;
} else if (ht[i].parent == -1 && min2 > ht[i].weight) {
min2 = ht[i].weight;
id2 = i;
}
}
}
Create a Huffman Tree
void HuffmanTree(huffTree &ht, int n) {
int m = n * 2 - 1;
int id1, id2;
int i;
if (n < 0) // 创建空树
return;
ht = new Node[m];
for (i = 0;i < m;i++) {
ht[i].parent = ht[i].left = ht[i].right = -1;
// 初始化各节点
}
for (i = 0;i < n;i++) {
cin >> ht[i].weight; // 输入各个结点的权值
}
for (i = n;i < m;i++) {
Select(ht, i, id1, id2);
// 在n个结点中选择俩无双亲的结点且权值最小的结点
ht[id1].parent = ht[id2].parent = i;
// 获得id1,id2,把第i个结点设为它俩的双亲
ht[i].left = id1;
ht[i].right = id2; // 设第i个结点的左右孩子为id1,id2
ht[i].weight = ht[id1].weight + ht[id2].weight;
}
}
destroy a Huffman Tree
void Destroy(HuffmanTree &ht) {
delete[] ht;
ht = NULL;
}
create the Huffman Code
void createHuffmanCode(HuffmanTree ht, HuffmanCode &hc, int n) {
int start;
int cur, f;
hc = new char *[n + 1];
char *cd = new char[n];
cd[n - 1] = '\0';
for (i = 0;i < n;i++) {
start = n - 1;
cur = i; // 当前结点在数组中的位置
f = hf[i].parent; // 当前结点的父节点在数组的位置
while (f != 0) {
// 如果该结点是父节点的左孩子则对应编码为0,否则右孩子为1
start--;
if (hf[f].left == cur)
cd[start] = '0';
else
cd[start] = '1';
// 以父节点为孩子结点,继续朝树根的方向遍历
cur = f;
f = hf[f].parent;
}
// 跳出循环后,cd数组中从下标start开始,存放的就是该结点的哈夫曼编码
hc[i] = new char[n - start];
strcpy(hc[i], &cd[start]);
}
delete cd;
}
the code
#include <bits/stdc++.h>
using namespace std;
const int Max = 9999;
typedef char **HuffmanCode;
typedef struct Node {
int weight;
int parent, left, right;
} HTNode, *HuffmanTree;
void Select(HuffmanTree ht, int k, int id1, int id2) {
int min1 = min2 = 9999;
for (int i = 0;i < k;i++) {
if (ht[i].parent == -1 && min1 < ht[i].weight) {
if (min1 < min2) {
min2 = min1;
id2 = id1;
}
id1 = i;
min1 = ht[i].weight;
} else if (ht[i].parent == -1 && min2 > ht[i].weight) {
min2 = ht[i].weight;
id2 = i;
}
}
}
void createHuffmanTree(HuffmanTree ht, int n) {
int id1, id2;
if (n <= 0)
return;
for (int i = 0; i < n; i++) {
ht[i].left = ht[i].right = ht[i].parent = 0;
}
for (int i = 0;i < n;i++) {
cin >> ht[i].weight;
}
for (int i = 0;i < n;i++) {
Select(ht, i, id1, id2);
ht[id1].parent = ht[id2].parent = i;
ht[i].left = id1;
ht[i].right = id2;
ht[weight] = ht[id1].weight + ht[id2].weight;
}
}
void createHuffmanTreeCode(HuffmanTree ht, HuffmanCode &hc, int n) {
int start, cur f;
hc = new char*[n + 1];
char* cd = new char[n];
cd[n - 1] = '\0';
for (int i = 0;i < n;i++) {
start = n - 1;
cur = i;
f = ht[i].parent;
while (f != 0) {
start--;
if (ht[f].left == cur) {
cd[start] = '0';
} else {
cd[start] = '1';
}
cur = f;
f = ht[i].parent;
}
hc[i] = cd[n - start];
strcpy(hc[i], &cd[start]);
}
delete cd;
}
int main() {
int n;
cin >> n;
HuffmanTree ht;
HuffmanCode hc;
int sum = 0;
HuffmanTree(ht, n);
createHuffmanCode(ht, hc, n);
for (int i = 0;i < 2 * n - 1;i++) {
cout << ht[i].weight << ' '; // 测试,输出所有结点,包括非原有结点
}
cout << endl;
for (int i = 0;i < n;i++) {
cout << hc[i] << ' '; // 输出每个结点的HuffmanCode
}
}
参考链接
数据结构:哈夫曼树与哈夫曼编码 - 乌漆WhiteMoon - 博客园 (cnblogs.com)
数据结构与算法基础--第09周04--5.7哈夫曼树及其应用4-5.7.2哈夫曼树的构造算法2-哈夫曼树算法实现_哔哩哔哩_bilibili(共6p)