哈夫曼树和哈夫曼编码(数据结构程序设计)

哈夫曼树和哈夫曼编码本节初赛复赛都会考。

初学数据结构的读者可以在本节领略到数据结构的奥妙。

在学习本节内容之前，我们先跳过概念学习怎样构造一棵哈夫曼树。

一、如何构造一棵哈夫曼树？（哈夫曼树也是一棵二叉树）给 n 个点，每个点都有权值，构造一棵哈夫曼树。

每次选剩下的两棵根权值最小的树合并成一棵新树，新树的根权值等于两棵合并前树的根权值和。

（一开始一个点也看成一棵树，只不过这棵树没有孩子节点）例1： 4 个点， a、 b、 c、 d，权值分别为 7、 5、 2、4。

构树过程：因为 4 个点，所以合并 3 次（ n 个点，合并n-1 次）第一步：选根权值最小的两棵树2（c）和 4（d）合并，新树的根节点为6，如图 (b) ；第二步：选根权值最小的两棵树5（b）和 6 合并，新树的根节点为11，如图 (c) ；第二步：选根权值最小的两棵树7（a）和 11 合并，新树的根节点为18，如图 (c) ；例 2 ： 6 个点， a 、b 、 c、 d、 e 、 f，权值分别为0.4 、 0.3 、 0.1 、0.1 、 0.02 、0.08 。

构图过程同例1。

（如下图）二、基本概念树的路径长度PL：从树根到树的每个节点的路径长度（每条边长度为1）之和（完全二叉树为这种路径长度最短的二叉树）。

树的带权路径长度 WPL：树的所有叶子节点的带权路径长度（该节点到根节点路径长度与节点上权的乘积）之和。

透彻理解树的路径长度和树的带权路径长度这两个概念非常重要。

哈夫曼树：带权路径长度 WPL 最短的二叉树（最优二叉树）构造这种树的算法最早是由哈夫曼(Huffman)1952 年提出，这种树在信息检索中很有用。

例如例 1，构造哈夫曼树的WPL为 35 是最小的。

具体比较如下图：三、哈夫曼编码一篇电文，原文为：AMCADEDDMCCAD。

现在要把原文转换成01 串发送给对方。

为了节省资源，我们当然希望翻译好的01 串长度尽量的短。

数据结构哈夫曼树和哈夫曼编码权值一、引言在计算机领域，数据结构是非常重要的一部分，而哈夫曼树和哈夫曼编码是数据结构中非常经典的部分之一。

本文将对哈夫曼树和哈夫曼编码的权值进行全面评估，并探讨其深度和广度。

通过逐步分析和讨论，以期让读者更深入地理解哈夫曼树和哈夫曼编码的权值。

二、哈夫曼树和哈夫曼编码的基本概念1. 哈夫曼树哈夫曼树，又称最优二叉树，是一种带权路径长度最短的二叉树。

它的概念来源于一种数据压缩算法，可以有效地减少数据的存储空间和传输时间。

哈夫曼树的构建过程是基于给定的权值序列，通过反复选择两个最小权值的节点构建出来。

在构建过程中，需要不断地重排权值序列，直到构建出一个满足条件的哈夫曼树。

2. 哈夫曼编码哈夫曼编码是一种变长编码方式，它利用了哈夫曼树的特点，对不同的字符赋予不同长度的编码。

通过构建哈夫曼树，可以得到一套满足最优存储空间的编码规则。

在实际应用中，哈夫曼编码经常用于数据压缩和加密传输，能够有效地提高数据的传输效率和安全性。

三、哈夫曼树和哈夫曼编码的权值评估1. 深度评估哈夫曼树和哈夫曼编码的权值深度值得我们深入探究。

从构建哈夫曼树的角度来看，权值决定了节点在树中的位置和层次。

权值越大的节点往往位于树的底层，而权值较小的节点则位于树的高层。

