五章树和二叉树

《五章树和二叉树》由会员分享，可在线阅读，更多相关《五章树和二叉树（45页珍藏版）》请在金锄头文库上搜索。

1、第五章第五章 树和二叉树树和二叉树红颓贝蹲淖昨端不抿弊碉串埔迈沈浩艳妇埠抿韶犊了潮企馆敲廊素研凸蛰五章树和二叉树五章树和二叉树9/21/20241 二叉树在一般情况下无法直接找到某结点在二叉树在一般情况下无法直接找到某结点在某种遍历序列中的前驱和后继结点。若增加指针某种遍历序列中的前驱和后继结点。若增加指针域来存放前驱和后继结点信息，将大大降低存储域来存放前驱和后继结点信息，将大大降低存储空间的利用率（密度）。考察空间的利用率（密度）。考察 n n 个结点的二叉树，个结点的二叉树，其中有其中有 n+1 n+1 个空指针域，它们可以被用来存放个空指针域，它们可以被用来存放“线线索索”加了线索的二

2、叉树称为线索二叉树。加了线索的二叉树称为线索二叉树。一、线索二叉树一、线索二叉树磷衙咸编隧俯叔尉刃厦徊浇疆唾服譬赌景究茂怜魁爬糊瓶禾罐父挂鞭蜕泥五章树和二叉树五章树和二叉树9/21/20242线索二叉树结点的描述线索二叉树结点的描述typedef int datatype;typedef struct node int ltag,rtag; datatype data; struct node *lchild,*rchild; bithptr;bithptr *pre;lchildltagrtagdatarchild标志位如果为标志位如果为0，表示指针指向孩子，表示指针指向孩子结点，为结点，为

3、1表示指针为线索表示指针为线索涵院抠纸拜原厦巍隅瘪酮已藩诊火溃输糖例躯钧仑艇买韦锡枯瞻磺澈尸鞍五章树和二叉树五章树和二叉树9/21/202430 A 00 B 00 E 11 C 11 D 11 F 00 G 01 H 11 I 1NULLNULLt锌徒坠审茨勒豢活靠亥至惋寸搀它缆空庞殃然诈特惧剐岂泳儿和酋贩告腑五章树和二叉树五章树和二叉树9/21/20244中序线索化算法中序线索化算法INTHREAD(bithptr *p,bithptr *pre)/ p为当前结点，为当前结点，pre为为p的前驱结点，开始调用时的前驱结点，开始调用时p为根结点指针，为根结点指针，pre为为NULL if (

4、p!=NULL) INTHREAD(p-lchild,pre); / 左子树线索化左子树线索化 / 若当前结点的左子树为空，则建立指向其前驱结点的前驱线索若当前结点的左子树为空，则建立指向其前驱结点的前驱线索 if (p-lchild = = NULL) p-ltag1; p-lchildpre; else p-ltag0; / 若前驱结点不为空，且其右孩子为空，则建立该前驱结点指向当前结点的后续线索若前驱结点不为空，且其右孩子为空，则建立该前驱结点指向当前结点的后续线索 if (pre!=NULL & pre-rchild = = NULL) pre-rtag1; pre-rchildp;

5、else p-rtag0; prep; / 中序向前遍历一个结点中序向前遍历一个结点 INTHREAD(p-rchild, pre); 辊猫陕趋胆藐珊溪失哺成伞握怠涌脊占绢敲蛊溜丫栋摹叁蓉辫搽和绩棺鳖五章树和二叉树五章树和二叉树9/21/202451 1、若、若 *p *p 的右子树为空，则的右子树为空，则 p-rchild p-rchild 为右线为右线 索，直接指向索，直接指向 *p *p 的中序后继结点。的中序后继结点。2 2、若、若 *p *p 的右子树非空，则的右子树非空，则 *p *p 的中序后继必是的中序后继必是 其右子树中第一个遍历到的结点，也就是从其右子树中第一个遍历到的结点

