第6章树和二叉树(4.18)讲述.ppt

例：字符串‘ABACCDA’ 设A、B、C、D编码分别为00、01、10、11，则编码为14位‘00010010101100’ ，对方接收时将其译码。如设A、B、C、D编码分别为0、00、1和01，则上述7个字符转换成总长为9位‘000011010’，但是这样的电文无法译码。‘0000’可有多种译法‘AAAA’或‘ABA’、‘BB’ 。 前缀编码：任一个字符的编码都不是另一个字符编码的前缀。 可利用二叉树设计前缀编码 怎么进行不等长编码？ 如何避免二义性？ 二叉树用于编码 用二叉树进行编码： （1）左右分支：0、1 （2）字符只在叶子结点上 例：字符串‘ABACCDA’ 字符频率：A:3, B:1, C:2, D:1 A B C D 0 0 0 1 1 1 WPL=3*2+1*2+2*2+1*2=14 A B C D 0 0 0 1 1 1 如何构造一棵编码代价最小的二叉树？ 哈夫曼树 A：1 B：000 C：01 D：001 WPL=3*1+1*3+2*2+1*3 =13 例：要传送数据 state、seat、act、tea、cat、set、a、eat，如何使传送的长度最短？ 为了保证长度最短，先看字符出现的次数，然后将出现次数当作权。为保证传送词间互相区别，则需加入一空白字符，空白字符^出现次数为7， 字符 字符出现的次数 c s e a ^ t 2 3 5 7 7 8 字符 字符出现的次数 c s e a ^ t 2 3 5 7 7 8 2 3 5 7 7 8 2 3 5 10 5 2 3 5 7 7 14 8 5 10 2 3 5 18 32 7 7 14 8 5 10 2 3 5 18 c: 1100 s: 1101 e: 111 a: 00 t: 10 ^: 01 哈夫曼编码算法的实现 由于哈夫曼树中没有度为1的结点，则一棵有n个叶子的哈夫曼树共有2n-1个结点，可以用一个大小为2n-1的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。静态三叉链表描述如下： typedef struct  { unsigned int weight ; /* 用来存放各个结点的权值*/ unsigned int parent, LChild, RChild ; /*指向双亲、 孩子结点的指针*/ }HTNode, * HuffmanTree; /*动态分配数组， 存储赫夫曼树*/ typedef char * *HuffmanCode ; /*动态分配数组， 存储赫夫曼编码*/ 创建赫夫曼树并求赫夫曼编码的算法如下： HuffmanTree CrtHuffmanTree(HuffmanTree ht , HuffmanCode hc, int * w, int n) {/*w存放n个权值, 构造赫夫曼树ht, 并求出赫夫曼编码hc */ if (n=1) return ; m=2*n-1;  ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/ for(i=1; i=n; i++) ht［i］ ={ w［i］, 0, 0, 0}; /*叶子结点初始化*/ for(i=n+1; i=m; i++) ht［i］ ={0, 0, 0, 0}; /*非叶子结点初始化*/ for(i=n+1; i=m; i++) /*创建非叶子结点, 建赫夫曼树*/ {/*在ht［1］~ht［i-1］的范围内选择两个parent为0且weight最小的结点，其序 号分别赋值给s1、 s2返回*/ select(ht, i-1, 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 *)); /*