第六章树和二叉树-2

《第六章树和二叉树-2》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、6.4线索二叉树6.4.1线索二叉树定义前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~线索：指向前驱或后继结点的指针称为~线索二叉树：加上线索的二叉链表表示的二叉树叫~线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~在有n个结点的二叉链表中必定有n+1个空链域在线索二叉树的结点中增加两个标志域ltag:若ltag=0,left域指向左孩子；若ltag=1,left域指向其前驱rtag:若rtag=0,right域指向右孩子；若rtag=1,right域指向其后继结点定义：leftltagdatartagrightABCDEABDCET先序序列：ABCDE先序线

2、索二叉树00001111^11ABCDEABDCET中序序列：BCAED中序线索二叉树00001111^11^ABCDEABDCET后序序列：CBEDA后序线索二叉树0000111111^6.4.2中序线索二叉树二叉树的中序线索化中序线索二叉树类中根次序遍历中序线索二叉树【例6.4】构造中序线索二叉树并进行中根次序遍历。6.5哈夫曼编码与哈夫曼树6.5.1哈夫曼编码路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的~路径长度：路径上的分支数树的路径长度：从树根到每一个结点的路径长度之和树的带权路径长度：树中所有带权结点的路径长度之和二叉树的带权外路径长度哈夫曼树定义为带权外路径长度最

3、短的二叉树。哈夫曼树不唯一构造哈夫曼树1、根据给定的n个权值{w1，w2，……，wn}构成n棵二叉树的集合F={T1，T2，……，Tn}，其中每棵二叉树Ti中都有一个权值为wi的根结点，其左右子树均空。2、在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。3、在F中删除这两棵树，同时将新得到的二叉树加入F中。4、重复2和3，直到F只含一棵树为止。这棵树便是哈夫曼树。例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118例w={5,29,7,8,14,23,3,11}51429782331

4、114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100哈夫曼编码所谓编码是指将文件中的每个字符均转换为一个惟一的二进制位串，而解码则相反，是将二进制位串转换为对应的字符。例：假设待压缩的数据文件中共有100000个字符，这些字符均取自字符集C={a，b，c，d，e，f}，其中每个字符在文件中出现的次数（简称频度）如表所示。定长编码：300000位变长编码：（451+133+12

5、3+163+94+54）1000=224000位思考：变长编码的特点。字符abcdef频度（单位：千次）4513121695概率0.450.130.120.160.090.05定长编码000001010011100101变长编码010110011111011100Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列例要传输的字符集D={C,A,S,T,;}字符出现频率w={2,4,2,

6、3,3}CS3364224814T;A00110110T:00;:01A:10C:110S:111译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束例电文是{CAS;CAT;SAT;AT}其编码“11010111011101000011111000011000”电文为“1101000”译文只能是“CAT”CS3364224814T;A00110110T:00;:01A:10C:110S:111Huffman树应用最佳判定树等级分数段比例ABCDE0~5960~6970~798

7、0~8990~1000.050.150.400.300.10a<60a<90a<80a<70EYNDYNCYNBYNA70a<80a<60CYNBYNDYNEYNA80a<9060a<70EADBCa<80a<70a<60a<90EYNDYNCYNBYNA6.6树的表示6.6.1树的存储结构孩子链表孩子兄弟链表6.6.2树的遍历树的先根遍历算法描述如下：访问根结点。按照从左到右的次序先根遍历