哈夫曼树的构造和哈夫曼编码实现详细讲解(含例题详细讲解)

这篇具有很好参考价值的文章主要介绍了哈夫曼树的构造和哈夫曼编码实现详细讲解(含例题详细讲解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

一、哈夫曼树

   1.哈夫曼树的基本概念

   2.哈夫曼树的构造过程

   3.哈夫曼树的的实现

二、哈夫曼编码

    1.有关哈夫曼树编码的两个概念

    2.哈夫曼树编码满足的两个性质

    3.哈夫曼编码的实现

三、例题(含完整代码及详细注解)

    1.题目

    2.代码实现

    3.结果截图


一、哈夫曼树

1.哈夫曼树的基本概念

  • 路径:从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径。
  • 路径长度:路径上的分支数目称作路径长度。
  • 树的路径长度:从树根到每一结点的路径长度之和。
  • :赋予某个实体的 一个量,是对实体的某个或某些属性的数值化描述。在数据结构中,实体有结点和边两大类,所以对应有结点权和边权。
  • 结点的带权路径长度:从该结点到树根之间的路径长度与结点上的全的乘积。
  • 树的带权路径长度:树中所有叶子结点的带权路径长度与结点上权的乘积。
  • 哈夫曼树:假设有m个权值,可以构造一颗含n个叶子结点的二叉树,则其中带权路径长度WPL的最小二叉树称作最优二叉树或哈夫曼树。

      例如,下图中所示的两颗二叉树,都包含4个叶子结点a、b、c、d,分别带权7、5、2、4,它   们的带权路径长度分别为

哈夫曼树的构造和哈夫曼编码实现详细讲解(含例题详细讲解)

 2.哈夫曼树的构造过程

  1. 根据给定的n个权值,构建n棵只有根结点的二叉树,这n棵二叉树构成一个森林F。
  2. 在森林中选取两棵根结点的权值最小的树作为左右子树构造一颗新的二叉树,且置新的二叉树的根结点的权值为其左、右子树上的权值之和。
  3. 在森林F中删除这两颗树,同时将新得到的二叉树加入F中。
  4. 重复2和3,直到F中只含一颗树时为止。这棵树便是哈夫曼树。

      注意:在构造哈夫曼树时,首先选择权小的,这样保证权大的离根较近,在计算树的带权路径        长度时,自然会得到最小带权路径长度,这种生成算法算是一种典型的贪心法。

口诀:1.构造森林全是根

           2.选用两小造新树

           3.删除两小添新人

           4.重复2、3剩单根

哈夫曼树的构造和哈夫曼编码实现详细讲解(含例题详细讲解)

 3.哈夫曼树的实现

  算法步骤:

  1. 初始化:首先动态申请2n个单元;然后循环2n-1次,从1号单元开始,依次将1至2n-l所有单元中的双亲、左孩子、右孩子的下标都初始化为0;最后再循环n次,输入前n个单元中叶子结点的权值。
  2. 创建树:循环n-1次,通过n-1次的选择、 删除与合并来创建哈夫曼树。选择是从当前森林中选择双亲为0且权值最小的两个树根结点sl和s2;删除是指将结点s1和s2的双亲改为非0;合并就是将s1和s2的权值和作为一个新结点的权值依次存人到数组的第n+1之后的单元中,同时记录这个新结点左孩子的下标为s1,右孩子的下标为s2。
void CreateHuffmanTree(HuffmanTree& HT,int n){
	//构造哈夫曼树
	if(n<=1)  return;
	int m=2*n-1;
	HT=new HTNode[m+1]; //0单元号未用,下标从1开始 
	for(int i=1;i<=m;i++){ //初始化,将下标1~m号结点的双亲,左孩子,右孩子置为0 
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	} 
	for(int i=1;i<=n;i++){
		cin >> HT[i].weight;  //输入前n个结点的权值 
	} 
// 初始化结束,下面创开始创建哈夫曼树
//---------------------------------------------------------	
 for(int i=n+1;i<=m;i++){
 	/* 在select函数中,在前n个结点中通过n-1次的选择两个权值较小的结点,
	 进行合并,删除 来创建哈夫曼树 */
	 int s1=0,s2=0;
 	Select(HT,i-1,&s1,&s2);
 	/* 在select中挑选出两个权值较小的结点,且s1<s2;
	 合并成一个新的结点,新的结点的结点号为i ,此时s1和s2结点的双亲结点即为i */
 	HT[s1].parent=i; HT[s2].parent=i;
 	HT[i].lchild=s1;//将s1和s2分别作为结点i的左右孩子 
 	HT[i].rchild=s2;
 	HT[i].weight=HT[s1].weight+HT[s2].weight;//结点i的权值为左右孩子之和 
 } 

}
//Select函数 
void Select(HuffmanTree HT,int end,int *s1,int *s2){
	int min1,min2;//min1存放较小的,min2存放第二小的,min1<min2
	//先挑选出一个双亲结点为0的结点 ,如果双亲节点不为0说明这个结点已经在生成新节点中被使用过 
	int i=1;
	while(HT[i].parent!=0&&i<=end){
		i++;
	}
	//将第一次挑选出来的结点的权值先赋值给min1,然后i加一,挑选第二个双亲结点为0的结点
	min1=HT[i].weight;
	*s1=i;
	i++;
	// 挑选第二个双亲结点为0的结点
	while(HT[i].parent!=0&&i<=end){
		i++;
	}
	/*对挑选出来的第一个结点第二个结点再进行权值的比较,如果第二次挑选出来的HT[i].weight
	小于min1的值,则先将min1的值付给min2,再将HT[i].weight赋给min1; 如果第二次挑选出来的
	HT[i].weight大于min1的值,则将HT[i].weight赋给min2
	*/
	if(HT[i].weight<min1){
		min2=min1;
		*s2=*s1;
		min1=HT[i].weight;
		*s1=i;
	}else{
		min2=HT[i].weight;
		*s2=i;
	}
	//对余下的结点进行遍历
	for(int j=i+1;j<=end;j++){
		if(HT[j].parent!=0) continue;
		if(HT[j].weight<min1){
			min2=min1;
			min1=HT[j].weight;
			*s2=*s1;
			*s1=j;
		}
		//如果 min1<=HT[i].weight<=min2,则 将HT[j].weight的值赋给min2
		else if(HT[j].weight>=min1&&HT[j].weight<min2){
			min2=HT[j].weight;
			*s2=j;
		}	
		
	} 
}

二、哈夫曼编码

1.有关哈夫曼树编码的两个概念

  • 前缀编码:如果在一个编码方案中, 任一个编码都不是其他任何编码的前缀(最左子串),如称编码是前缀编码。例如,案例5.1中的第2种编码方案的编码0, 10, 110,111是前缀编码,而第3种编码方案的编码0,01, 010, 111 就不是前缀编码。前缀编码可以保证对压缩文件进行解码时不产生二义性,确保正确解码。
  • 哈夫曼编码:对一棵具有n个叶子的哈夫曼树,若对树中的每个左分支赋予0,右分支赋予1,则从根到每个叶子的路径上,各分支的赋值分别构成一一个二进制串,该二进制串就称为哈夫曼编码。

2.哈夫曼树编码满足的两个性质

  • 性质1  哈夫曼编码是前缀编码

    哈夫曼编码是根到叶子路径上的编码序列,由树的特点知,若路径A是另一条路径B的最左部分,则B经过了A.则A的终点一定不是叶子,而哈夫曼编码对应路径的终点一定为叶子,因此,任一哈夫曼码都不会与任意其他哈夫曼编码的前缀部分完全重叠,因此哈夫曼编码是前缀编码。

  • 性质2  哈夫曼编码是最优前缀编码

    对于包括n个字符的数据文件,分别以它们的出现次数为权值构造哈夫曼树,则利用该树对应的哈夫曼编码对文件进行编码,能使该文件压缩后对应的二进制文件的长度最短。

3.哈夫曼编码的实现

算法步骤:

  1. 分配存储刀个字符编码的编码表空间HC,长度为n+1:;分配临时存储每个字符编码的动态数组空间cd, cd[n-1]置为'\0'。
  2. 逐个求解n个字符的编码,循环n次,执行以下操作:
  • 设置变量start用于记录编码在cd中存放的位置,start 初始时指向最后,即编码结束符位置n-1;
  • 设置变量c用于记录从叶子结点向上回溯至根结点所经过的结点下标,c初始时为当前待编码字符的下标i,f用于记录i的双亲结点的下标;
  • 从叶子结点向上回溯至根结点,求得字符i的编码,当f没有到达根结点时,循环执行以下操作:

           回溯一次start向前指一个位置,即--start;

           若结点c是f的左孩子,则生成代码0,否则生成代码1,生成的代码0或1保存在cd[start]             中;
           继续向上回溯,改变c和f的值。

  • 根据数组cd的字符串长度为第i个字符编码分配空间HC[i],然后将数组cd中的编码复制    到HC[i]中。

     3. 释放临时空间cd。

typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表
 
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){
	//得到哈夫曼编码 
	int start,c,f;
	HC=new char*[n+1];      //下表从1开始,分配存储n个字符编码的编码表空间
	char* cd=new char[n];  //临时存放每个字符编码的动态数组空间
	 cd[n-1]='\0';        //编码结束符 
	for(int i=1;i<=n;i++){    //逐个字符求哈夫曼编码 
		start=n-1;            //start开始指向最后,即编码结束符的位置 
		c=i;f=HT[i].parent;   //f指向结点c的双亲结点,
		while(f!=0){          
			start--;           //回溯一次,start位置向前指一个位置 
			if(HT[f].lchild==c) cd[start]='0'; //如果结点c是f的左孩子,则生成代码0 
			else cd[start]='1';                //如果结点c是f的右孩子,则生成代码0 
			c=f;f=HT[f].parent;                //继续向上回溯,直至 f的双亲为0回溯结束 
		}   
		/* 注意:1.for循环是为了逐个字符求哈夫曼编码;while循环是为了对所求字符进行回溯,直至双亲为0
		         2.结点的双亲,左孩子,右孩子指向的全都是结点i,并不是结点的权值,这一点很容易混淆 
		*/                                    
		HC[i]=new char[n-start];    // 为第i个字符进行编码 
		strcpy(HC[i],&cd[start]);   //为第i个字符编码分配空间 
	} 
	delete cd;                    //释放临时空间 
} 