这种特性使得哈夫曼树在数据搜索和遍历过程中能够更快地找到目标节点，提高了数据的处理效率。

而从哈夫曼编码的角度来看，权值的大小直接决定了编码的长度。

权值越大的字符被赋予的编码越短，可以有效地减少数据传输的长度，提高了数据的压缩率。

2. 广度评估另哈夫曼树和哈夫曼编码的权值也需要进行广度评估。

在构建哈夫曼树的过程中，权值的大小直接影响了树的结构和形状。

当权值序列较为分散时，哈夫曼树的结构会更加平衡，节点的深度差异较小。

然而，当权值序列的差异较大时，哈夫曼树的结构也会更不平衡，而且可能出现退化现象。

这会导致数据的处理效率降低，需要进行额外的平衡调整。

数据结构：哈夫曼树和哈夫曼编码哈夫曼树哈夫曼树是⼀种最优⼆叉树，其定义是：给定n个权值作为n个叶⼦节点，构造⼀棵⼆叉树，若树的带权路径长度达到最⼩，这样的树就达到最优⼆叉树，也就是哈夫曼树，⽰例图如下：基本概念深⼊学习哈夫曼树前，先了解⼀下基本概念，并以上⾯的哈夫曼树图为例路径：树中⼀个结点到另⼀个结点之间的分⽀序列构成两个结点间的路径。

路径长度：路径中分⽀的数⽬，从根结点到第L层结点的路径长度为L-1。

例如100和80的路径长度为1，50和30的路径长度为2。

结点的权：树中结点的数值，例如100，50那些。

结点带权路径长度：根结点到该结点之间的路径长度与该结点的权的乘积。

如结点20的路径长度为3，该结点的带权路径长度为：3*20 = 60。

树的带权路径长度：所有叶⼦结点的带权路径长度之和，记为WPL。

例如上图树的WPL = 1100 + 280 +320 +310 = 350。

带权路径长度⽐较前⾯说到，哈夫曼树是最优⼆叉树，因为符合哈夫曼树特点的树的带权路径长度⼀定是最⼩的，我们将哈夫曼树和普通的⼆叉树做个⽐较，仍以上图为例，上图的哈夫曼树是结点10，20，50，100组成的⼆叉树，WPL是350，⽤这四个结点组成普通的⼆叉树，结果如下：不难计算，该⼆叉树的WPL = 210 + 220 + 250 + 2100 = 360，明显⽐哈夫曼树⼤，当然⼆叉树的组成结果不唯⼀，但WPL⼀定⽐哈夫曼树⼤。

所以说哈夫曼树是最优⼆叉树。

哈夫曼树的构造现在假定有n个权值，设为w1、w2、…、wn，将这n个权值看成是有n棵树的森林，根据最⼩带权路径长度的原则，我们可以按照下⾯步骤来将森林构造成哈夫曼树：1. 在森林中选出根结点的权值最⼩的两棵树进⾏合并，作为⼀棵新树的左、右⼦树，且新树的根结点权值为其左、右⼦树根结点权值之和；2. 从森林中删除选取的两棵树，并将新树加⼊森林；3. 重复1、2步，直到森林中只剩⼀棵树为⽌，该树即为所求得的哈夫曼树。

主题：数据结构——哈夫曼树和哈夫曼编码权值1. 引言在计算机科学中，对于大规模的数据存储和传输，有效地压缩数据是一项重要的任务。

哈夫曼树和哈夫曼编码权值是一种经典的数据结构和算法，用于实现数据的高效压缩和解压缩。

本文将介绍哈夫曼树和哈夫曼编码权值的概念和原理，探讨其在数据压缩中的应用以及个人对该主题的理解。

2. 哈夫曼树2.1 概念哈夫曼树，又称最优二叉树，是一种具有最小带权路径长度的二叉树。

树的带权路径长度定义为树中所有叶子节点的权值乘以其到根节点的距离，即路径长度的总和。

2.2 构造方法哈夫曼树的构造方法是一种贪心算法。

