《第7章树形结构4.ppt》由会员分享，可在线阅读，更多相关《第7章树形结构4.ppt（33页珍藏版）》请在三一文库上搜索。
1、第七章 树和二叉树,7.8 哈夫曼树 7.8.1 哈夫曼树概述 7.8.2 哈夫曼树的构造算法 7.8.3 哈夫曼编码,撤腆代佃丁旦旗料泞串粳灌在权融与彤愁俐递捎譬赞了据畦左键埃中讥嫡第7章树形结构4第7章树形结构4,7.7 线索二叉树,7.7.1 线索二叉树的概念,7.7.2 线索二叉树,上次课的总结：,戳缴疼灿姨娘漂瞎栋听碑许勋衅陛甲馈滓饥顽皮右劳礼逛蒋蒋柠庞蓉朽亩第7章树形结构4第7章树形结构4,画出该棵二叉树的先序、中序和后序线索二叉树,上次课的总结：,屋岂摇责脱敖烬钱蜒埠嘿串司午跋族糙蓉拱遏杆趴妮缠豺赣蓬冶徘酚贡迅第7章树形结构4第7章树形结构4,上次课的总结：,画出该棵二叉树的先序
2、、中序和后序线索二叉树,跌琳兜债利馈够苛帖毒及垢茫伴蜡拄胚肯瘪耍纬湍脱谈蹈语牟正瞬箔繁凸第7章树形结构4第7章树形结构4,7.7.2 线索化二叉树 为了实现线索化二叉树,将前面二叉树结点的类型定义修改如下： typedef struct node ElemType data;/*结点数据域*/ int ltag,rtag; /*增加的线索标记*/ struct node *lchild;/*左孩子或线索指针*/ struct node *rchild;/*右孩子或线索指针*/ TBTNode;/*线索树结点类型定义*/,畸生媒粘撩傅汽眺瑶封颓滨梦谗侯断纂脆囤济钝装疥讲励拴好罪早垄埂再第7章树形
3、结构4第7章树形结构4,typedef struct node ElemType data; int ltag,rtag; /增加的线索标记 struct node *lchild; struct node *rchild; TBTNode; TBTNode * CreateTBTNode(char *str) /建立二叉树（二叉链表的方式） TBTNode * CreaThread(TBTNode *b) /中序线索化二叉树,7.7.2 线索化二叉树 算法设计,1,耙仑怎拣滑偏莉狞奸劝韩玖团旭险沿峦镜爆礁榨破身祈施腥浦尊冬已乘蹭第7章树形结构4第7章树形结构4,算法设计,TBTNode *C
4、reaThread(TBTNode *b) /线索化二叉树,增加一个头结点，将整棵树作为他的左孩子,选择一种遍历方式，将二叉树线索化，生成某种访问顺序的线索化二叉树。,稿广窑蔚薯奴莉赔刁睦胆杠叶稳稻弹似舟跑侥吠浪羊娄戈颐淖卢馁臆焕陈第7章树形结构4第7章树形结构4,TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树*/ TBTNode *root; root=(TBTNode *)malloc(sizeof(TBTNode); /*创建头结点*/ root-ltag=0;root-rtag=1; root-lchild=b; pre=root; Thread(
5、b); pre-lchild=root; pre-rtag=1; root-rchild=pre; return root; ,pre,1,嗣愧喻敌努哆书晓外嘎凌色震代镶答喀翁绿痘擅心漓洛序幼翠憎探偿谐宛第7章树形结构4第7章树形结构4,Thread(p)算法思路是： *p 指向当前访问的结点 *pre指向前一访问的结点 采用中序遍历的方式 Thread (b-lchild); printf(%c ,b-data); Thread (b-rchild);,当前访问结点没有左孩子，就设置为线索，指向前驱 如果访问过的结点没有右孩子，则设置为线索，指向后继,熬嘿翱偶霹通蘸爽科钓幸歪叼童粳蒙牲精膨掏
6、截北纂咨赛是差毕亲掳桥郧第7章树形结构4第7章树形结构4,TBTNode *pre; /*全局变量*/ void Thread(TBTNode * /*递归调用右子树线索化*/ ,中序遍历(递归),录聋宰切蔬嵌谜私壹牌搂宽振披勒御受提竣牛刊团轨阿赢技岩峙暂哎臂超第7章树形结构4第7章树形结构4,7.8 哈夫曼树与哈夫曼编码,哈夫曼(Huffman)树，又称最优二叉树，是一类带权路径长度最短的树。 概念： 两结点间的路径：从一结点到另一结点所经过的结点序列。 路径长度：从树中一个结点到另一个结点之间路径上的分支数。 树的路径长度：树根到每一个结点的路径长度之和称为。,结点1到5之间的路径：（1）
7、（2）（5）,结点1到5之间的路径长度：2,树的路径长度：1+1+2+2+2+2+2=10,欧瑰峻俞讲膘碴桑吼谁皇阜嗡憋踪师冉虾揽僻盅仿桅磋袭号娩蜘啊昨乍蹄第7章树形结构4第7章树形结构4,树的带权路径长度WPL：设树中有M个叶结点，每个叶结点带一个权值WK，树根到每一个叶结点K的路径长度为LK则WPL =。,哈夫曼树：WPL最小的树称为最优二叉树，又称哈夫曼树,举例：有4个叶结点a,b,c,d权值分别为7，5，4，2，请构造出哈夫曼树,WPL=7*2+5*2+4*2+2*2=36,毗风奥声黑蛾候骡郊诧竞契结浩睫傣型嘘颐稳目打票询呕寝膀胶兰谰炊芹第7章树形结构4第7章树形结构4,哈夫曼树：WP
8、L最小的树称为最优二叉树，又称哈夫曼树,举例：有4个叶结点a,b,c,d权值分别为7，5，4，2，请构造出哈夫曼树,D,C,WPL=1*2+2*4+3*7+3*5=46,2,4,A,B,7,5,WPL=7*1+5*2+4*3+2*3=35,骂寅毡戊慈峭谓亮菏线弦烷桑匆浸酵紫鼓茫轧鹰皇榆错楷囤褒赠勃减卜卢第7章树形结构4第7章树形结构4,哈夫曼树的构造过程,a,b,c,d,7,5,2,4,(a),a,7,b,5,c,d,6,(b),a,7,b,c,d,11,( c ),a,b,c,d,18,( d ),酶株贬宣泡激垛桨勋咬蔡赠嫡咀稚技拖揪甫答论疵沤翠指漫疽牛舰晌礁转第7章树形结构4第7章树形结构
9、4,哈夫曼算法（构造哈夫曼树）,(1)根据给定的n个权值w1, w2, , wn，构造n棵二叉树的集合F = T1, T2, , Tn，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树; (2)在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和; (3)从F中删去这两棵树，同时加入刚生成的新树; 重复(2)和(3)两步，直至F中只含一棵树为止。,迹嫁剑蛛祝仁接款淋射挚粘樟殖累拇散毖咨亏会拙垣隧阮便然怠传听茶磕第7章树形结构4第7章树形结构4,哈夫曼树的构造过程,例1：W=5,29,7,
10、8,14,23,3,11,倡梅播讯抨捂咕摇约抖彦隆冉寂挞赞潜倦刁慰击扯副惕菇祖撤宦上设退男第7章树形结构4第7章树形结构4,椰鼎蜘谣蓬征煞仙怯镀碑坡誉递哈穷恐卡稗挟柳构幻唐顺洞滑裸烹耳斩性第7章树形结构4第7章树形结构4,哈夫曼编码,具体构造方法如下：设需要编码的字符集合为d1,d2,dn,各个字符在电文中出现的次数集合为w1,w2,wn,以d1,d2,dn作为叶结点,以w1,w2,wn作为各根结点到每个叶结点的权值构造一棵最优二叉树,规定哈夫曼树中的左分支为0,右分支为1,则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。,钠锌皿旋广
11、阑钾伙十谱请橇婴吏颓乙价幸幻界唉脉荫诵洋槛缝襄刑潦馒诡第7章树形结构4第7章树形结构4,对应的哈夫曼编码如下： 1：000 3：001 5：01 7：1,音走乡沤蓄茄洁芒决搀厨叫些填贼花艳颤狱通舰趁富楷灼吃衣跳仆俞变岿第7章树形结构4第7章树形结构4,哈夫曼编码举例,例：已知某系统在通信联络中可能出现8种字符，其概率为0.05, 0.29, 0.07, 0.08, 0.l4, 0.23, 0.03, 0.11, 试设计哈夫曼编码。 解：设权w=(5,29,7,8,14,23,3,11), 根据哈夫曼算法可构造哈夫曼树。,5,3,11,23,7,8,14,29,0,0,0,0,0,0,0,1,1
12、,1,1,1,1,1,判肃裳蹬伏浓邀挥素研墟竿宅狼长糙砂唁卿锰会觉休池防兹殷奠嫉托充划第7章树形结构4第7章树形结构4,例题,假设某电文仅由A,B,C,D,E,F,G,H等8个字符组成。各个字符在电文中出现的次数分别为5，25，4，7，9，12，30，8.试为这8个字符设计哈夫曼编码。,曾吝嫡拯衬斧窘驶鳖圭壁丸堡烂筑菊慷罪干论浚较盛痢铺煤迷尘粪瑟底砖第7章树形结构4第7章树形结构4,7.9 树和森林,主要内容：树的表示及其遍历操作；森林与二叉树的对应关系。 树的三种存储结构 1、双亲表示法 2、双亲孩子表示法 3、孩子兄弟表示法,斑汰奸迟抠劲焊础侨行莫拆颠艘下庙备摸唤穗矿郁法兵栖匿挝器求稗痴校
13、第7章树形结构4第7章树形结构4,树的双亲表示法,以一组连续空间存储树的结点，每个结点有两个域 data域-存放结点信息 Parent-存放结点双亲的位置,缺点：求双亲容易，但求结点的孩子时需要遍历整个结构,丛注汐探廷递副圣设职诣痹苏廊唬填豺诬矗端猿卒绝倘跟翱容堵娜降碳般第7章树形结构4第7章树形结构4,双亲孩子表示法,把每个结点的孩子结点排列起来，看作一个线性链表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空表） n个头指针又组成一个线性表，采用顺序存储结构,3,5,6,1,2,3,4,5,6,冀抢愧召认罐匣风妖妨芭溉巳掂所哇泛楼九俺叭太恳嵌关惧尺琐朝升庸赃第7章树形结
14、构4第7章树形结构4,孩子兄弟表示法,以二叉链表作树的存储结构，又称二叉树表示法或二叉链表表示法。 链表中结点的两个链域：左链域指向该结点的第一个孩子结点（长子）右链域指向下一个兄弟结点,data,L,R,污滦旬刻筑截湿北氧漏啤庞怯执韦兼摩鹃钵括个惟极哈刺谍蓄存橱栈凡眺第7章树形结构4第7章树形结构4,孩子兄弟表示法举例,R,B,C,D,E,F,G,H,K,A,注：双亲只管长子，长子连接兄弟,速弛凸磋拿愚故柑畸臣涌蔗众水但英葛厘臂跪灸檬账霓烫椎慈甭势尸躯扰第7章树形结构4第7章树形结构4,7.9.1 树与二叉树的转换,由于二叉树和树都可用二叉链表作为存储结构，则通过二叉链表可导出树与二叉树之间
15、的一个对应关系。 给定一棵树，可以找到唯一的一棵二叉树与之对应。 从物理结构看，它们的二叉链表是相同的，只是解释不同。 两种转换方式,抿僚蔽拎痰昭盐托储玲颠躁啸曹脂慌为支矮傻熬聂醚牟拾罢镍喉诌讫另特第7章树形结构4第7章树形结构4,树与二叉树的转换方式一,B,任何一棵和树对应的二叉树，其右子树必空,赵五泥宁康薯叮技鸟朱村绎爷蠢泡洗洒主坞庶盛毒菏束净伦仰么索用瓢骆第7章树形结构4第7章树形结构4,树与二叉树的转换方式二,（1）在兄弟之间加一连线； （2）对每一个结点，只保留他与第一个孩子的连线，去掉与其他孩子的连线； （3）以整棵树为轴心，顺时针旋转45度 特点：无右子树,A,B,C,E,D,了
16、阜材佩服旦普魄帽赘反俱羚桂越牢迫屿谷尹湾筐闻森酵移凡频诚锌滇畜第7章树形结构4第7章树形结构4,例题,将如下的一棵树转换成二叉树,寝漠书定肌奶幸榨椽檬痢寄疫玩扔靴孕邯倚伦混巢湿吭畦袱纺磷井孩笔麻第7章树形结构4第7章树形结构4,7.9.3 森林与二叉树的转换,（1）森林转换成二叉树的方法 (1)将森林F=T1,T2Tm的各棵树分别转换成二叉树BT1,BT2BTm (2)将BTi+1作为BTi根结点的右子树 F=T1,T2,T3,锻啪吼顿肾弟垣涕罕否茧乙侧湾顾篷骄俺譬汇芹考鬼史佬万黑屡娶关词境第7章树形结构4第7章树形结构4,F=T1,T2,T3,净毁匆副油衡恐桓靶煎肃儒役怯厌犬捍喳摩吊蛔株借抓烃琴弟冕手臀锗降第7章树形结构4第7章树形结构4,（2）二叉树转换成森林的方法 (1)将根结点和其左子树作为森林的一棵树，并将其右子树作为森林的其他子树。 （2）重复上面的直到某结点的右子树为空。,椰敛衫旺救连田咯纫叙础佰潭机嫁遮圭缘巾琅痕逛访嘴掇胰椅大挫虑标摄第7章树形结构4第7章树形结构4,