三、 例题(含完整代码及详细注解)

1.题目

  1. 一个单位有5个部门,每个部门都有一部电话,但是整个单位只有一根外线,当有电话打过来的时候,由转接员转到内线电话,已知各部门使用外线电话的频率为(次/天):5 16 9 12 19。利用哈夫曼树算法思想设计内线电话号码,使得接线员拨号次数尽可能少要求:

        (1)依据使用外线电话的频率构造二叉树。

        (2)输出设计出的各部门内线电话号码。

2.代码实现

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
typedef struct{
	int weight; 
	int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;//动态分配数组存储哈夫曼编码表

void CreateHuffmanTree(HuffmanTree &HT,int n);   //构造哈夫曼树 
void Select(HuffmanTree HT,int end,int *s1,int *s2);  //select函数 
void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n); //哈夫曼编码 


void CreateHuffmanTree(HuffmanTree& HT,int n){
	//构造哈夫曼树
	if(n<=1)  return;
	int m=2*n-1;
	HT=new HTNode[m+1]; //0单元号未用,下标从1开始 
	for(int i=1;i<=m;i++){ //初始化,将下标1~m号结点的双亲,左孩子,右孩子置为0 
		HT[i].parent=0;
		HT[i].lchild=0;
		HT[i].rchild=0;
	} 
	for(int i=1;i<=n;i++){
		cin >> HT[i].weight;  //输入前n个结点的权值 
	} 
// 初始化结束,下面创开始创建哈夫曼树
//---------------------------------------------------------	
 for(int i=n+1;i<=m;i++){
 	/* 在select函数中,在前n个结点中通过n-1次的选择两个权值较小的结点,
	 进行合并,删除 来创建哈夫曼树 */
	 int s1=0,s2=0;
 	Select(HT,i-1,&s1,&s2);
 	/* 在select中挑选出两个权值较小的结点,且s1<s2;
	 合并成一个新的结点,新的结点的结点号为i ,此时s1和s2结点的双亲结点即为i */
 	HT[s1].parent=i; HT[s2].parent=i;
 	HT[i].lchild=s1;//将s1和s2分别作为结点i的左右孩子 
 	HT[i].rchild=s2;
 	HT[i].weight=HT[s1].weight+HT[s2].weight;//结点i的权值为左右孩子之和 
 } 

}

