最优二叉树--哈夫曼树和最优前缀编码--哈夫曼编码_哈夫曼树最优前缀码

作者：你好赵伟 | 2024-03-16 01:51:36

踩

哈夫曼树最优前缀码

1.最优二叉树的定义

最优二叉树又称哈夫曼树，是一种带权路径长最短的树。树的路径长度是从树根到每一个叶子之间的路径长度之和。节点的带树路径长度为从该节点到树根之间的路径长度与该节点权（比如字符在某串中的使用频率）的乘积。

2.构造哈夫曼树

2.1贪心算法

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
在构建哈夫曼树的过程中，即每次选出两个权值最小的数据，构成左右子树。

2.2构建哈夫曼树的过程

有一堆数据0，1，2，3，4该如何构建哈夫曼树呢？

按照贪心算法每次找权值最小（即值最小）的两个数，构成孩子结点，并将这两个数据排除出这一堆数据之外
由于哈弗曼树的数据全在叶子结点，所以把上述权值最小的两个数据构成父结点，然后再将父结点的权值放回上述数据，返回第一步，重复上述过程，直到所有的数据都变成哈夫曼树的叶子结点

这里写图片描述

2.3用代码实现哈夫曼树

1>从构建哈夫曼树的过程我们可以看到每次要选出两个最小的数据，为了提高效率，我们将数据的结点建堆,由于要取权值最小的，所以建小堆，这样能避免因为用数据建堆可能造成重复创建结点
构建堆的代码：

[cpp] view plain copy

print ?