6、，也就是从 *p *p的右孩子开始，沿左指针链往下查找，直的右孩子开始，沿左指针链往下查找，直 到找到一个没有左孩子的结点为止。到找到一个没有左孩子的结点为止。中序线索二叉树中，查找指定结点中序线索二叉树中，查找指定结点*p*p的中序后继结点的中序后继结点爪舵湘棕烃打僧履闹柬畅甘姬狰桥泊幼染葡田夜劝雅咽领梯聊濒义零惜本五章树和二叉树五章树和二叉树9/21/20246pR1R2Rk最左下结点最左下结点怎枝暖孝淹诛楼洒瓜藐嗜涡配嘛病搽辜郭狸曰走宣链漓葱眉聘氏堤捻她诛五章树和二叉树五章树和二叉树9/21/20247中序线索二叉树中求中序后继结点的算法中序线索二叉树中求中序后继结点的算法bithptr

7、 *INORDERNEXT(bithptr *p) bithptr *q; if (p-rtag=1) return(p-rchild); else qp-rchild; while (q-ltag=0) qq-lchild; return(q); 隙崖喳幕堰泄强掩爆眶蹄覆刚片伯恶孝霹桨尺美文枕根赦鲍樊揣败盗磕糕五章树和二叉树五章树和二叉树9/21/202481 1、若、若 *p *p 的左子树为空，则的左子树为空，则 p-lchild p-lchild 为左线为左线 索，直接指向索，直接指向 *p *p 的中序前驱结点。的中序前驱结点。2 2、若、若 *p *p 的左子树非空，则从的左子树非

8、空，则从 *p *p 的左孩子出发的左孩子出发 ，沿右指针链往下查找，直到找到一个没有右，沿右指针链往下查找，直到找到一个没有右 孩子的结点为止。孩子的结点为止。中序线索二叉树中，查找指定结点中序线索二叉树中，查找指定结点*p*p的中序前驱结点的中序前驱结点腊缺羞檬堑消褥晨歼陶盆更社宣邯恰望殴确资挨寺箩铱看模慌嫁哲纽延废五章树和二叉树五章树和二叉树9/21/20249pR1R2Rk最右下结点最右下结点入皋侯抬史畔豺您蚁铅侵搪属键贴韧汛瓦碌舱檬兢杨千醋仿汁驭豺澳面句五章树和二叉树五章树和二叉树9/21/202410线索二叉树的遍历算法线索二叉树的遍历算法TRAVERSEINTHREAD(bith

9、ptr *p) if (p!=NULL) while (p-ltag=0) pp-lchild; do printf(“t%dn”,p-data); pINORDERNEXT(p); while(p!=NULL); 您伦硝后板滥诛骨拒妹触蔬犹这辩邯揣隐聚垫腊惩玩幢夸卒玉撬浑死种押五章树和二叉树五章树和二叉树9/21/202411线索二叉树的结点插入算法线索二叉树的结点插入算法INSERTRIGHT(bithptr *p,bithptr *q) bithptr *s; sINORDERNEXT(p); q-ltag1; q-lchildp; q-rtagp-rtag; q-rchildp-rch

10、ild; p-rtag0; p-rchildq; if (s!=NULL)&(s-ltag=1) s-lchildq;陆呼指卞苗怔殖寨界伎涡父萌讨枕勿碱吧露腐矢划攒锚乙状貉您尝烙磐相五章树和二叉树五章树和二叉树9/21/202412 二叉排序树又称为二叉查找树，其定义为：二叉排序树又称为二叉查找树，其定义为：二叉排序树或者是一棵空树，或者是具有如下性二叉排序树或者是一棵空树，或者是具有如下性质的二叉树：质的二叉树：1 1、若它的左子树非空，则左子树上所有结点的值、若它的左子树非空，则左子树上所有结点的值 均小于根结点；均小于根结点；2 2、若它的右左子树非空，则右子树上所有结点的、若它的右左子