//Select函数 
void Select(HuffmanTree HT,int end,int *s1,int *s2){
	int min1,min2;//min1存放较小的,min2存放第二小的,min1<min2
	//先挑选出一个双亲结点为0的结点 ,如果双亲节点不为0说明这个结点已经在生成新节点中被使用过 
	int i=1;
	while(HT[i].parent!=0&&i<=end){
		i++;
	}
	//将第一次挑选出来的结点的权值先赋值给min1,然后i加一,挑选第二个双亲结点为0的结点
	min1=HT[i].weight;
	*s1=i;
	i++;
	// 挑选第二个双亲结点为0的结点
	while(HT[i].parent!=0&&i<=end){
		i++;
	}
	/*对挑选出来的第一个结点第二个结点再进行权值的比较,如果第二次挑选出来的HT[i].weight
	小于min1的值,则先将min1的值付给min2,再将HT[i].weight赋给min1; 如果第二次挑选出来的
	HT[i].weight大于min1的值,则将HT[i].weight赋给min2
	*/
	if(HT[i].weight<min1){
		min2=min1;
		*s2=*s1;
		min1=HT[i].weight;
		*s1=i;
	}else{
		min2=HT[i].weight;
		*s2=i;
	}
	//对余下的结点进行遍历
	for(int j=i+1;j<=end;j++){
		if(HT[j].parent!=0) continue;
		if(HT[j].weight<min1){
			min2=min1;
			min1=HT[j].weight;
			*s2=*s1;
			*s1=j;
		}
		//如果 min1<=HT[i].weight<=min2,则 将HT[j].weight的值赋给min2
		else if(HT[j].weight>=min1&&HT[j].weight<min2){
			min2=HT[j].weight;
			*s2=j;
		}	
		
	} 
}

