第5树和二叉树精要.ppt

北京林业大学信息学院 例:设n=4, w={70,50,20,40} 试设计 huffman code (m=2*4-1=7) weight parent lch rch 1 70 0 0 0 2 50 0 0 0 3 20 0 0 0 4 40 0 0 0 5 6 7 weight parent lch rch 1 70 7 0 0 2 50 6 0 0 3 20 5 0 0 4 40 5 0 0 5 60 6 3 4 6 110 7 2 5 7 180 0 1 6 a 70 b 50 c 20 d 40 * 北京林业大学信息学院 算法 void CreatHuffmanTree (HuffmanTree HT,int n){ if(n=1)return; m=2*n-1; HT=new HTNode[m+1];//0号单元未用，HT[m]表示根结点 for(i=1;i=m;++i) {HT[i].lch=0;HT[i].rch=0;HT[i].parent=0;} for(i=1;i=n;++i)cinHT[i].weight; weight parent lch rch 1．．．８ ９．．15 5 29 7 8 14 23 3 11 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 例:设n=8, w={5,29,7,8,14,23,3,11} 试设计 huffman code (m=2*8-1=15) 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 北京林业大学信息学院 for( i=n+1;i=m;++i) //构造 Huffman树 { Select(HT,i-1, s1, s2);　 //在HT[k](1≤k≤i-1)中选择两个其双亲域为0, // 且权值最小的结点, // 并返回它们在HT中的序号s1和s2 HT[s1].parent=i; HT[s2] .parent=i; //表示从F中删除s1,s2 HT[i].lch=s1; HT[i].rch=s2 ; //s1,s2分别作为i的左右孩子 HT[i].weight=HT[s1].weight + HT[s2] .weight; //i 的权值为左右孩子权值之和 } } 北京林业大学信息学院 weight parent lch rch 1．．．８９．．15 5 29 7 8 14 23 3 11 8 15 19 29 42 58 100 9 14101012139 11 1112131415150 138562 7490 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 13 构造Huffman tree后,HT为: 北京林业大学信息学院 void CreatHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n){ //从叶子到根逆向求每个字符的赫夫曼编码，存储在编码表HC中 HC=new char *[n+1]; //分配n个字符编码的头指针矢量 cd=new char [n]; //分配临时存放编码的动态数组空间 cd[n-1]=’\0’; //编码结束符 for(i=1; i=n; ++i){ //逐个字符求赫夫曼编码 start=n-1; c=i; f=HT[i].parent; while(f!=0){ //从叶子结点开始向上回溯，直到根结点 --start; //回溯一次start向前指一个位置 if (HT[f].lchild= =c) cd[start]=’0’; //结点c是f的左孩子，则生成代码0 else cd[start]=’1’; //结点c是f的右孩子，则生成代码1 c=f; f=HT[f].parent; //继续向上回溯 } //求出第i个字符的编码