大师兄的数据结构学习笔记(七）:堆
大师兄的数据结构学习笔记(九）: 图
一、哈夫曼树
1. 带权路径长度(WPL)
- 树的所有叶结点的带权路径长度之和，称为树的带权路径长度，表示为WPL。
- 公式:
2. 什么是哈夫曼树(Huffman Tree)
-
如果一颗二叉树的WPL达到最小，称为最优二叉树或哈夫曼树。
3. 哈夫曼树的构造
- 每次把权值最小得两颗二叉树合并。
// 树结构
struct TreeNode
{
int Weight; //权值
int lchild, rchild, parent; // 左、右和双亲结点的下标
};
// 选出权值最小的两个结点
void SelectMin(TreeNode a[], int n, int& s1, int& s2)
{
for (int i = 0; i < n; i++)
{
if (a[i].parent == -1)
{
s1 = i;
break;
}
}
for (int i = 0; i < n; i++)
{
if (a[i].parent == -1 && a[s1].Weight > a[i].Weight)
s1 = i;
}
for (int j = 0; j < n; j++)
{
if (a[j].parent == -1 && j != s1)
{
s2 = j;
break;
}
}
for (int j = 0; j < n; j++)
{
if (a[j].parent == -1 && a[s2].Weight > a[j].Weight && j != s1)
s2 = j;
}
}
// 构造哈夫曼树
void Huffman(TreeNode huftree[],int w[],int n)
{
for (int i = 0; i < 2 * n - 1; i++) // 初始化
{
huftree[i].parent = -1;
huftree[i].lchild = -1;
huftree[i].rchild = -1;
}
for (int i = 0; i < n; i++) // 构造只有根节点的二叉树
{
huftree[i].Weight = w[i];
}
for (int k = n; k < 2 * n - 1; k++) // 从权值最小的两个合并
{
int i1, i2;
SelectMin(huftree, k, i1, i2);
huftree[i1].parent = k;
huftree[i2].parent = k;
huftree[k].lchild = i1;
huftree[k].rchild = i2;
huftree[k].Weight = huftree[i1].Weight + huftree[i2].Weight;
}
}
4. 哈夫曼树的特点
- 没有度为1的结点。
- n个叶结点的哈夫曼树共有2n-1个结点。
- 任意非叶结点的左右子树交换后仍是哈夫曼树。
- 对同一组权值，可以存在不同构的两个哈夫曼树。
二、哈夫曼编码
1. 关于编码
- 在通信行业中，通常用二进制编码表示字母或其他字符，并用这样的编码来表示字符序列, 例: A,B,C分别用00,01,10表示，ABC就是000110。
2. 前缀编码
- 实际应用中各字符的出现频度不相同,为了让编码序列的总长度更小，所需总空间最少，需要使用短编码表示大频率字符，用长编码表示小频率字符。
- 译码的二义性问题，例：A,B,C分别为0,1,11，011可以译成ABB或AC。
- 为了解决这个问题，需要使用前缀编码，要求任一字符的编码都不能是另一字符编码的前缀。
3. 用二叉树设计前缀编码
- 左右分支分表为0,1。
- 字符只在叶节点上
- 例：A:0 C:10 B:110 D:111
4. 用哈夫曼树设计前缀编码
- 假设需传送的电文为‘ABBCCCD’, 二叉树编码为'0110110101010111'(16位)。
- 使用频率(权值)为：A(1) B(2) C(3) D(1)。
- 这时如果使用哈夫曼树，可以根据权重优化编码，使编码最短。
- 例: A(111) B(10) C (0) D(110)
- 优化后的编码为：'1111010000110'(13位）
4. 实现哈夫曼编码
#ifndef HUFFMANCODE
#define HUFFMANCODE
#include<string>
using namespace std;
// 哈夫曼树结点结构
struct Node {
int Weight; // 权重
char ch; // 存储符号
string code; // 对应的编码
int leftChild, rightChild, parent; // 树的元素
};
class HuffmanCode
{
public:
HuffmanCode(string str); // 构造函数
~HuffmanCode(); // 析构函数
void getMin(int& first, int& second, int parent); // 选取两个最小的元素
void Merge(int first, int second, int parent); // 合并结点
void Encode(); // 编码
void Decode(string str); // 解码
private:
Node* HuffmanTree; // 哈夫曼树
int leafSize; // 叶结点个数，也就是字符种类
};
#endif // !HUFFMANCODE
#include <iostream>
#include "HuffmanCode.h"
//析构函数
HuffmanCode::~HuffmanCode()
{
delete[]HuffmanTree;
}
// 构造函数
HuffmanCode::HuffmanCode(string str)
{
int len = (int)str.size();
int arr[256], i;
HuffmanTree = new Node[256]; // 分配空间
for (i = 0; i < (2 * len - 1); i++)
{
HuffmanTree[i].leftChild = -1;
HuffmanTree[i].rightChild = -1;
HuffmanTree[i].parent = -1;
HuffmanTree[i].code = "";
}
memset(arr, 0, sizeof(arr)); // 初始化内存空间
for (i = 0; i < len; i++) // 统计字符出现次数
{
arr[str[i]]++;
}
leafSize = 0;
for (i = 0; i < 256; i++)
{
if (arr[i] != 0)
{
HuffmanTree[leafSize].ch = (char)i;
HuffmanTree[leafSize].Weight = arr[i];
leafSize++;
}
}
int first, second;
for (i = leafSize; i < (2 * leafSize - 1); i++) // 合并两个最小的结点
{
getMin(first, second, i);
Merge(first, second, i);
}
}
// 合并两个weight最小的结点
void HuffmanCode::Merge(int first, int second, int parent)
{
HuffmanTree[first].parent = parent;
HuffmanTree[second].parent = parent;
HuffmanTree[parent].leftChild = first;
HuffmanTree[parent].rightChild = second;
HuffmanTree[parent].Weight = HuffmanTree[first].Weight + HuffmanTree[second].Weight;
}
// 选择两个weight最小的元素
void HuffmanCode::getMin(int& first, int& second, int parent)
{
double weight = 0;
int i;
for (i = 0; i < parent; i++)
{
if (HuffmanTree[i].parent != -1) // 已选过
{
continue;
}
if (weight == 0) // 第一次选
{
weight = HuffmanTree[i].Weight;
first = i;
}
else if (HuffmanTree[i].Weight < weight)
{
weight = HuffmanTree[i].Weight;
first = i;
}
}
weight = 0;
for (i = 0; i < parent; i++)
{
if (HuffmanTree[i].parent != -1 || i == first) // 如果是first跳过
{
continue;
}
if (weight == 0) // 如果是第一次选到
{
weight = HuffmanTree[i].Weight;
second = i;
}
else if (HuffmanTree[i].Weight < weight)
{
weight = HuffmanTree[i].Weight;
second = i;
}
}
}
// 编码
void HuffmanCode::Encode()
{
string code;
int i, j, k, parent;
for (i = 0; i < leafSize; i++)
{
j = i;
code = "";
while (HuffmanTree[j].parent != -1)
{
parent = HuffmanTree[j].parent;
if (j == HuffmanTree[parent].leftChild)
{
code += "0";
}
else
{
code += "1";
}
j = parent;
}
for (k = (int)code.size() - 1; k >= 0; k--)
{
HuffmanTree[i].code += code[k];
}
std::cout << HuffmanTree[i].ch << "的编码为:" << HuffmanTree[i].code << endl;
}
}
// 解码
void HuffmanCode::Decode(string str)
{
string decode, temp;
int len = (int)str.size();
int i, j;
decode = temp = "";
for (i = 0; i < len; i++)
{
temp += str[i];
for (j = 0; j < leafSize; j++)
{
if (HuffmanTree[j].code == temp)
{
decode += HuffmanTree[j].ch;
temp = "";
break;
}
}
if (i == len - 1 && j == leafSize)
{
cout << "未找到编码" << endl;
return;
}
}
cout << decode << endl;
}
