数据结构与算法-树(2).ppt

《数据结构与算法-树(2).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.5二叉树的应用一、哈夫曼树——带权路径长度最短的树1、定义（Huffman树）路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的~路径长度：路径上的分支数树的路径长度：从树根到每一个结点的路径长度之和树的带权路径长度:树中所有带权结点的路径长度之和Huffman树——设有n个权值{w1,w2,……wn}，构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi,则wpl最小的二叉树叫~例有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2

2、=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=352、构造Huffman树的方法——Huffman算法构造Huffman树步骤根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树，令其权值为wj在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树例1a7b5c2

3、d4a7b5c2d46a7b5c2d4611a7b5c2d461118例2w={5,29,7,8,14,23,3,11}51429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100Huffman算法实现一棵有n个叶子结点的Huffman树有2n-1个结点采用顺序存储结构——一维结构数组

4、结点类型定义typedefstruct{intdata;intpa,lc,rc;}JD;lcdatarcpa12345670000000752400000000000000000(1)lcdatarcpa12345670000300752460000004000055000k(2)lcdatarcpa123456700003207524611000004500655600k(3)lcdatarcpa1234567000032175246111800004567655670k(4)二、Huffman树应用1、最佳判

5、定树等级分数段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.10a<60a<90a<80a<70EYNDYNCYNBYNA70a<80a<60CYNBYNDYNEYNA80a<9060a<70EADEC2、Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序

6、列例要传输的字符集D={C,A,S,T,;}字符出现频率w={2,4,2,3,3}CS3364224814T;A00110110T:00;:01A:10C:110S:111译码：从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束例电文是{CAS;CAT;SAT;AT}其编码“11010111011101000011111000011000”电文为“1101000”译文只能是“CAT”CS3364224

7、814T;A00110110T:00;:01A:10C:110S:111三、线索二叉树定义：前驱与后继：在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为~线索：指向前驱或后继结点的指针称为~线索二叉树：加上线索的二叉链表表示的二叉树叫~线索化：对二叉树按某种遍历次序使其变为线索二叉树的过程叫~实现在有n个结点的二叉链表中必定有n+1个空链域在线索二叉树的结点中增加两个标志域lt:若lt=0,lc域指向左孩子；若lt=1,lc域指向其前驱rt:若rt=0,rc域指向右孩子；若rt=1,rc域指向其后继结点定

8、义：typedefstructnode{intdata;intlt,rt;structnode*lc,*rc;}JD;lcltdatartrcABCDEABDCET先序序列：ABCDE先序线索二叉树00001111^11ABCDEABDCET中序序列：BCAED中序线索二叉树00001111^11^ABCDEABDCET后序序列：CBEDA后序线索二叉树000011111