数据结构第15讲_赫夫曼树及其应用_c[精品].ppt

第6章 树和二叉树 6.1 树的定义和基本术语 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4 树和森林 6.6 赫夫曼树及其应用;6.6 赫夫曼树及其应用; 在许多应用中，常常将树中的结点赋上一个有着某种意义的实数，称其为该结点的权。 结点的带权路径长度（WPL)规定为从树根到该结点之间的路径长度与该结点上权的乘积。; 树中所有叶子结点的带权路径长度之和。通常记为： 其中 n 表示叶子结点的数目，wi 和 li分别表示叶子结点ki的权值和根到ki之间的路径长度。;4）赫夫曼（Huffman）树 又称最优二叉树。它是 n 个带权叶子结点构成的所有二叉树中，带权路径长度WPL最小的二叉树。;; 1）根据给定的n个权值{w1, w2, …, wn}，构造 n棵二叉树的集合 F = {T1, T2, …,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树；;第一步：;3.判定树 (赫夫曼树的应用之一);输入10000个数据，则需进行31500次比较。;有没有一种更好的办法来减少比较次数呢？; 70≤a80 ;4.赫夫曼编码（赫夫曼树的应用之二）;字符：A B A C C D A; 如何能缩短传送电文的 总长度，从而节省传送 时间呢？; 若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样有可能缩短传送电文的总长度。;2）前缀编码;利用二叉树设计二进制的前缀编码;3）赫夫曼编码;例：设通信用的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为 { 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 }，试为这8个字母设计哈夫曼编码。;0.07;0.07;0.07;typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; } HTNode, *HuffmanTree; //动态分配数组存储赫夫曼树 typedef char **HuffmanCode; ;void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w, int n) {//w存放n个字符的权值，构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC if (n=1) return; // n为字符数目， m=2*n-1; // m为结点数目 HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //HT存放Huffman树结构，0号单元未用,其余前n个单元 //存放树的叶子结点，n-1个单元存放内部结点 for (p=HT, i=1; i=n; ++i,++p,++w) { p-weight = *w; p-parent=0; p-lchild=0; p-rchild=0; } // *p={*w,0,0,0}；初始化HT中的叶结点循环退出时i=n+1;; for (; i=m;++i,++p) { p-weight = 0; p-parent=0; p-lchild=0; p-rchild=0; } // *p={0,0,0,0}; 初始化HT中的内部结点 for (i=n+1; i=m;++i) // 建赫夫曼树，(建立HT静态链表中的链) { Select(HT,i-1,s1,s2);//在HT[1～i-1]中选择parent // 为0且weight最小的两个结点，序号分别为s1和s2 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; }; //从叶子到根逆向求赫夫曼编码 HC= (HuffmanCode)malloc((n+1)*sizeof(char *)); cd = (char *)malloc( n * sizeof(char) ); cd[n-1]=‘\0’; //编码结束符 for (i=1;i=n;++i) //逐个字符求赫夫曼编码 { start = n-1; //编码结束符