c/c++开发分享漫谈C++哈夫曼树的原理及实现

1. 前言

什么是哈夫曼树？

把权值不同的n个结点构造成一棵二叉树，如果此树满足以下几个条件：

• 此 n 个结点为二叉树的叶结点 。
• 权值较大的结点离根结点较近，权值较小的结点离根结点较远。
• 该树的带权路径长度是所有可能构建的二叉树中最小的。

则称符合上述条件的二叉树为最优二叉树，也称为哈夫曼树(huffman tree)。

构建哈夫曼树的目的是什么？

用来解决在通信系统中如何使用最少的二进制位编码字符信息。

c/c++开发分享漫谈C++哈夫曼树的原理及实现将和大家聊聊哈夫曼树的设计思想以及构建过程。

2. 设计思路

哈夫曼树产生的背景：

在通信系统中传递一串字符串文本时，需要对这一串字符串文本信息进行二进制编码。编码时如何保证所用到的bit位是最少的，或保证整个编码后的传输长度最短。

现假设字符串由abcd 4个字符组成，最直接的想法是使用 2 个bit位进行等长编码，如下表格所示：

传输abcd字符串一次时，所需bit为 2位，当通信次数达到 n次时，则需要的总传输长度为 n*2。当字符串的传输次数为 1000次时，所需要传输的总长度为 2000个bit。

使用等长编码时，如果传输的报文中有 26 个不同字符时，因需要对每一个字符进行编码，至少需要 5位bit。

但在实际应用中，各个字符的出现频率或使用次数是不相同的，如a、b、c的使用频率远远高于x、y、z。使用等长编码特点是无论字符出现的频率差异有多大，每一个字符都得使用相同的bit位。

哈夫曼的设计思想：

• 对字符串信息进行编码设计时，让使用频率高的字符使用短码，使用频率低的用长码，以优化整个信息编码的长度。
• 基于这种简单、朴素的想法设计出来的编码也称为不等长编码。

哈夫曼不等长编码的具体思路如下：

如现在要发送仅由a、b、c、d 4 个字符组成的报文信息 ，a字符在信息中占比为 50%，b的占比是 20%，c的占比是 15%， d的 占比是10%。

不等长编码的朴实思想是字符的占比越大，所用的bit位就少，占比越小，所用bit位越多。如下为每一个字符使用的bit位数：

• a使用 1位bit编码。
• b使用 2 位 bit编码。
• c 使用 3 位 bit编码。
• d 使用 3 位 bit 编码。

具体编码如下表格所示：

如此编码后，是否真的比前面的等长编码所使用的总bit位要少？

计算结果=0.5*1+0.2*2+0.15*3+0.1*3=1.65。

先计算每一个字符在报文信息中的占比乘以字符所使用的bit位。

然后对上述每一个字符计算后的结果进行相加。

显然，编码abcd只需要 1.65 个bit ，比等长编码用到的2 个 bit位要少 。当传输信息量为 1000时，总共所需要的bit位=1.65*1000=1650 bit。

哈夫曼编码和哈夫曼树有什么关系？

因为字符的编码是通过构建一棵自下向上的二叉树推导出来的，如下图所示：

哈夫曼树的特点：

• 信息结点都是叶子结点。
• 叶子结点具有权值。如上二叉树，a结点权值为0.5，b结点权值为0.2，c结点权值为0.15，d结点权值为 0.1。
• 哈夫曼编码为不等长前缀编码（即要求一个字符的编码不能是另一个字符编码的前缀）。
• 从根结点开始，为左右分支分别编号0和1，然后顺序连接从根结点到叶结点所有分支上的编号得到字符的编码。

相信大家对哈夫曼树有了一个大概了解，至于如何通过构建哈夫曼树，咱们继续再聊。

3. 构建思路

在构建哈夫曼树之前，先了解几个相关概念：

• 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第l层结点的路径长度为l-1。
• 结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。
• 树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为wpl。

如有权值为{3,4,9,15}的 4 个结点，则可构造出不同的二叉树，其带权路径长度也会不同。如下 3 种二叉树中，b的树带权路径长度是最小的。

哈夫曼树的构建过程就是要保证树的带权路径长度最小。

那么，如何构建二叉树，才能保证构建出来的二叉树的带权路径长度最小？

如有一字符串信息由 abcdefgh 8个字符组成，每一个字符的权值分别为{3,6,12,9,4,8,21,22}，构建最优哈夫曼树的流程：

1.以每一个结点为根结点构建一个单根二叉树，二叉树的左右子结点为空，根结点的权值为每个结点的权值。并存储到一个树集合中。

2.从树集合中选择根结点的权值最小的 2 个树。重新构建一棵新二叉树，让刚选择出来的2 棵树的根结点成为这棵新树的左右子结点，新树的根结点的权值为 2 个左右子结点权值的和。构建完成后从树集合中删除原来 2个结点，并把新二叉树放入树集合中。

如下图所示。权值为 3和4的结点为新二叉树的左右子结点，新树根结点的权值为7。

3.重复第二步，直到树集合中只有一个根结点为止。

当集合中只存在一个根结点时，停止构建，并且为最后生成树的每一个非叶子结点的左结点分支标注0，右结点分支标注1。如下图所示：

通过上述从下向上的思想构建出来的二叉树，可以保证权值较小的结点离根结点较远，权值较大的结点离根结点较近。最终二叉树的带权路径长度： wpl=(3+4)*5+6*4+(8+9+12)*3+(21+22)*2=232 。并且此树的带权路径长度是所有可能构建出来的二叉树中最小的。