将所有的权值作为叶子节点构建n棵单节点树。

从这些树中选择两棵权值最小的树合并，得到一棵新的树，新树的根节点的权值为这两棵树根节点权值之和。

重复此过程，直到只剩下一棵树，即为哈夫曼树。

2.3 例子以数据集[7, 5, 2, 4]为例，构造哈夫曼树的过程如下： 1. 初始状态下，将每个权值看作一棵树：7、5、2、4。

2. 选择两棵权值最小的树2和4进行合并，得到一棵新树，根节点的权值为2+4=6。

此时，剩下的树为6、5、7。

3. 选择两棵权值最小的树5和6进行合并，得到一棵新树，根节点的权值为5+6=11。

此时，剩下的树为11、7。

4. 选择两棵权值最小的树7和11进行合并，得到一棵新树，根节点的权值为7+11=18。

得到最终的哈夫曼树。

3. 哈夫曼编码权值3.1 概念哈夫曼编码权值是指在哈夫曼树中，从根节点到每个叶子节点的路径上所经过的边的权值。

对于哈夫曼树中的每个字符（叶子节点），都可以通过从根节点到叶子节点的路径上的边的权值，来进行编码。

3.2 编码方法哈夫曼编码方法的基本原则是将出现频率高的字符用较短的编码表示，出现频率低的字符用较长的编码表示。

在哈夫曼树中，根节点到左子树的路径上的边标记为0，到右子树的路径上的边标记为1。

通过遍历哈夫曼树，可以分配每个字符的编码。

哈夫曼（huffman）树和哈夫曼编码讨论QQ群：待定哈夫曼树哈夫曼树也叫最优二叉树（哈夫曼树）问题：什么是哈夫曼树？例：将学生的百分制成绩转换为五分制成绩：≥90 分: A，80～89分: B，70～79分: C，60～69分: D，＜60分: E。

if (a < 60){b = 'E';}else if (a < 70) {b = ‘D’;}else if (a<80) {b = ‘C’;}else if (a<90){b = ‘B’;}else {b = ‘A’;}判别树：用于描述分类过程的二叉树。

如果每次输入量都很大，那么应该考虑程序运行的时间如果学生的总成绩数据有10000条，则5％的数据需1 次比较，15％的数据需 2 次比较，40％的数据需 3 次比较，40％的数据需 4 次比较，因此 10000 个数据比较的次数为： 10000 (5％＋2×15％＋3×40％＋4×40％)＝31500次此种形状的二叉树，需要的比较次数是：10000 (3×20％＋2×80％)＝22000次，显然：两种判别树的效率是不一样的。

问题：能不能找到一种效率最高的判别树呢?那就是哈夫曼树回忆树的基本概念和术语路径：若树中存在一个结点序列k1,k2,…,kj，使得ki是ki+1的双亲，则称该结点序列是从k1到kj的一条路径。

路径长度：等于路径上的结点数减1。

结点的权：在许多应用中，常常将树中的结点赋予一个有意义的数，称为该结点的权。

结点的带权路径长度：是指该结点到树根之间的路径长度与该结点上权的乘积。

树的带权路径长度：树中所有叶子结点的带权路径长度之和，通常记作：其中，n表示叶子结点的数目，wi和li分别表示叶子结点ki的权值和树根结点到叶子结点ki之间的路径长度。

赫夫曼树（哈夫曼树，huffman树）定义：在权为w1,w2,…,wn的n个叶子结点的所有二叉树中，带权路径长度WPL最小的二叉树称为赫夫曼树或最优二叉树。

