数据结构第06章_树和二叉树.ppt

2）前缀编码 若对某一字符集进行不等长编码，则要求字符集中任一字符的编码都不能是其他字符编码的前缀。符合此要求的编码叫做前缀编码。 如何设计前缀编码？ 利用二叉树设计二进制的前缀编码 如何得到电文总长最短的二进制前缀编码呢？ 0 1 a b c d 1 1 0 0 假设有一棵如左图所示的二叉树，四个叶结点分别表示A、B、C、D四个字符，且约定左分支表示字符‘0’，右分支表示字符‘1’，则可以从根结点到叶子结点的路径上以分支字符组成的字符串作为该叶子结点的编码。可以证明，如此得到的必为二进制前缀编码。 3）赫夫曼编码 设计电文总长最短的二进制前缀编码即： 以 n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码称赫夫曼编码。 例：设通信用的电文由字符集{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.19 0.02 0.06 0.32 0.03 0.21 0.10 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 0.05 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 0.05 0.11 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 0.05 0.11 0.17 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 0.05 0.11 0.17 0.28 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 0.05 0.11 0.17 0.28 0.40 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 0.05 0.11 0.17 0.28 0.40 0.60 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 0.05 0.11 0.17 0.28 0.40 0.60 1.00 0 0 0 0 0 0 0 1 1 1 1 1 1 1 a = 1010 b = 00 c = 10000 d = 1001 e = 11 f = 10001 g = 01 h = 1011 b g e d a h c f typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; } HTNode, *HuffmanTree; //动态分配数组存储赫夫曼树 typedef char **HuffmanCode; 建立赫夫曼树及求赫夫曼编码的算法 赫夫曼树没有度为1的结点，则一棵有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。 由于在构造赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子到根的路径；而为译码需从根出发走一条从根到叶子的路径。所以，每个结点既需知道双亲的信息，又需知道孩子结点的信息。 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;