void CreateHuffmanCode(HuffmanTree HT,HuffmanCode &HC,int n){
	//得到哈夫曼编码 
	int start,c,f;
	HC=new char*[n+1];      //下表从1开始,分配存储n个字符编码的编码表空间
	char* cd=new char[n];  //临时存放每个字符编码的动态数组空间
	 cd[n-1]='\0';        //编码结束符 
	for(int i=1;i<=n;i++){    //逐个字符求哈夫曼编码 
		start=n-1;            //start开始指向最后,即编码结束符的位置 
		c=i;f=HT[i].parent;   //f指向结点c的双亲结点,
		while(f!=0){          
			start--;           //回溯一次,start位置向前指一个位置 
			if(HT[f].lchild==c) cd[start]='0'; //如果结点c是f的左孩子,则生成代码0 
			else cd[start]='1';                //如果结点c是f的右孩子,则生成代码0 
			c=f;f=HT[f].parent;                //继续向上回溯,直至 f的双亲为0回溯结束 
		}   
		/* 注意:1.for循环是为了逐个字符求哈夫曼编码;while循环是为了对所求字符进行回溯,直至双亲为0
		         2.结点的双亲,左孩子,右孩子指向的全都是结点i,并不是结点的权值,这一点很容易混淆 
		*/                                    
		HC[i]=new char[n-start];    // 为第i个字符进行编码 
		strcpy(HC[i],&cd[start]);   //为第i个字符编码分配空间 
	} 
	delete cd;                    //释放临时空间 
} 

int main(){
	HuffmanTree HT;
	HuffmanCode HC;
	cout<<"各部门使用外线电话的频率为:"<<endl;
	CreateHuffmanTree(HT,5);
	CreateHuffmanCode(HT,HC,5);
	cout << "各部门内线电话号码" << endl;
	for (int i = 1; i <= 5; i++) {
		cout << HC[i] << endl;
	}
	return 0;
}

3.结果截图 

哈夫曼树的构造和哈夫曼编码实现详细讲解(含例题详细讲解)

 文章中还存在着瑕疵,希望各位大神指教    文章来源地址https://www.toymoban.com/news/detail-469190.html


