数据结构课件110章全第六章树和二叉树幻灯片.ppt

A B C D 0 00 1 01 这样，上述电文便可编码为总长为9：’000011010’。但这时候，又可能带来歧义。比如对于’ 0000’就有多种译法，可以是’AAAA’，也可以是’ABA’等。 因此，若要设计长短不一的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。 可以利用二叉树来设计二进制的前缀编码。如图6.25所示的二叉树，其4个叶子结点分别表示A、B、C和D这4个字符，且约定左分支表示字符’0’，右分支表示字符’1’，则可以从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子结点的编码。A(0) B(10) C(110) D(111) 如何得到使电文总长最短的二进制编码呢？ 假设每种字符在电文中出现的次数为wi，其编码长度为li，电文中只有n种字符，则电文编码总长为w1l1+w2l2+…+wnln。对应到二叉树上，若置wi为叶子结点的权， li为从根到叶子的路径长度。则w1l1+w2l2+…+wnln恰为二叉树上带权路径长度WPL。 由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一棵赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。 以下讨论具体做法。 算法分析 由于赫夫曼树中没有度为1的结点（这类树又称为正则二叉树），则一棵有n个叶子结点的赫夫曼树共有2n-1个结点，可以存储在一个大小为2n-1的一维数组中。如何选定结点结构？由于在构成赫夫曼树之后，为求编码需从叶子结点出发走一条从叶子结点到根结点的路径；而为译码需从根出发走一条从根到叶子结点的路径。则对每个结点而言，需知道结点的双亲信息和孩子信息。 故可设定下述存储结构： typedef struct{ unsigned int weight; unsigned int parent, lchild, rchild; }HTNode , *HuffmanTree; //赫夫曼树 typedef char **HuffmanCode; //赫夫曼编码表 w pa lc rc 1 2 3 4 5 6 7 0 0 0 0 0 0 0 7 5 2 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (1) s1=3,s2=4 m1=2,m2=4 7 5 2 4 6 0 0 0 0 0 0 3 0 0 0 0 0 0 4 0 0 0 0 5 5 0 0 0 1 2 3 4 5 6 7 k (2) w pa lc rc 1 2 3 4 5 6 7 0 0 0 0 3 2 0 7 5 2 4 6 11 0 0 0 0 0 4 5 0 0 6 5 5 6 0 0 k s1=2,s2=5 m1=5,m2=6 (3) w pa lc rc 1 2 3 4 5 6 7 0 0 0 0 3 2 1 7 5 2 4 6 11 18 0 0 0 0 4 5 6 7 6 5 5 6 7 0 k s1=1,s2=6 m1=7,m2=11 (4) w pa lc rc 赫夫曼编码的算法描述： 输入：w存放n个字符的权值 输出：赫夫曼树HT，求赫夫曼编码HC [初始化] 总结点数为m=2*n-1；申请m个结点空间的赫夫曼树HT；用w为前n个结点的权值赋值；后面的结点权值初始为0。这些结点的双亲和孩子皆为0。 [建赫夫曼树HT] i从n+1到m，执行如下循环： 在HT[1..i-1]中选择父亲信息为0且权值最小的两个结点s1和s2，以i作为它们的双亲，并修改他们的双亲信息为i，修改i的孩子信息为s1和s2，i的权重为s1和s2的权重之和。 [求赫夫曼编码HC] 分配n个字符编码的头指针向量HC； i从1到n，执行如下循环： 沿着i的父亲信息上溯，直到根： 在每一层，如果为左孩子则记下‘0’； 在每一层，如果为右孩子则记下‘1’； 把上溯过程得到的字符串逆向写入HC[i]。 [算法结束] 这样由叶子到根，逆向处理，可以得到赫夫曼编码HC。其中，HC的前n个分量表示叶子结点，其余结点为非终端结点，最后一个结点为根结点。 另外，还可以由根出发，遍历整棵赫夫曼树，求得各个叶子所表示的字符的赫夫曼编码，如算法6.13，其中借用结点的weight域来作结点状态标志(weight为0表示向左，1表示向右，2表示退回)： 例6－2给出了赫夫曼编码的一个示例。P148 Status InOrderTraverse(BiTree T, Status (*Visit) (TEle