#include <vector>
template<class T>
struct Greater
{
bool operator()(const T& left, const T& right) const
{
return left > right;
}
};
template<typename T,class Compare=Greater<T>>
class Heap
{
public:
Heap()
{}
Heap(T* a, size_t n)
{
//减少多次开辟容量的代价
v.reserve(n);
for (size_t i = 0; i < n; i++)
{
v.push_back(a[i]);
}
//建堆
int Size = v.size();
for (int i = (Size - 2) / 2; i >= 0; i–)
{
AdjustDown(i);
}
}
//从哪个结点开始调整
void AdjustDown(int parent)
{
Compare com;
int Size = v.size();
int child = parent * 2 + 1;
while (child < Size)
{
//if (child + 1 < Size&&v[child + 1] > v[child])
if (child + 1 < Size&&com(v[child + 1], v[child]))
{
child++;
}
//if (v[child] > v[parent])
if (com(v[child],v[parent]))
{
swap(v[child], v[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void AdjustUp(int child)
{
Compare com;
int parent = (child - 1) / 2;
while (parent >= 0)
{
//if (v[child] > v[parent])
if (com(v[child], v[parent]))
{
swap(v[child], v[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
void Push(const T& x)
{
v.push_back(x);
AdjustUp(v.size() - 1);
}
void Pop()
{
swap(v[0], v[v.size() - 1]);
v.pop_back();
AdjustDown(0);
}
T& Top()
{
assert(v.size() > 0);
return v[0];
}
size_t Size()
{
return v.size();
}
protected:
vector<T> v;
};

2> 每次取出堆顶的最小的数据之后，将堆中的存放结点删除，重复两次，再将权值相加，创建一个新的结点，并将三个结点链接，将它存放到堆中，在堆中每次删除和增加数据时，记得将堆调整为小堆，直到堆中只剩下一个结点时，哈夫曼树就构建成功了

构建哈夫曼树代码：

[cpp] view plain copy

print ?

#include “Heap.hpp”
template<typename W>
struct HuffmanNode
{
HuffmanNode<W>* _lchild;
HuffmanNode<W>* _rchild;
HuffmanNode<W>* _parent;
W _w;
HuffmanNode(const W &w)
:_lchild(NULL)
, _rchild(NULL)
, _w(w)
, _parent(NULL)
{}
};
template <typename W>
class HuffmanTree
{
typedef HuffmanNode<W> Node;
public:
HuffmanTree()
:_root(NULL)
{}
HuffmanTree(W* a, size_t n,W &invalid)
{
//堆中存放的是结点,而比较大小的时候我们希望比较的是权值
struct NodeCompare
{
bool operator()(const Node* left, const Node* right) const
{
return left->_w < right->_w;
}
};
Heap<Node*, NodeCompare> minHeap;
for (size_t i = 0; i < n; i++)
{
//此处需要重载
if (a[i] != invalid)
{
Node* cur = new Node(a[i]);
minHeap.Push(cur);
}
}
Node* parent = NULL;
//根据权值生成小堆,选小堆中最小的两个数据生成父节点
while (minHeap.Size()>1)
{
Node* left = minHeap.Top();
minHeap.Pop();
Node* right = minHeap.Top();
minHeap.Pop();
Node* cur = new Node(left->_w + right->_w);
minHeap.Push(cur);
parent = cur;
parent->_lchild = left;
parent->_rchild = right;
left->_parent = parent;
right->_parent = parent;
}
_root = parent;
}
Node* GetRoot()
{
return _root;
}
protected:
Node* _root;
};

3.哈夫曼编码

3.1前缀编码

在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀（最左子串）。
例：
比如一组编码01，010，001，100，110就不是前缀编码，因为01是010的前缀，如果去掉01和010就是前缀编码了。好比人名张三和张三章就不是前缀编码。

3.2哈夫曼编码（最优前缀编码）

对于一棵具有叶子结点的哈弗曼树，若对树中的每个左支赋予0，右支赋予1（也可以左1右0），则从根到每个叶子结点的通路上，各分支的赋值构成一个二进制串，该二进制串称为哈夫曼编码。
这里写图片描述
从叶节点往根扫描，若为左子树则标记为0，为右子树则标记为1。如上图6的编码即为：00，5的编码100，等等。

3.3如何实现哈夫曼编码

统计字符出现的个数
构建哈夫曼树
生成哈夫曼编码

构建哈夫曼编码的代码：
测试用例：aaaabbbccd

[cpp] view plain copy

print ?

#include “Huffman.hpp”
#include <algorithm>
//字符串每个结点的信息
typedef size_t LongType;
struct CharInfo
{
char ch; //字符
LongType count; // 字符出现个数
string code;
//比较字符串出现的个数是否相等
bool operator!=(const CharInfo &x) const
{
return this->count != x.count;
}
CharInfo operator+(const CharInfo &x) const
{
CharInfo ret;
ret.count = this->count + x.count;
return ret;
}
bool operator<(const CharInfo &x) const
{
return this->count < x.count;
}
};
class HuffmanCode
{
typedef HuffmanNode<CharInfo> Node;
public:
HuffmanCode()
{
for (size_t i = 0; i < 256; i++)
{
_infos[i].ch = i;
_infos[i].count = 0;
}
}
void Code(const char* filename)
{
assert(filename);
FILE* fout = fopen(filename, “r”);
assert(fout);
//1.统计字符个数
char ch = fgetc(fout);
while (ch != EOF)
{
_infos[ch].count++;
ch = fgetc(fout);
}
//2. 构建哈夫曼树
//非法值用字符出现次数为0
CharInfo invalid;
invalid.count = 0;
HuffmanTree<CharInfo> tree(_infos, 256, invalid);
//3生成哈夫曼编码
Node* root = tree.GetRoot();
GenerateHuffmanCode(root);
}
//从每个叶子结点往根节点走,规定左边标记为1,右边标记为0
void GenerateHuffmanCode(Node* root)
{
if (root == NULL)
return;
if (root->_rchild == NULL&&root->_lchild == NULL)
{
Node* cur = root;
Node* parent = NULL;
string s;
while (cur->_parent != NULL)
{
parent = cur->_parent;
if (parent->_lchild == cur)
s.push_back(’1’);
else
s.push_back(’0’);
cur = parent;
}
//stl中提供的算法逆置,只需提供一段迭代器区间即可
reverse(s.begin(), s.end());
root->_w.code = s;
//输出霍夫曼编码
cout <<”ch:”<< root->_w.ch <<“ ”<<“count:”<<root->_w.count<< “ ” << root->_w.code << endl;
}
GenerateHuffmanCode(root->_lchild);
GenerateHuffmanCode(root->_rchild);
}
protected:
CharInfo _infos[256];
};
void TestHuffmanCode()
{
HuffmanCode fc;
fc.Code(”Input.txt”);
}
//test.cpp
#include <iostream>
#include <assert.h>
#include <string>
using namespace std;
#include “HuffmanCode.hpp”
int main()
{
TestHuffmanCode();
return 0;
}

测试结果：
这里写图片描述
生成的哈弗曼树即为：

4.哈夫曼编码的应用

主要应用于信息传输和数据压缩等方面。

附:
BTree的插入和查找算法分析（详细图解过程）
http://blog.csdn.net/skyroben/article/details/73755103

红黑树（RBTree）的插入算法以及如何测试一棵树是否是红黑树？（详细图解说明）
http://blog.csdn.net/skyroben/article/details/72837890

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】