11、树非空，则右子树上所有结点的 值均大于根结点；值均大于根结点；3 3、左、右子树本身又各是一棵二叉树。、左、右子树本身又各是一棵二叉树。二、二叉排序树二、二叉排序树盘臂孕阎寺蛆彝绽季位赤莲玩疾脐纲瑞破斋幢踏骨析皮姨叙漫误兵冶愤遵五章树和二叉树五章树和二叉树9/21/202413caozhaodingchenwangmaxiaduni滚膘棋蛹霖晴诧荣韧并坐熄拖午戮忻莉拔识仁胎唁介老菱渺稿夜袋拨脂鞋五章树和二叉树五章树和二叉树9/21/202414二叉排序树结点的结构描述二叉排序树结点的结构描述typedef struct node datatype data; struct node *lchi

12、ld,*rchild; bitree;骚神叼棉粒飘丰娘桓椰喂匿监琴羔茬齿狸锋蘸骋曾畦遗景掣臃置器扑刽羚五章树和二叉树五章树和二叉树9/21/202415二叉排序树的结点插入二叉排序树的结点插入/ 向一个二叉排序向一个二叉排序树中插入一个中插入一个结点点svoid INSERT(bitree *b, bitree *s) if ( b = NULL ) b=s; else if ( s-data = b-data ) return; / 不做任何插入操作不做任何插入操作 else if ( s-data data ) INSERT(b-lchild, s); / 将将s插入到左子树中插入到左子树