到了这里,关于哈夫曼树的构造和哈夫曼编码实现详细讲解(含例题详细讲解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C语言---数据结构实验---哈夫曼树及哈夫曼编码的算法实现---图的基本操作

    本篇实验代码非本人写,代码源自外部,经调试解决了部分warning和error后在本地vs上可以正常运行,如有运行失败可换至vs 未来会重构实现该两个实验 内容要求: 1、初始化(Init):能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并建立哈夫曼树 2、建立编码

    2024年02月13日
    浏览(59)
  • 数据结构实验五:哈夫曼树的设计及实现

    实验五   哈夫曼 树的设计及实现 一、实验目的 1. 掌握哈夫曼树的构造算法,理解二叉树的应用; 2. 掌握哈夫曼编码的构造算法。 二、实验内容 输入一串字符串,根据给定的字符串中字符出现的频率建立相应的哈夫曼树,构造哈夫曼编码表,在此基础上可以对压缩文件进行

    2024年02月09日
    浏览(450)
  • 【数据结构与算法】哈夫曼编码(最优二叉树)实现

    哈夫曼编码 等长编码:占的位置一样 变长编码(不等长编码):经常使用的编码比较短,不常用的比较短 最优:总长度最短 最优的要求:占用空间尽可能短,不占用多余空间,且不能有二义性 这里给出哈夫曼二叉树的实现: HuffmanTree.h: 测试数据(主函数): 运行结果截图

    2024年02月16日
    浏览(47)
  • 哈夫曼树与哈夫曼编码及等长编码

    哈夫曼树的构造:就是将给定的数据中选择最小的两个权值进行合并,然后重复该操作,构造出一个 二叉树。使其带权路径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。 例如:给定几个数值:0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.01 可以将其扩大一百倍,以方便计

    2024年02月06日
    浏览(43)
  • 15哈夫曼树/哈夫曼编码

    哈夫曼树又称为 最优树 ,作用是找到一种效率最高的判断树。 路径 :从树中一个结点到另一个结点之间的 分支 构成这两个结点之间的路径。 结点的路径长度 :两结点间路径上的分支树 如图 a :从 A - D 的路径长度就是是 2。从 A 到 B C D E F G F I 的路径长度分别为 1 1 2 2 3

    2024年02月05日
    浏览(45)
  • 哈夫曼树、哈夫曼编码/解码

    哈夫曼树的基本介绍 哈夫曼树构建步骤图解 创建哈夫曼树代码实现 基本介绍 哈夫曼编码原理剖析 哈夫曼编码的实例 思路分析 代码实现 使用哈夫曼编码压缩文件的注意事项(代码胜省略)

    2024年02月08日
    浏览(42)
  • 【数据结构与算法】哈夫曼编码(最优二叉树实现

    哈夫曼编码 等长编码:占的位置一样 变长编码(不等长编码):经常使用的编码比较短,不常用的比较短 最优:总长度最短 最优的要求:占用空间尽可能短,不占用多余空间,且不能有二义性 这里给出哈夫曼二叉树的实现: HuffmanTree.h: 测试数据(主函数): 运行结果截图

    2024年02月16日
    浏览(45)
  • c++利用哈夫曼编码实现文件的压缩加密和解压缩解密

    需求分析 @1:编码实现哈夫曼树,然后根据数据建立哈夫曼树,然后显示所有的字符的哈夫曼编码 @2:实现哈夫曼编码和解码 并通过编码实现文本文件的压缩 通过解码实现压缩文件的解压缩 概要设计 @1:在二叉树的基础上实现哈夫曼树的数据结构 @2:读取文本文件--对字符频

    2024年02月03日
    浏览(43)
  • 哈夫曼树与哈夫曼编码

    哈夫曼树:结点中赋予一个某种意义的值,称为结点的权值,从根结点开始,到目标结点经过的边数,称为路径长度,路径长度乘以权值,称为带权路径长度; 例如:根结点代表着快递集散点,一个叶子结点权值是5,在业务逻辑中代表着重量是5斤的货物📦,路径长度是3,

    2024年02月05日
    浏览(49)
  • 哈夫曼树详解及其应用(哈夫曼编码)

    一,哈夫曼树的基本概念 路径: 从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径 结点的路径长度 :两结点之间路径上的 分支数 树的路径长度: 从 树根 到每一个结点的 路径长度之和 . 记作:TL 权(weight): 将树中结点赋给一个有着某种含义的数值

    2024年02月04日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包