哈夫曼树及哈夫曼编码的程序-附流程图（下）int m,s1,s2;typedef struct {unsigned int weight;unsigned int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char *HuffmanCode;void Select(HuffmanTree HT,int n) {int i,j;for(i = 1;i <= n;i++)if(!HT[i].parent){s1 = i;break;}for(j = i+1;j <= n;j++)if(!HT[j].parent){s2 = j;break;}for(i = 1;i <= n;i++)if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;for(j = 1;j <= n;j++)if((HT[s2].weight>HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;}void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {int i, j;char *cd;int p;int cdlen;if (n<=1) return;m = 2 * n - 1;HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));for (i=1; i<=n; i++) {HT[i].weight=w[i-1];HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}for (i=n+1; i<=m; i++) {HT[i].weight=0;HT[i].parent=0;HT[i].lchild=0;HT[i].rchild=0;}puts("\n哈夫曼树的构造过程如下所⽰：");printf("HT初态:\n 结点 weight parent lchild rchild");for (i=1; i<=m; i++)printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,HT[i].parent,HT[i].lchild, HT[i].rchild);printf(" 按任意键，继续 ...");getchar();for (i=n+1; i<=m; i++) {Select(HT, i-1);HT[s1].parent = i; HT[s2].parent = i;HT[i].lchild = s1; HT[i].rchild = s2;HT[i].weight = HT[s1].weight + HT[s2].weight;printf("\nselect: s1=%d s2=%d\n", s1, s2);printf(" 结点 weight parent lchild rchild");for (j=1; j<=i; j++)printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,HT[j].parent,HT[j].lchild, HT[j].rchild);printf(" 按任意键，继续 ...");getchar(); }cd = (char *)malloc(n*sizeof(char));p = m; cdlen = 0;for (i=1; i<=m; ++i)HT[i].weight = 0;while (p) {if (HT[p].weight==0) {HT[p].weight = 1;if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; } else if (HT[p].rchild == 0){ HC[p] = (char *)malloc((cdlen+1) * sizeof(char));cd[cdlen] ='\0'; strcpy(HC[p], cd); }}else if (HT[p].weight==1){ HT[p].weight = 2;if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }} else { // HT[p].weight==2，HT[p].weight = 0; p = HT[p].parent; --cdlen; } }}void main() {HuffmanTree HT;HuffmanCode *HC;int *w,n,i;puts("输⼊结点数:");scanf("%d",&n);HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));w = (int *)malloc(n*sizeof(int));printf("输⼊%d个结点的权值\n",n);for(i = 0;i < n;i++)scanf("%d",&w[i]);HuffmanCoding(HT,HC,w,n);puts("\n各结点的哈夫曼编码:");for(i = 1;i <= n;i++)printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);getchar(); }。

课程设计（数据结构）课程设计任务书及成绩评定课题名称表达式求值哈夫曼树和哈夫曼编码Ⅰ、题目的目的和要求：巩固和加深对数据结构的理解，通过上机实验、调试程序，加深对课本知识的理解，最终使学生能够熟练应用数据结构的知识写程序。

（1）通过本课程的学习，能熟练掌握几种基本数据结构的基本操作。

（2）能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。

Ⅱ、设计进度及完成情况Ⅲ、主要参考文献及资料[1] 严蔚敏数据结构（C语言版）清华大学出版社 1999[2] 严蔚敏数据结构题集（C语言版）清华大学出版社 1999[3] 谭浩强 C语言程序设计清华大学出版社[4] 与所用编程环境相配套的C语言或C++相关的资料目录第一章概述 (1)第二章系统分析 (2)第三章概要设计 (3)第四章详细设计及实现代码 (5)第五章调试过程中的问题及系统测试情况 (9)第六章结束语 (10)参考文献 (11)第一章概述课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。

课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。

《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。

数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。

同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。

在这次的课程设计中我选择的题目是表达式求值和哈夫曼树及哈夫曼编码。

这里我们介绍一种简单直观、广为使用的算法，通常称为“算符优先法”。

哈夫曼树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。

功能：表达式求值以栈为存储结构，实现输入的表达式的求值；哈夫曼树和哈夫曼编码是实现最优二叉树的构造，并能通过最优二叉树进行编码，应用到电文中，并以此来译码。