13、中 else if ( s-data b-data ) INSERT(b-rchild, s); / 将将s插入到右子树中插入到右子树中 诸苍哄收甲倍阶队写工褥茵衰构废按潮宙探窜囊占告包微丧善弹执业钠卷五章树和二叉树五章树和二叉树9/21/202416二叉排序树的生成二叉排序树的生成void CREAT(bitree *b) int x; bitree *s; b=NULL; do scanf(“%d”,&x); / 读入一个整数读入一个整数 s=(bitree *)malloc(sizeof(bitree); / 产生一个树结点产生一个树结点 s-data=x; s-lchild=NULL;

14、 s-rchild=NULL; INSERT(b,s); / 插入该结点插入该结点 while(x!=-1);祁蛋热蜒弛浓抑声惫帽尹漆表舷瘤但董团锐玖帆证缨慌区贩猿兆禾奠闪潮五章树和二叉树五章树和二叉树9/21/202417452453122890关键字输入顺序：关键字输入顺序：45，24，53，12，28，90味匠熏漳亿机胆妄彻缄孝滇版踞对仑逛脂恋示潍遮流丹龚走肖肩侈珐透缚五章树和二叉树五章树和二叉树9/21/202418二叉排序树的结点删除二叉排序树的结点删除(被删除结点无左孩子被删除结点无左孩子)qpqpp是左孩子是左孩子p是右孩子是右孩子点糖蹿乞渠便秤龚壤俩崎喜来遍白葡在洛蜂咱弄错百试

15、阔们蝎蚊杂昨顷尧五章树和二叉树五章树和二叉树9/21/202419二叉排序树的结点删除二叉排序树的结点删除(被删除结点有左孩子被删除结点有左孩子)qpqpp是左孩子是左孩子p是右孩子是右孩子酪贤惭吁李铺庶俄盼决窗遂血羞獭辩邯课胁敏棺坐平贴静京砾怨妖牲痰非五章树和二叉树五章树和二叉树9/21/202420二叉排序树的结点删除算法二叉排序树的结点删除算法/ 在二叉排序树在二叉排序树b中删除一个数据域为中删除一个数据域为x的结点的算法函数的结点的算法函数void DELNODE(bitree *b, int x) bitree *p, *q, *r, *t; p=b; / p指向待比较的结点指向待比

16、较的结点 q=NULL; / q指向指向p的前驱结点的前驱结点 while (p!=NULL & p-data!=x) if (x data) q=p; p=p-lchild; else q=p; p=p-rchild; if (p=NULL) printf(“未发现数据域为未发现数据域为%d的结点的结点n”, x); else if (p-lchild=NULL) / 被删结点无左子树被删结点无左子树 if (q=NULL) t=p-rchild; else if (q-lchild=p) q-lchild=p-rchild; else q-rchild=p-rchild; 们枣逊奖盈卒把宣

17、钠韵挑耕矾串陶田半铺嫡评洽借赋畦时环霖仑耕漆闯吕五章树和二叉树五章树和二叉树9/21/202421 else / 被删结点有左子树被删结点有左子树 / 查找被删结点的左子树中的最右结点，即刚好小于查找被删结点的左子树中的最右结点，即刚好小于x的结点的结点 r=p-lchild; while (r-rchild != NULL) r=r-rchild; / 被删结点的右子树作为被删结点的右子树作为r的右子树的右子树 r-rchild=p-rchild; / 被删结点的左子树根代替被删结点被删结点的左子树根代替被删结点 if (q=NULL) t=p-lchild; else if (q-lchi

18、ld=p) q-lchild=p-lchild; else q-rchild=p-lchild; 怜偷樟宣炎遭潘牺敲迷煌朗近翰膀盖啤讥铝薪揪筐髓辫分磋琐颤图欲驰铸五章树和二叉树五章树和二叉树9/21/202422二叉排序树的查找二叉排序树的查找bitree *SEARCH(bitree *b, int x) if (b=NULL) return (NULL); else if (b-data = x) return (b); if (b-data x) return (SEARCH(b-lchild); else return (SEARCH(b-rchild); 鞠涤典哦撇伏持沃障兹嗡剔掷话

19、吗告厩贸裳任彬秆桐颖趴辟梢各衔庆烂香五章树和二叉树五章树和二叉树9/21/202423一棵一棵 m 阶的阶的B-树满足下列条件：树满足下列条件：1 1、每个结点、每个结点至多有至多有m个个孩子；孩子；2、根结点至少有两个孩子（唯一例外的是只包含一个根根结点至少有两个孩子（唯一例外的是只包含一个根 结点的结点的B-树）；树）；3、除根结点和叶结点外，其它每个结点至少有除根结点和叶结点外，其它每个结点至少有 m/2 个个 孩子；孩子；4、有、有n+1个孩子的非叶结点恰好包含个孩子的非叶结点恰好包含n个关键字个关键字 (A0 , K1 , A1 , K2 , A2 , Kn, An);5、所有叶结点

20、在同一层，叶结点不包含任何关键字信息。、所有叶结点在同一层，叶结点不包含任何关键字信息。三、三、B- -树树兹揉痴杖倚栗钩择连痊汹搭吩喇枕策承呕碌除口同淳素其炯洼用诫糜峨忙五章树和二叉树五章树和二叉树9/21/202424357045112236392490560631670008040052110135142212237240279378381388393396400435471492502553叠舰栽看坟皮立斤逗吉致蒂翅劲国抓崩宏圃道操鼠铃立扦蚌锦贞益沾赌锥五章树和二叉树五章树和二叉树9/21/202425 在在B-B-树中包含树中包含j j个关键字，个关键字，j+1j+1个指针的个指针的

21、结点，一般表示形式为：结点，一般表示形式为：A0 , K1 , A1 , K2 , A2 , Kj , Aj伶墟受康避统育腆翼谴灵允缺粥驮奄催四您狰蒋韩糟寐弛世讣冗新滴算猛五章树和二叉树五章树和二叉树9/21/202426B-树的运算树的运算1、查找、查找2、插入、插入 132 142 212 132 137 142 212 插入137变为纫专握痕谍泵坦仿孤莱乍水劳燥萨垛惹乎兔氦吓厦抑迟浦猪株灰佯嘶扇壮五章树和二叉树五章树和二叉树9/21/202427357490392400453460471393396560631670响冈轻琢巴室躲乖框灰生浇翻深菩发控哥嘲距贰躇号超通秋赞晤迈舅卑邢五章树和

22、二叉树五章树和二叉树9/21/2024283、删除、删除052112236008040052110135142212237240279协驳豢诀愚壹捻捧速乾酉匡玻漂惺观孰缄晒茶鸿琳揽丁讯烯疵墙头豆未呈五章树和二叉树五章树和二叉树9/21/202429052135236008040110112142212237240279052236008040110135142212237240279栏蠕苗菏棚椰憋冷又钾石慕贰逼踌挨省栋淌抹致坪猛忽惺砍有细途南舔藉五章树和二叉树五章树和二叉树9/21/202430具有不同路径长度的二叉树具有不同路径长度的二叉树四、赫夫曼树 (Huffman Tree)路径长度路

23、径长度 (Path Length) 两个结点之间的路径长度是连接两结点的路径两个结点之间的路径长度是连接两结点的路径上的分支数。树的路径长度是从树根到每一结点上的分支数。树的路径长度是从树根到每一结点的路径长度之和。的路径长度之和。甲承规付堪沼岁态良介邵刑龟赏笼得恃榜咀皂省呵吏王愉彩辕扳污惶寸掀五章树和二叉树五章树和二叉树9/21/202431带权路径长度带权路径长度 ( Weighted Path Length, WPL )树的带权路径长度是树的各叶结点所带的权值树的带权路径长度是树的各叶结点所带的权值与该结点到根的路径长度的乘积的和。与该结点到根的路径长度的乘积的和。必爷橡悟疽篡厩绷卞卿葬

24、列木虫惶条格款柏搐殖才迸搅气僚锭吕得侍微砌五章树和二叉树五章树和二叉树9/21/202432具有不同带权路径长度的二叉树具有不同带权路径长度的二叉树赫夫曼树赫夫曼树 带权路径长度达到最小的二叉树即为赫夫曼带权路径长度达到最小的二叉树即为赫夫曼树。在赫夫曼树中，权值大的结点离根最近。树。在赫夫曼树中，权值大的结点离根最近。训佬暗绞仍五圈毛足睹本彤骏溯者基砂祈钻铰三馅肩泰釉谩掖友霉袋裴涅五章树和二叉树五章树和二叉树9/21/202433三种前缀编码三种前缀编码字符字符概率概率编码编码1编码编码2编码编码3a0.120000001111b0.40001110c0.1501001110d0.08011

25、0011110e0.251001010杨楼烁笆哺燃嵌袖维禽漓动铬琅寓惊邦拎按拐六递酉恃撵拓烩迹式殃眼磨五章树和二叉树五章树和二叉树9/21/202434adceb右婚檄淘英竿搜汇滚荧洪薪那般舅晚括温阁棠吵毯灭景碍坯颓汐听号逮肥五章树和二叉树五章树和二叉树9/21/202435赫夫曼算法赫夫曼算法 (1) 由给定的由给定的n个权值个权值w1, w2, , wn，构造具，构造具有有n棵二叉树的森林棵二叉树的森林F = T1, T2, , Tn，其中每，其中每一棵二叉树一棵二叉树Ti只有一个带有权值只有一个带有权值wi的根结点，其左、的根结点，其左、右子树均为空。右子树均为空。 (2) 重复以下步骤

26、重复以下步骤, 直到直到F中仅剩下一棵树为止：中仅剩下一棵树为止： 在在F中选取两棵根结点的权值最小的二叉树中选取两棵根结点的权值最小的二叉树, 做为左、右子树构造一棵新的二叉树。置新的二做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的叉树的根结点的权值为其左、右子树上根结点的权值之和。权值之和。 在在F中删去这两棵二叉树。中删去这两棵二叉树。 把新的二叉树加入把新的二叉树加入F。喉乘眠疮理违努衍劫文坊橙互藉塘婿嘛叫使嵌晾扦溜致廖渗窄锡踢端脚璃五章树和二叉树五章树和二叉树9/21/202436赫夫曼树的构造过程赫夫曼树的构造过程嘴沏峡爪坝逐苔兹颤级唆卓裁淆抄

27、鹰有辟汉谦呢张扶晦隋柯炒揩叶汕宁最五章树和二叉树五章树和二叉树9/21/202437赫夫曼编码赫夫曼编码 主要用途是实现数据压缩。主要用途是实现数据压缩。主要用途是实现数据压缩。主要用途是实现数据压缩。 设给出一段报文：设给出一段报文：设给出一段报文：设给出一段报文： CAST CAST SAT AT A TASACAST CAST SAT AT A TASA 字符集合是字符集合是字符集合是字符集合是 C, A, S, T C, A, S, T ，各个字符出现的频度，各个字符出现的频度，各个字符出现的频度，各个字符出现的频度( (次数次数次数次数) )是是是是 WW 2, 7, 4, 5 2,

28、 7, 4, 5 。 若给每个字符以等长编码若给每个字符以等长编码若给每个字符以等长编码若给每个字符以等长编码 A : 00 T : 10 C : 01 S : 11A : 00 T : 10 C : 01 S : 11则总编码长度为则总编码长度为则总编码长度为则总编码长度为 ( 2+7+4+5 ) * 2 = 36. ( 2+7+4+5 ) * 2 = 36. 若按各个字符出现的概率不同而给予不等长编码，若按各个字符出现的概率不同而给予不等长编码，若按各个字符出现的概率不同而给予不等长编码，若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。可望减少总编码长度。可望减少总编码长度

29、。可望减少总编码长度。 因各字符出现的概率为因各字符出现的概率为因各字符出现的概率为因各字符出现的概率为 2/18, 7/18, 4/18, 5/18 2/18, 7/18, 4/18, 5/18 。肾殖澳缝砍瞳仲动钞幻卧轴爹庭砂切圈魏吱山抛拄霉倒餐寂粟穿栈钵森范五章树和二叉树五章树和二叉树9/21/202438化整为化整为 2, 7, 4, 5 ，以它们为各叶结点上的权值，以它们为各叶结点上的权值，建立赫夫曼树。左分支赋建立赫夫曼树。左分支赋 0，右分支赋，右分支赋 1，得赫夫，得赫夫曼编码曼编码(变长编码变长编码)。 A : 0 T : 10 C : 110 S : 111它的总它的总编码

30、长度：编码长度：7*1+5*2+( 2+4 )*3 = 35。比等。比等长编码的情形要短。长编码的情形要短。 总编码长度正好等于总编码长度正好等于赫赫夫曼树的带权路径长夫曼树的带权路径长度度WPL。 赫赫夫曼编码是一种夫曼编码是一种前缀编码。解码时不会前缀编码。解码时不会混淆。混淆。赫夫曼编码树赫夫曼编码树鹊孽阳浮摸斜千夫衔桩殉玄者洁白是冷还胃辣壕逾续皿吵化叮壳佬直朴遵五章树和二叉树五章树和二叉树9/21/202439赫夫曼树的存储结构赫夫曼树的存储结构#define n 7#define m 2*n-1typedef struct int weight; int lchild,rchild,

31、parent; hufmtree;hufmtree treem+1;狡向哮从岔右棘贰端穷夹耗襟腋桓儒浸酒钝钞冲沉凋椿贱转瞻穷灯捧拆喉五章树和二叉树五章树和二叉树9/21/202440赫夫曼树的构造算法赫夫曼树的构造算法赫夫曼树的构造算法赫夫曼树的构造算法HUFFMAN(hufmtree tree)HUFFMAN(hufmtree tree)HUFFMAN(hufmtree tree)HUFFMAN(hufmtree tree) int i,j,p1,p2; int i,j,p1,p2; int i,j,p1,p2; int i,j,p1,p2; int small1,small2,f; int

32、 small1,small2,f; int small1,small2,f; int small1,small2,f; for (i=1;i=m;i+) for (i=1;i=m;i+) for (i=1;i=m;i+) for (i=1;i=m;i+) treei.parent=0; treei.parent=0; treei.parent=0; treei.parent=0; treei.lchild=0; treei.lchild=0; treei.lchild=0; treei.lchild=0; treei.rchild=0; treei.rchild=0; treei.rchild

33、=0; treei.rchild=0; treei.weight=0; treei.weight=0; treei.weight=0; treei.weight=0; for (i=1;i=n;i+) for (i=1;i=n;i+) for (i=1;i=n;i+) for (i=1;i=n;i+) scanf( scanf( scanf( scanf(“ “%d%d%d%d” ”,&f);,&f);,&f);,&f); treei.weight=f; treei.weight=f; treei.weight=f; treei.weight=f; for (i=n+1;i=m;i+) for

34、 (i=n+1;i=m;i+) for (i=n+1;i=m;i+) for (i=n+1;i=m;i+) p1=0; p2=0; p1=0; p2=0; p1=0; p2=0; p1=0; p2=0; small1=MAXVAL; small2=MAXVAL; small1=MAXVAL; small2=MAXVAL; small1=MAXVAL; small2=MAXVAL; small1=MAXVAL; small2=MAXVAL; for (j=1;j=i-1;j+) for (j=1;j=i-1;j+) for (j=1;j=i-1;j+) for (j=1;j=i-1;j+) if

35、 (treej.parent = 0) if (treej.parent = 0) if (treej.parent = 0) if (treej.parent = 0) if (treej.weightsmall1) if (treej.weightsmall1) if (treej.weightsmall1) if (treej.weightsmall1) small2=small1; small2=small1; small2=small1; small2=small1; small1=treej.weight; small1=treej.weight; small1=treej.wei

36、ght; small1=treej.weight; p2=p1; p1=j; p2=p1; p1=j; p2=p1; p1=j; p2=p1; p1=j; else else else else if (treej.weightsmall2) if (treej.weightsmall2) if (treej.weightsmall2) if (treej.weightsmall2) small2=treej.weight; small2=treej.weight; small2=treej.weight; small2=treej.weight; p2=j; p2=j; p2=j; p2=j

37、; treep1.parent=i; treep1.parent=i; treep1.parent=i; treep1.parent=i; treep2.parent=i; treep2.parent=i; treep2.parent=i; treep2.parent=i; treei.lchild=p1; treei.lchild=p1; treei.lchild=p1; treei.lchild=p1; treei.rchild=p2; treei.rchild=p2; treei.rchild=p2; treei.rchild=p2; treei.weight=treep1.weight

38、+ treei.weight=treep1.weight+ treei.weight=treep1.weight+ treei.weight=treep1.weight+ treep2.weight; treep2.weight; treep2.weight; treep2.weight; 矾肪碗言舅妥厉固巫樟盒习吭鸿吵卜煤谍孰叛词蜗粒赖定迪增柒荆猿末炉五章树和二叉树五章树和二叉树9/21/202441赫夫曼编码的存储结构赫夫曼编码的存储结构typedef structtypedef struct char bitsn+1; char bitsn+1; int start; int start

39、; char ch; char ch; codetype; codetype;codetype coden+1;codetype coden+1;课抄喂宵比轨图兔单取仓街趟容永住仲代蘸刘话挛疏支荚餐锰踌笛量僧斥五章树和二叉树五章树和二叉树9/21/202442赫夫曼编码的存储结构赫夫曼编码的存储结构序号序号bitschstart11111a220b53110c341110d2510e4黄必枉妹废哀苍羞拆硕造病嫁啥瓤邯肮专翔廓砂头楞卑敦交践奈饯华缓悟五章树和二叉树五章树和二叉树9/21/202443赫夫曼编码算法赫夫曼编码算法赫夫曼编码算法赫夫曼编码算法( ( ( (根据已构成的赫夫曼树，求出编

40、码根据已构成的赫夫曼树，求出编码根据已构成的赫夫曼树，求出编码根据已构成的赫夫曼树，求出编码) ) ) )HUFFMANCODE(codetype code, hufmtree tree)HUFFMANCODE(codetype code, hufmtree tree)HUFFMANCODE(codetype code, hufmtree tree)HUFFMANCODE(codetype code, hufmtree tree) int i,j,c,p; int i,j,c,p; int i,j,c,p; int i,j,c,p; codetype cd; codetype cd; code

41、type cd; codetype cd; for (i=1;i=n;i+) for (i=1;i=n;i+) for (i=1;i=n;i+) for (i=1;i=n;i+) cd.start=n+1; cd.start=n+1; cd.start=n+1; cd.start=n+1; c=i; c=i; c=i; c=i; p=treei.parent; p=treei.parent; p=treei.parent; p=treei.parent; while (p!=0) while (p!=0) while (p!=0) while (p!=0) cd.start cd.start

42、cd.start cd.start - -;- -; if (treep.lchild = = c) if (treep.lchild = = c) if (treep.lchild = = c) if (treep.lchild = = c) cd.bitscd.start= cd.bitscd.start= cd.bitscd.start= cd.bitscd.start= 0 0 0 0 ; ; ; ; else else else else cd.bitscd.start= cd.bitscd.start= cd.bitscd.start= cd.bitscd.start= 1 1 1

43、 1 ; ; ; ; c=p; c=p; c=p; c=p; p=treep.parent; p=treep.parent; p=treep.parent; p=treep.parent; codei=cd; codei=cd; codei=cd; codei=cd; 砖涩废双暖恃恭今召倘性庆渐剿厌炔沦额懊悦洋双隐停嗽萨温疑捻协斗火五章树和二叉树五章树和二叉树9/21/202444赫夫曼解码算法赫夫曼解码算法赫夫曼解码算法赫夫曼解码算法DECODE(codetype code,hufmtree tree)DECODE(codetype code,hufmtree tree)DECODE(cod

44、etype code,hufmtree tree)DECODE(codetype code,hufmtree tree) int i,j,c,p,b; int i,j,c,p,b; int i,j,c,p,b; int i,j,c,p,b; int endflag=-1; int endflag=-1; int endflag=-1; int endflag=-1; i=m; i=m; i=m; i=m; scanf( scanf( scanf( scanf(“ “%d%d%d%d” ”,&b);,&b);,&b);,&b); while (b!=endflag) while (b!=endf

45、lag) while (b!=endflag) while (b!=endflag) if (b=0) i=treei.lchild; if (b=0) i=treei.lchild; if (b=0) i=treei.lchild; if (b=0) i=treei.lchild; else i=treei.rchild; else i=treei.rchild; else i=treei.rchild; else i=treei.rchild; if (treei.lchild=0) if (treei.lchild=0) if (treei.lchild=0) if (treei.lch

46、ild=0) putchar(codei.ch); putchar(codei.ch); putchar(codei.ch); putchar(codei.ch); i=m; i=m; i=m; i=m; scanf( scanf( scanf( scanf(“ “%d%d%d%d” ”,&b);,&b);,&b);,&b); if (treei.lchild!=0) printf( if (treei.lchild!=0) printf( if (treei.lchild!=0) printf( if (treei.lchild!=0) printf(“ “nERRORnnERRORnnERRORnnERRORn” ”);););); 炼旬烽硫肉条瘩扎谜嚼灰男慕星熏寒茬彩皂右床译统思韧穴翔丽炭审郑拔五章树和二叉树五章树和二叉树9/21/202445