树 - 哈夫曼树及其应用 - 哈夫曼编码 （二）
根据最优二叉树构造哈夫曼编码
利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码 哈夫曼编码正是一种应用广泛且非常有效的数据压缩
技术 该技术一般可将数据文件压缩掉 %至 % 其压缩效率取决于被压缩文件的特征
具体做法
( )用字符c i 作为叶子 p i 或f i 做为叶子c i 的权 构造一棵哈夫曼树 并将树中左分支和右分支分别标记为 和 ;
( )将从根到叶子的路径上的标号依次相连 作为该叶子所表示字符的编码 该编码即为最优前缀码(也称哈夫曼编码)
哈夫曼编码为最优前缀码
由哈夫曼树求得编码为最优前缀码的原因
① 每个叶子字符c i 的码长恰为从根到该叶子的路径长度l i 平均码长(或文件总长)又是二叉树的带权路径长度WPL 而哈
夫曼树是WPL最小的二叉树 因此编码的平均码长(或文件总长)亦最小
② 树中没有一片叶子是另一叶子的祖先 每片叶子对应的编码就不可能是其它叶子编码的前缀 即上述编码是二进制的前缀码
求哈夫曼编码的算法
( )思想方法
给定字符集的哈夫曼树生成后 求哈夫曼编码的具体实现过程是 依次以叶子T[i]( ≤i≤n )为出发点 向上回溯至根为止
上溯时走左分支则生成代码 走右分支则生成代码
注意
① 由于生成的编码与要求的编码反序 将生成的代码先从后往前依次存放在一个临时向量中 并设一个指针start指示编码在
该向量中的起始位置(start初始时指示向量的结束位置)
② 当某字符编码完成时 从临时向量的start处将编码复制到该字符相应的位串bits中即可
③ 因为字符集大小为n 故变长编码的长度不会超过n 加上一个结束符 \ bits的大小应为n+
( )字符集编码的存储结构及其算法描述
typedef struct {
char ch; //存储字符
char bits[n+ ]; //存放编码位串
}CodeNode;
typedef CodeNode HuffmanCode[n];
void CharSetHuffmanEncoding(HuffmanTree T HuffmanCode H)
{//根据哈夫曼树T求哈夫曼编码表H
int c p i;//c和p分别指示T中孩子和双亲的位置
char cd[n+ ]; //临时存放编码
int start; //指示编码在cd中的起始位置
cd[n]= \ ; //编码结束符
for(i= i <n，i++){ 依次求叶子t[i]的编码
H[i].ch=getchar();//读入叶子T[i]对应的字符
start=n; //编码起始位置的初值
c=i; //从叶子T[i]开始上溯
while((p=T[c].parent)>=0){//直至上溯到T[c]是树根为止
//若T[c]是T[p]的左孩子，则生成代码0;否则生成代码1
cd[--start]=(T[p).1child==C)?'0'：'1';
c=p; //继续上溯
}
strcpy(H[i].bits，&cd[start]); //复制编码位串
}//endfor
}//CharSetHuffmanEncoding
文件的编码和解码
有了字符集的哈夫曼编码表之后，对数据文件的编码过程是：依次读人文件中的字符c，在哈夫曼编码表H中找到此字符，若
H[i].ch=c，则将字符c转换为H[i].bits中存放的编码串。wingwiT.
对压缩后的数据文件进行解码则必须借助于哈夫曼树T，其过程是：依次读人文件的二进制码，从哈夫曼树的根结点(即T[m-
1])出发，若当前读人0，则走向左孩子，否则走向右孩子。一旦到达某一叶子T[i]时便译出相应的字符H[i].ch。然后重新从根出发
继续译码，直至文件结束。
文件的编码和解码算法【参见练习】。
lishixinzhi/Article/program/sjjg/201311/23862
线扶开思： 哈夫曼树 在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码.哈夫曼编码是哈夫曼树的一个应用.哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码.首先介绍什么是哈夫曼树.哈夫曼...
鄯善县15094063313： 哈夫曼树的应用 - ？
线扶开思： 1、哈夫曼编码 在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符.例如,需传送的报文为“AFTER DATA EAR ARE ART AREA”,这里用到的字符集为“A,E,R,T,F,D”,各字母出现的次数为{8,4,5,3,1,...
鄯善县15094063313： 简述哈夫曼树的性质.？
线扶开思： 哈 夫 曼 树 2.9 二叉树的应用2.9.1 哈夫曼树及应用 哈夫曼树又称最优树(二叉树),是一类带权路径最短的树.构造这种树的算法最早是由哈夫曼(Huffman)1952年提出,这种树在信息检索中很有用.结点之间的路径长度:从一个结点到另一...
鄯善县15094063313： 到底什么是哈夫曼树啊,求例子 - ？
线扶开思： 哈夫曼树是给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree).哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近. 例子: 1、将w...
鄯善县15094063313： 哈夫曼树的建立？
线扶开思： 在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码.哈夫曼编码是哈夫曼树的一个应用.哈夫曼编码应用广泛,如JPEG中就应用了哈夫曼编码. 首先介绍什么是哈夫曼树.哈夫曼树又称最...
鄯善县15094063313： 哈夫曼树的建立及应用？
线扶开思： 给你个我写的哈夫曼函数: void HuffmanTree(HuffmanTree &HT, int * w, int n) { //w 存放n 个字符的权值(均>0),构造赫夫曼树HT if (n<=1) return; m=2* n-1; HT=(HuffmanTree)malloc(m+1) * sizeof(HTNode); //分配存储空间 //用给定的n个权...
鄯善县15094063313： 什么是哈夫曼树呢? - ？
线扶开思： 夫曼树是带权路径长度最小的二叉树,用途是平均查找信息的代价最小. 普通二叉树的用途也普通,比较通用,就是信息存储和查找. 普通二叉树可能有的只有一个子节点,而哈夫曼树一定有两个.
鄯善县15094063313： 请简述哈夫曼树的应用领域.已知字符A B C D E F的权值为8 12 5 20 4 11,请写出构造哈夫曼树的过程,并为这些字符设计哈夫曼编码,一步一步的! - ？
线扶开思：[答案] 哈夫曼树的应用领域:数字传输编码压缩.先编造哈夫曼树,哈夫曼树构造规则:假设有n个权值,则构造出的哈夫曼树有n个叶子结点.n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:(1) 将w1、w2、…,wn看成是有n ...
鄯善县15094063313： 题目: 哈夫曼树应用 - ？
线扶开思： 在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符.例如,需传送的报文为“AFTER DATA EAR ARE ART AREA”,这里用到的字符集为“A,E,R,T,F,D”,各字母出现的次数为{8,4,5,3,1,1}.现要求为这...
鄯善县15094063313： 霍夫曼树和霍夫曼编码trcpy怎么定义 - ？
线扶开思： 一、哈夫曼树的概念和定义什么是哈夫曼树?让我们先举一个例子.判定树: 在很多问题的处理过程中,需要进行大量的条件判断,这些判断结构的设计直接影响着程序的执行效率.例如,编制一个程序,将百分制转换成五个等级输出....