上述的构建思想即为哈夫曼树设计思想，不同权值的字符编码就是结点路径上0和1的顺序组合。如下表所述，权值越大，其编码越小，权值越小，其编码越大。其编码长度即从根结点到此叶结点的路径长度。

4. 编码实现

4.1 使用优先队列

可以把权值不同的结点分别存储在优先队列（priority queue）中，并且给与权重较低的结点较高的优先级（priority）。

具体实现哈夫曼树算法如下：

1.把n个结点存储到优先队列中，则n个节点都有一个优先权pi。这里是权值越小，优先权越高。

2.如果队列内的节点数>1，则：

• 从队列中移除两个最小的结点。
• 产生一个新节点，此节点为队列中移除节点的父节点，且此节点的权重值为两节点之权值之和，把新结点加入队列中。
• 重复上述过程，最后留在优先队列里的结点为哈夫曼树的根节点（root）。

完整代码：

#include   #include   #include   using namespace std;  //树结点  struct treenode {  	//结点权值  	float weight;  	//左结点  	treenode *lelfchild;  	//右结点  	treenode *rightchild;      //初始化  	treenode(float w) {  		weight=w;  		lelfchild=null;  		rightchild=null;      }  };  //为优先队列提供比较函数  struct comp {  	bool operator() (treenode * a, treenode * b) {          //由大到小排列  		return a->weight > b->weight;   	}  };    //哈夫曼树类  class hfmtree {  	private:           //优先队列容器  		priority_queue,comp> hfmqueue;  	public:  		//构造函数，构建单根结点树  		hfmtree(int weights[8]) {  			for(int i=0; i<8; i++) {  				//创建不同权值的单根树  				treenode *tn=new treenode(weights[i]);  				hfmqueue.push(tn);  			}  		}  		//显示队列中的最一个结点  		treenode* showhfmroot() {  			treenode *tn;  			while(!hfmqueue.empty()) {  				tn= hfmqueue.top();  				hfmqueue.pop();  			}  			return tn;  		}  		//构建哈夫曼树  		void create() {               //重复直到队列中只有一个结点  			while(hfmqueue.size()!=1) {  				//从优先队列中找到权值最小的 2 个单根树  				treenode *minfirst=hfmqueue.top();  				hfmqueue.pop();  				treenode *minsecOnd=hfmqueue.top();  				hfmqueue.pop();  				//创建新的二叉树  				treenode *newroot=new treenode(minfirst->weight+minsecond->weight);  				newroot->lelfchild=minfirst;  				newroot->rightchild=minsecond;  				//新二叉树放入队列中  				hfmqueue.push(newroot);  			}  		}  		//按前序遍历哈夫曼树的所有结点  		void showhfmtree(treenode *root) {  			if(root!=null) {  				cout<weight<lelfchild);  				showhfmtree(root->rightchild);  			}  		}  		//析构函数  		~hfmtree() {              //省略  		}  };    //测试  int main(int argc, char** argv) {  	//不同权值的结点  	int weights[8]= {3,6,12,9,4,8,21,22};      //调用构造函数  	hfmtree hfmtree(weights);      //创建哈夫曼树  	hfmtree.create();      //前序方式显示哈夫曼树  	treenode *root= hfmtree.showhfmroot();  	hfmtree.showhfmtree(root);  	return 0;  }  

显示结果：

上述输出结果，和前文的演示结果是一样的。

此算法的时间复杂度为o（nlogn）。因为有n个结点，所以树总共有2n-1个节点，使用优先队列每个循环须o（log n）。

4.2 使用一维数组

除了上文的使用优先队列之外，还可以使用一维数组的存储方式实现。

在哈夫曼树中，叶子结点有 n个，非叶子结点有 n-1个，使用数组保存哈夫曼树上所的结点需要 2n-1个存储空间 。其算法思路和前文使用队列的思路差不多。直接上代码：

#include   using namespace std;  //叶结点数量  const unsigned int n=8;  //一维数组长度  const unsigned int m= 2*n -1;  //树结点  struct treenode {  	//权值  	float weight;  	//父结点  	int parent;  	//左结点  	int leftchild;  	//右结点  	int rightchild;  };  class huffmantree {  	public:  		//创建一维数组  		treenode hfmnodes[m+1];  	public:  		//构造函数  		huffmantree(int weights[8]);  		~huffmantree( ) {    		}  		void findminnode(int k, int &s1, int &s2);  		void showinfo() {  			for(int i=0; ifindminnode(i-1, firstmin, secondmin);  		hfmnodes[firstmin].parent = i;  		hfmnodes[secondmin].parent = i;  		hfmnodes[i].leftchild = firstmin;  		hfmnodes[i].rightchild = secondmin;  		hfmnodes[i].weight = hfmnodes[firstmin].weight + hfmnodes[secondmin].weight;  	}  }  void huffmantree::findminnode(int k, int & firstmin, int & secondmin) {  	hfmnodes[0].weight = 32767;  	firstmin=secOndmin=0;  	for(int i=1; i<=k; i++) {  		if(hfmnodes[i].weight!=0 && hfmnodes[i].parent==-1) {  			if(hfmnodes[i].weight 

测试结果：

5. 总结

哈夫曼树是二叉树的应用之一，掌握哈夫曼树的建立和编码方法对解决实际问题有很大帮助。

以上就是漫谈c++哈夫曼树的原理及实现的详细内容，更多关于c++哈夫曼树的资料请关注<编程笔记>其它相关文章！

需要了解更多c/c++开发分享漫谈C++哈夫曼树的原理及实现，都可以关注C/C++技术分享栏目—编程笔记