第六章树二叉树

第六章树和二叉树一、树的基本概念二、二叉树、遍历、线索化三、树和森林四、哈夫曼树【教学目的】掌握树的基本概念，二叉树的基本概念，二叉树的逻辑结构、存储结构以及二叉树的操作的实现；掌握二叉树与树和森林的转换，进而掌握树和森林的存储结构，利用二叉树解决Huffman编码的应用【教学重点】二叉树的概念、二叉树的递归与非递归遍历算法、线索化、二叉树与树、森林的转换，Huffman树及Huffman编码【教学难点】二叉树的非递归遍历及线索化6.1树的基本概念一、树的定义及表示1定义树：n（n≥0）个数据元素（结点）的有限集合。当n=0，则称为空树；当n>0，满足：（1）树中有且仅有一个特定的数据元素被称为根结点。（2）当n>1时，其余数据元素被分成m（m>0）个互不相交的子集T1，T2，...，Tm，每个子集又是一棵树,称为根结点的一颗子树。树的几种形态树的特点（逻辑结构）（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点（2）树中所有结点可以有零个或多个后继结点①②③2树的表示方法直观表示法嵌套集合表示法凹入表示法//不清晰广义表表示法④二、基本术语结点：数据元素(的内容及其指向其子树根的分支统)称为结点结点的度：结点的子树（分支）数。终端结点（叶子）：度为0的结点。非终端（分支）结点：度不为0的结点。结点的层次：树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的度：树中所有结点度的最大值。树的深度：树中所有结点层次的最大值。有序树、无序树：如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。森林：是m（m≥0）棵互不相交的树的集合。孩子、双亲：结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。子孙：以某结点为根的子树中的所有结点都被称为是该结点的子孙。祖先：从根结点到该结点路径上的所有结点。兄弟：同一个双亲的孩子之间互为兄弟。堂兄弟：双亲在同一层的结点互为堂兄弟。6.2二叉树定义二叉树:n（n≥0）个结点的有限集合。当n=0时，称为空二叉树；当n>0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个称为左子集（树），另一个称为右子集（树），每个子集（树）又是一个二叉树。二叉树的基本形态二叉树的性质在二叉树的第i层上最多有2i-1个结点（i≥1）深度为K的二叉树最多有2K-1个结点（K≥1）（称为满二叉树）对于任意一棵二叉树，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1二叉树的总度数＝n1+2n2二叉树的节点数＝n0＋n1＋n2二叉树的总度数＝二叉树的节点数－1n1+2n2=n0＋n1＋n2-1即：n0=n2+11234675具有n个结点的完全二叉树的深度为log2n+1完全二叉树：n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1～n的结点位置一一对应，则称这棵二叉树为完全二叉树证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出：2K-1-1<

n≤2K-1将不等式两端加1得到：2K-1≤n<2K取以2为底的对数，化简：K-1≤log2n<K得到：log2n=K-1。整理：K=log2n+1完全二叉树：一棵二叉树至多只有最下面两层结点的度可小于2，且最下面一层上的结点都集中在该层最左边的若干位置对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i（1≤i≤n），有:如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为i/2。如果2i>n，则结点i没有左孩子；否则其左孩子结点的编号为2i。如果2i+1>n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1。二叉因树的僚操作Cr针ea榜te筹Bi牛Tr妥ee盆(T,尚de塑fi社ni稿ti搁on蹦);以de围fi狂ni捡ti蜂on给出锹二叉挥树T的定讽义创溉建一性棵二乎叉树De孔st彻ro惯yB苏iT粱re衔e(香T);销毁府二叉余树T。Cl回ea规rB对iT摄re却e(岔&T);将二英叉树T清为意空树尺。Pa巴re职nt蝴(T,籍e)仇;求e结点称的双全亲结适点，疮若e是T的非精根结声点，息则返注回它汤的双手亲，终否则德返回“空”。Le窄ft田Ch刺il欧d(瓣T,警e)修;求结食点e的左导孩子砍，若e无左闭孩子必，则刘返回"空"。Ri盯gh捞tC磁hi屠ld授(T,忌e)饶;求结举点e的右追孩子互，若e无左萍孩子劳，则祝返回"空"。二叉荷树的俗操作Le柱ft仰Si堵bl能in贪g(勒T,隐e)画;求结罢点e的左兼兄弟征。若e是其浙双亲活的左园孩子替或无固左兄披弟，鼠则返桨回"空"。Ri更gh梳tS异ib析li绳ng鉴(T,馒e)务;求e的右须兄弟蜓。若e是其吹双亲朋的右嚼孩子箭或无荣右兄圈弟，骂则返继回“空”。In径se息rt连Ch米il厨d(桂&T,县p,泡L狱R,透c冠);根据LR为0或1，插膜入c为T中p所指少结点格的左仰或右艰子树歇。p所指膀结点谁原有扒左或坛右子轨树成户为c的右纯子树扭。De图le疯te樱Ch牢il傍d(谎&T,凤p,笛L虑R)妙;根据LR为0或1，删蜜除T中p所指仙结点漠的左攻或右痕子树加。其他创衍生融操作二叉串树的乎操作Pr勇eO腾rd厨er秧Tr窗av跳er锈se湾(T,激vi译si闭t(元))贝;先序压遍历T，对尊每个再结点晕调用哲函数vi聚si狂t。In范Or煮de去rT援ra紧ve衣rs虑e(沙T,vs奏it()患);中序雁遍历T，对牢每个抓结点痛调用添函数Vi尽si娘t。Po器st译Or骨de番rT造ra倾ve给rs英e(反T,场vi督si寨t(女))精;后序也遍历T，对垃每个焦结点买调用岩函数vi衣si耻t。Le罩ve浙lO妥rd饮er按Tr粘av撞er语se氏(T,弦vi匀si融t(厚))侍;层序仪遍历T，对涂每个妈结点印调用裤函数vi仆si唉t。三蚊二叉鞋树的督存储侍结构1顺序撞存储回忆绸性质塔⑤，助完全狂二叉谅树二叉长树的帐顺序冻存储蓬定义#d欢ef蜘in磁eMa任xT枣re甜eN耀od金eN伶um10勺0ty裤pe倦de商fst测ru稿ct{Da议ta贱Ty危peda站ta钓[M耕ax补Tr蹲ee舱No赖de公Nu杨m];/*根存插储在龄下标冠为1的数招组单逃元中徐*/in屋tn;括/*当前尽完全稠二叉啄树的呜结点伶个数育*/}QB夺Tr骨ee;二叉族树是利完全仿二叉泽树时沫，没米有问才题。已但是流如果丘是非微完全艳二叉让树怎疏么办航？方法胀：将轮非完趟全二软叉树具以特寄殊值蚊填充饶成完乏全二举叉树记形式映。新的恨问题家：若卫为完更全二迅叉树笑，空衰间利眼用率创高、场寻找除孩子兴和双名亲比充较容蕉易。枣若不衬是完孩全二饲叉树涂，造搬成空抹间利凭用率封的下芳降。2二叉刘树的镇链式脆存储由于梢二叉胜树最懒多只匹有两显颗子禾树，刻因此毛可以宾采用浮二叉刮链表迁形式饱存储历。Lc勒hi酬ld和Rc底hi牢ld是分残别指闹向该麦结点辛左孩脏子和静右孩味子的腾指针二叉翁树的杀链式云存储傍定义ty脊pe柴de饺fst残ru壤ctbn颈od吹e{Da黄ta惭Ty匪peda评ta拾;st牺ru弃ctbn技od时e*lc秤hi壮ld,伪*rc帐hi钩ld;}Bn没od懒e，*BT孩re避e;二叉声树的翼链式馆存储恐结构眯类似欠线性显表的乒双向申链表赚存在丛两个拜指针料，分饼别指旬向其饿左右泼子树原，而脑非双楼向链差表的惰前驱箩和后呼继。链式版结构徐可以低根据男二叉班树的后结点锈数来逼动态殊分配迅存储述空间密，解胁决了住顺序预存储勾结构怪的问摔题，坊因此醉常用腐的二哄叉树务采用额二叉锡链表雕的形病式比较较多规。根据谁操作身的不顽同可搜以对拾二叉剃树进只行改跪进，脱如：次考虑挎求双湖亲（笼前驱项）操诱作时较可以祖采用颤什么骑形式仔？遍历定义贯：按归照一向定规激则访森问二滋叉树凑的所哄有节之点一蹲次。根据围根结锅点和问左右庄子树猫访问贤的先赏后不案同，茧有四攻类七近种遍公历操嫩作。先序汤遍历敢：TL脆R或者TR驾L中序兰遍历博：LT混R或者RT是L后序呀遍历薯：LR伸T或者RL粗T层次工遍历继：从牢上到是下，从左殃到右依次判访问拨结点6.未3二叉只树的不遍历先序持遍历丧：ABDGCEFH先序蜘序列傍：AB没DG尤CE飘FH中序絮遍历漫：DGBAECHF中序序列约：DG场BA砌EC椅HF后序砍遍历主：GDBEHFCA后序序列写：GD宇BE遍HF股CA层次芬遍历凯：ABCDEFGH层次茶序列扬：GD俩BE勤HF每CA1二叉手树的由先序劈燕遍历算法蜓思想炼：判其断二惧叉树报是否题为空融？若为宽空，冒则结墨束遍佳历；达否则缺先访任问根鸟；再先腰序遍疼历根滤的左挑子树腊；最后构先序腹遍历司根的孔右子绣树vo显idPr正eO详rd严er(BT导re症et漫){}if煎(拦t交){低vi掌si润t斯(t波->娇da广ta拢);瓦/臣*访问秧结点考内容冤*/Pr捏eO球rd趋er(贯t-厕>lc童hi化ld);歪/*遍历流左子堪树治*/Pr烘eO倍rd丛er(压t-堤>rc晋hi训ld);召/*遍历业右子只树笑*/}2二叉桂树的隙中序多遍历算法堆思想哈：判横断二倍叉树四是否锻为空葡？若为勇空，肥则结锦束遍疾历；否则幅先中此序遍睁历根怀的左块子树窃；再访首问根妙；最朽后中葱序遍践历根栏的右条子树vo笋idIn冲Or著de柴r(BT刊re泥et阁){}if友(台t局){In柳Or弹de刚r(疮t-汽>lc涂hi昏ld);熔/*遍历膝左子剧树满*/vi妙si抽t调(t编->宁da姻ta蛛);炸/善*访问绢结点羊内容辟*/In引Or池de荐r(课t-阶>rc卵hi残ld);靠/*遍历诱右子坐树薪*/}3二叉鞠树的皆后序吃遍历算法胸思想宋：判习断二轰叉树惭是否态为空根？若为旨空，培则结莲束遍缘瑞历；否则盲先后劣序遍闷历根也的左傻子树观；再后汁序遍遥历根前的右宿子树登；最暗好访坏问根vo蔑idPo袍st雪Or腿de央r(BT渐re串et特){}if送(讲t番){Po担st卫Or死de蹈r(素t-绳>lc瞎hi该ld);买/*遍历闲左子蚂树天*/Po亭st司Or名de割r(外t-畅>rc特hi钢ld);妹/*遍历呈右子雪树妙*/vi仓si答t文(t历->赌da帐ta笼);假/翻*访问越结点厉内容擦*/}二叉陷树的邮先序杏遍历反的非馒递归灿算法理解列递归租算法早的过远程ABCDEFGHABDGCEFH二叉论树的龄先序傅遍历箩的非顾递归片算法vo没idPr冻eO块rd肥er(BT授re叫et){PS塑eq筹St耕ac亏kS;BT渗re遍ep刃=呆t;S=In里it唱_S芹eq歌St雹ac蚊k(饺);主/帮*栈初阴始化响*/A(利用细栈进康行遍休历)De短st捉ro肚y_祖Se喜qS学ta谈ck响(&羽S);}二叉代树的书先序赞遍历月的非社递归疼算法A:wh抛il材e菠(天p弄||花!Em怀pt达y_扛Se纳qS落ta沫ck(S肃)构){if砍(表p熄){Vi揉si图t分(p告->仁da海ta监)妻;Pu蔽sh臣_S护eq奋St盯ac窄k(屋S,帜p弱);障/丽*预留p指针还在栈阵中哨*/p胶=炭p-姐>lc币hi徐ld;}el跌se{Po番p_迷Se针qS潜ta飘ck(S,略&p);p泻=嘴p-意>rc推hi恼ld;}坚/*左子绵树为截空,进右尸子树鹿*/}目的术是什罚么？从左悦子树妈返回垃时能鸣找到泪右子索树二叉眠树的归中序月遍历高的非倚递归足算法理解罢递归架算法愧的过警程ABCDEFGHDGBAECHF二叉么树的炭中序性遍历饶的非瓦递归泳算法vo载idIn甜Or核de键r(BT孕re山et){PS诞eq竭St撇ac功kS;BT弊re稿ep盆=化t;S=In龄it挽_S犯eq段St词ac服k(扩);何/皱*栈初讨始化蒙*/A(利用根栈进僻行遍酒历)De缝st敲ro且y_匪Se伟qS棵ta准ck秤(&脏S);}二叉雷树的壤中序圣遍历闲的非鸟递归顷算法A:wh爸il距e委(烂p轮||司!Em丈pt会y_音Se贷qS匪ta筐ck(S艘)乔){if振(储p朵){Pu碗sh助_S绵eq素St疯ac悠k(葛S,爷p阶);帆/同*预留p指针绘在栈搜中掀*/p荣=煮p-巴>lc坏hi肿ld;}el治se{Po吊p_绝Se峰qS牙ta雪ck(S,棕&p);Vi怒si掩t稠(p鲁->奸da或ta合)岁;p幸=昏p-奥>rc家hi业ld;}纵/*左子斩树为络空,进右揉子树挽*/}目的暑是什笋么？从左禽子树蓬返回映时访永问根个，并轻且通型过根雨结点驻能找早到右圆子树二叉厦树的庸后序督遍历陷的非究递归判算法方法趁一：逃利用园先序种遍历糠非递痰归算边法(按先旨根结屿点、井再右子集树、再左子责树的顺惕序)将找磁到的追要访们问的启结点岔压栈遍历垮结束沈将栈发中元贼素出全栈访厌问vo倒idPr皮eO乳rd苹er(BT顺re锅et){PS警eq籍St拆ac思kS1奴,S催2;BT肠re面ep轮=溜t;S1接=In晋it部_S批eq凤St太ac秋k(方);如S2晋=In痛it蔑_S叠eq痰St久ac期k(杆);wh岂il练e肝(翻p爆||固!Em秋pt制y_野Se环qS晨ta丸ck(S学)傻){if亡(注p圈){Pu涉sh私_S雾eq作St绝ac厚k(潜S1削,破p)匹;//保存敢到结恰果栈荣中Pu迅sh虫_S朱eq乌St遵ac兔k(孟S2另,弯p)去;许/车/预留p指针铸在栈工中p谷=秒p-震>rc滴hi破ld;//先右镰后左}el节se{Po际p_绪Se帐qS偶ta台ck(S母2,锐&p读)迎;p徒=笛p-今>lc尾hi励ld;}}wh雪il伐e蹈(凭!Em偏pt略y_盲Se缝qS枝ta氏ck(S阳1)吉){Po聪p_芝Se粥qS阔ta棒ck(S裳1,诊&p矛)薄;Vi通si壤t效(p吊->绑da垂ta述)兄;}De佩st拍ro栽y_苏Se凯qS貌ta葛ck催(&多S1塌);蒙D葵es革tr土oy算_S饲eq全St旬ac镇k(井&S苏2)荷;}方法己二：峰二叉廉树的雀后序震遍历最的非鹿递归欧算法理解嘴递归尤算法是的过困程ABCDEFGHGDBEHFCA二叉往树的铃后序膜遍历昂的非栏递归蹈算法ty适pe泳de尘fst常ru考ct{Bn独od面e*n督od减e;in熄tfl房诚ag牺;}SD触at对aT崇yp雨e;vo浊idIn躺Or本de剥r(BT唇re哗et){PS夏eq顾St筑ac校kS;BT谎re堡ep赢=拐t;S=In殃it懂_S悔eq潮St滤ac曲k(干);若/凑*栈初骂始化靠*/A(利用积栈进丘行遍车历)De回st或ro睛y_颗Se矿qS火ta株ck叼(&挨S);}二叉毯树的幼后序湿遍历护的非怕递归淋算法A:wh纽奉il层e疮(装p宗||蹦!Em强pt项y_牲Se虹qS绳ta皇ck(S织)容){响if协(迎p览){Sq押.f茅la台g=0让;Sq淘.n梅od错e=p徒;Pu工sh悦_S族eq望St熄ac别k(尝S,延S命q)撞;p饲=融p-言>lc扁hi刑ld;拘}el惊se{Po炸p_野Se宽qS碑ta保ck(S,炮&s肠q);p=sq境.n况od按e;if屑(Sq针.f辛la框g==础0){Sq咳.f垫la孙g=1手;Pu熔sh筒_S矮eq滴St融ac绞k(S,德Sq);p=颠p惧->rc壳hi煮ld;编}el刃se{除Vi宴si蚀t缺(p狂->穴da蚊ta昏)纪;p来=芒NU净LL怀;}}目的矮是什杠么？目的虹是什吹么？目的围是什上么？从左岁子树哗返回蓝时通焦过根饺结点震能找非到右泻子树从右舌子树普返回肠时能赴访问恼根结研点从右件子树狱返回认访问场根后,结束捉了这缎颗子飞树访暑问应贡返回弃该子瓣树的泳双亲,应弹魂栈，帜设为nu奶ll使下律次循娱环能辛弹栈4二叉搂树的魄层次反遍历填算法ABCDEFGH队列知：ABCDEFGHvo枝idLe歪ve揉lO穷rd共er王(B规Tr转eet){Ps挪eq崭Qu自eu迟eQ;BT窗re划ep;if糠(喇t){送Q=In蜜it滨_s赌eq郑Qu伟eu果e()顺;缘瑞//设置旦一空台队列In评_s娱eq雾Qu牢eu金e(语Q,遵t);稠//根结妈点入评队wh涌il付e谋(!Em费pt螺y_谜se冶qQ舌ue旅ue(Q素)){金/惹/当队辫非空荣时重晓复执如行下些列操制作Ou启t_邀se牌qQ兄ue贿ue欠(Q辨,&叫p);Vi尺si周t(给p->台da驳ta草);眠//出队竿访问if牲(勿p-载>Lc思hi翻ld)In嘴_s碰eq姑Qu慰eu目e(肌Q,辅p->Lc汇hi联ld);少//左孩千子入别队if前(碑p-忌>Rc纤hi消ld)In细_s闷eq江Qu容eu共e(右Q,腹p->Rc薪hi败ld);将/壳/右孩世子入应队}De骑st从ro商y_听Se毯qQ挪ue钻ue波(&眉Q);}}5遍历旨算法汗应用膛举例二叉哄树是席递归魄定义纵，可灾以写毯出它所的递程归遍抵历算帐法，毅同时捉借助恰遍历那算法劣思想痒可以慨实现懂其它镇算法善，如换：创建掀二叉始树、袋销毁跨二叉趣树等傲；计算毒二叉绣树的告高度盈，计尘算结琴点数密，二缘瑞叉树袖的查诸找等辨操作二叉音树的沉创建钥算法在输野入先增序序零列时戴，需慎要在旦空节者点填替补一司个特潜殊的香字符休，比惠如，毯‘#’。如档果读众入的艰字符聋是‘#’，则丑在相古应的竿位置睬上构碰造一羞棵空折二叉蔑树；肝否则猪，创云建一授个新宵结点宪。采锄用先另序遍庭历递是归算鼓法为缠基础膛，二计叉树呈中结判点之乌间的鄙指针执连接节是通抬过指择针参腾数在醋递归婆调用候返回炮时完桂成。二叉民树的剂创建垦算法AB眼D#般G#蹦##奴CE咐##浆FH蠢##挪#ABD#G###CE##FH###BDGCEFHA二叉柄树的汪创建睁算法BT妥re墙eCr缸ea挠te偶Bi戚nT吹re桶e(慢vo估id吸){部ch缺arch;BT灶re帜et;ch=ge痒tc超ha丘r()穴;if穷(ch==登‘＃’)re接tu界rn虚NU灿LL爹;恩/*读入例＃时犹，将茂相应票结点雁指针烛置空观*/el鼻se{装t=皇(Bn促od竭e*)ma注ll透oc哈(B梢no芝de);宫/*生成丑结点盾空间热*/t-末>d柔at窃a=ch;t-收>lc渡hi啄ld=Cr倦ea圾te邮Bi转nT屑re羞e()扛;t-驼>rc饮hi呆ld=Cr址ea蚀te卡Bi狱nT追re粥e()淋;re永tu译rn矩t凤;}}二叉腰树的慌创建者算法vo剪idCr眯ea帮te洪Bi孩Tr疾ee(BT寸re苍e*t难){叶/*以加孔入空予结点杯的先邀序序谎列输测入，等构造禁二叉蚁链表岭*/ch盲arch;ch=ge量tc撒ha斥r()秒;if浑(ch==镇‘＃’)*t洞=N泥UL驼L;枝/颠*读入皱＃时红，将你相应些结点凡指针拨置空条*/el剩se{迈*t作=(Bi班Tr涨ee)ma哀ll茅oc缩慧(B竭no幕de);奸/*生成扬结点乞空间虏*/(*绳t)宪->熔da站ta过=ch;Cr利ea侦te框Bi本Tr唱ee(&脆((滥*t今)-福>lc侦hi棚ld))碎;Cr茫ea畜te薯Bi仙Tr疏ee(&兼((辜*t纸)-工>rc勤hi互ld))偷;}}二叉洲树的汪销毁康算法算法渐思想深：销毁膨二叉伯树可草以根桂据先剑序遍概历类芝似，潜先若怠树为盖空树趟，不守用销防毁直序接返御回；静若为销非空典树，行则先终销毁麻左子脏树，徒再销豪毁右敬子树胃，最伤后销钟毁根德节点眉。vo侵idDe氧st决ro语yB杂it魄Tr菊ee(BT游re归e*t艘){盲/*销毁t表示桐的二拉叉树笨*/if容(邪(宁*t拢)料){De辱st史ro枕yB违iT闸re桂e(&风((超*t秤)-橡>lc设hi迟ld))贩;De扮st映ro背yB河iT叨re泡e(&鹅((耕*t浅)-畜>rc浓hi塔ld))归;fr方ee狂(*蒸t)宅;*t梳=N匪UL肃L;}}计算进二叉探树的透结点恶个数vo吴idCo灾un声t_柱Tr剪ee寇(B说Tr垃eet){幻玉i谅f兄(t剩){Co农un凉t_奥Tr身ee披(t->lc刚hi苏ld)；//统计欺左子果树结挠点个单数co柔un咳t+缎+;//躺co沸un纵t为全社局变技量Co沫un凉t_恒Tr钥ee丢(t->rc刮hi承ld)仔;//统计步左子湖树结口点个趴数}}in拼tCo吉un集t_鬼Tr册ee委(B泳Tr支eet){in蹦tlc跟ou维nt暴,r斤co熟ut;if误(吊t=局=N萌UL弦L)搞re邪tu饱rn羡0灶;lc拆ou贷nt=Co历un宅t_炎Tr广ee乖(t->lc男hi弱ld)；rc方ou图nt=Co祸un种t_烧Tr把ee墨(t->rc穿hi歪ld)肉;re随tu并rn感(勤lc肺ou亮nt磨+r盐co偶un筝t+笑1)余;}求二屈叉树纯每层洋结点恳个数算法姥思想笼：设置堂一个答数组袭，数秩组的播下标涂表示浑树的约层数杜，该型下标稍元素孔的值舰记录殖该层宏元素苏的个院数；陪通过搁树的梦遍历火算法婚来得需到最北终数命组元罢素的毯值。求二浸叉树腹每层酬结点暴个数in通tnu克m[蜂20贩]；Vo资idLe祥vc镇ou棉n(BT筛re谁et,in劲tL,服in夏tnu匪m[昏]华)//话L是当童前结迈点的弦层次锄，初彻值1，nu勤m数组依元素妇初始骄化0{if他(盒t阁){nu倡m[暗L]+猫+;Le汁vc击ou骂n(t赤->lc林hi续ld,丈L+振1,奴nu澡m)史;Le异vc答ou纤n(t奋->rc伐hi侄ld,在L+旱1,被nu悬m)系;}}调用砖前，nu膀m数组亚元素雨全部青清0初始漏调用野：Le克vc预ou塑n(t猴,铺1,父nu制m)求二傍叉树算的高秋度定义纵：树纺中节固点深夺度的宾最大洒值结举点个向数in程tHe咸ig讯ht粪(BT俘re炼et劣){in晨th1钞,h制2;if啄(其t=篮=N宝UL叼L)嫁re烛tu对rn辛0鸣;h1钻=He撕ig倚ht约(t->lc刮hi片ld)；h2喜=He爪ig轧ht圆(t->rc嫌hi图ld)；re鲁tu锦rn庆(绢(h活1>慰h2乏)旱?轰h肚1+珠1:状h2刷+1探);}求二括叉树蜻的复得制BT化re坝e*Co蓄py性Tr攻ee(BT犯re扁et){BT财re奖es;if乘(钞t=典=壁NU战LL霉)re俊tu莫rn强(声NU塌LL爽);s=等(Bi蹈Tr雄ee)ma仿ll梅oc(Bn总od妹e);咐/返/复制迫根结理点s-叼>d第at炭a=蚊t-钩>d翼at就a;s-武>lc麻hi买ld=Co豪py钢Tr所ee懒(t->lc怖hi弄ld);主//复制金左子厌树s-脂>rc轿hi苹ld=Co验py侍Tr禁ee讽(t->rc帆hi其ld);规/墙/复制锻右子径树re脉tu卡rn科s就;}交换鞋二叉回树的誓左右偶子树vo丝式idch侄an辩ge舅_l谷ef营t_咱ri绘gh波t(跨BT萄re绿eBT郊){银i仗f统(B今T){ch地an葬ge梨_l炮ef滩t_勒ri己gh存t(腾BT->lc芽hi脂ld);ch炒an堡ge倦_l欧ef肝t_牙ri苹gh陕t(寇BT->rc粥hi杏ld);BT脸->lc抱hi清ld<-挨>B音T-乏>rc系hi除ld;}}6.幼4线索伟二叉纲树研究括二叉术树的绕遍历案发现须：通冠过指究定次捏序的愧遍历妥发现攻求结球点的相前驱稻或后禁继，扁费时论间，峡效率俗低。如何币解决惊？方法1：增傍设前灾驱和狼后继筛指针——在每闪个结戴点中双增设览两个眠指针慨，分却别指圣示该厉结点报在指倚定次拿序下亡的前秘驱或叛后继霞。从捐而避显免使两用递前归减窝少了似函数俱调用词的时蜻间，夺但增骗加了倾空间掀开销花。方法2:二叉树中联有很枝多闲岗置的骂指针燥，能请否利合用它漫们为赌访问劳二叉喉树提缴供便病利?利用腔二叉厕链表诞中的费空指唐针域橡（n个结嚷点的卖二叉咬树有n+宽1个空梨指针华域）休，将跟二叉神链表分中的奔空的衫指针剑域改迹为指括向其该前驱串和后妥继：体空的幸左孩垄子指旧针指甘向其霸前驱准，空焦的右姜孩子脖指针越指向翠其后们继伏。ABDGCEFH如何努区分察谁是简后继窜结点拨，谁懒是右花孩子弃结点狸？谁是个前驱迅结点品，谁加是左雾孩子旨结点殊？设立扶标志练位：lt年ag=0：lc筐hi督ld指示司该结滔点的制左孩字子lt惜ag=1：lc里hi认ld指针替该结想点的配前驱意。rt汽ag=0：rc把hi炉ld指示帜该结痒点的印右孩蛙子rt抵ag=1：rc喉hi这ld指针散该结锡点的汗后继童。中序抖遍历饥下的拥线索兵化二传叉树修形式球：ABDGCEFH线索锡二叉辫树的估数据遵结构转定义吨：ty嚷pe讲de抹fst煤ru炸ctTh划re侄ad侍no不de{in携tlt复ag；st阶ru撒ctTh险re贯ad泰no涌de*lc唇hi锤ld；Da静ta灾Ty粮peda但ta锋;in篮trt甲ag;st虾ru阻ctTh教re辟ad菊no贤de*rc肯hi终ld;}Th雪re白ad泡no锣de，*Th亿re槽ad肥Bi盒tT伍re判e；中序续二叉狐树的坛线索果化vo骑idIn倚Th弊re绵ad(Th捆re股ad榜Bi失tT缝re屈ero地ot鹿,Th色re魂ad恩Bi冰tT推re拉epr亿e){罪/*递归匀中序效线索售化二仅叉树早；加函浴数调讽用前pr砌e为空杨*/if允(r浮oo望t){In润Th售re六ad轿(r远oo辣t->lc卖hi缸ld遍,p命re);画/*中序熟线索盲化左躬子树景*/A：当叨前结脾点线份索化In潮Th穿re稻ad(r持oo侧t-张>rc栋hi帮ld救,p晚re);些/*中序稼线索胆化右窃子树姓*/}/撞/en嗽di楼f}中序史二叉滥树的惹线索双化A：当川前结遮点线那索化if沈(漠ro段ot裹->lc侧hi经ld==弓nu傻ll伯)国//建立情前驱饶线索{横r掩oo著t-食>lt犁ag=1芦;ro阳ot办->lc苦hi挎ld=p下re饺;请//左孩亡子域臣指向跟前驱}if宪(属ro解ot她->rc妇hi裤ld==湿nu魔ll弊)ro纺ot严->rt犯ag=1侵;if体(愚(pr尊e)沾&&肚(p方re->rt掀ag==位1)pr伶e-捉>rc敏hi录ld=r配oo酿t;pr返e=诉ro选ot勒;if赏(暗(pr溉e)往&&妻(p构re->rc两hi侦ld==朱nu赞ll俯){贞pr萍e-经>rt晒ag=1新;pr悬e-荷>rc呆hi相ld=r愈oo枝t;}//为下飘次后鹿继线渴索做裂准备//建立贼后继柳线索中序冤二叉判树的援线索践化的马非递网归算爬法vo坡idIn沉Th董re斑ad(Th科re株ad怒Bi箭tT包re吓ero掩ot舒,Th胳re盯ad症Bi淋tT少re屯epr避e){PS德eq率St督ac培kS;Bi浴Tr脂eep排=霜t;S=In乖it四_S独eq默St辜ac遇k(净);泽/洞*栈初桃始化拘*/A(利用野栈进至行中熊序线鲜索化)De耽st像ro哨yS揉eq桌St猎ac铸k(某&S);}二叉累树的此中序误遍历遇的非今递归他算法A:wh皇il蝇e(酿p|俗|!俊Em湖pt宅y_仅Se浅qS扮ta归ck(些S)蔽){辣if梅(日p){Pu娃sh溉_S朴eq稍St级ac矿k(驾S,胶p弯);剃p喝=课p效->lc栽hi壳ld;费}el伞se{po贺p_铸Se观qS包ta竞ck(S,宝&p);if色(p贤re!=泽NU扯LL疾){if咏(!奖pr绸e->rc秀hi航ld){上pr韵e-荐>rc蚕hi拒ld=p猜;更pr魂e-投>rt墓ag=1炼;储}if杆(!昂p->lc督hi舍ld){援p-映>rl浸ch格il别d=p没re酒;里p-拘>lt著ag=1环;倒}pr被e=侨p;p工=两p-匆>rc务hi于ld;}}/参/e士nd重w凯hi饶le中序培线索轿化的姐二叉磁树的闭前驱Th本re缺ad隆no墓de*In电Pr玩eN妹od焰e(Th箩re廊ad途no缎de*验p){遵//在中燃序线贪索二灿叉树蒙上寻讨找结货点p的中召序前毁驱结榴点伴，假沸设p非空Th林re龟ad废no熊de*否pr流e;pr笔e主=p拖->lc睬hi羊ld;if女(她p-贯>lt蜻ag==加0){磨wh献il协e痒(向pr道e劝&&森p赤re糕-升>rt气ag==竟0)pr兰e迅=pr赵e->rc夜hi矮ld;}re汽tu疼rn纵(盈pr箱e)锋;}中序扒线索菜化的柜二叉纸树的承后继Th军re现ad拥no轧de*In饱Po晓st词No寇de(Th淹re倚ad净no啄de*械p){蜜//在中斯序线名索二抵叉树互上寻年找结容点p的中痒序前颠驱结仗点马，假睁设p非空Th券re挎ad叔no蜜de*坊po奥st喷;po叠st荷=枕p-限>rc梁hi行ld;if做(市p-熊>rt沉ag==墙0){引wh第il优e愚(钱po把st编&夺&滔po织st解-胞>lt役ag==趋0)po径st晓=po漏st->lc柿hi肯ld;}re恢tu畅rn城(晨po员st宣);}中序愉线索贷化的滨二叉彩树的叔遍历vo劈燕idIn百Or姜de绣rT示h(Th单re拉ad培no漏de*镇ro输ot疫)/*对中伐序线室索二洒叉树吐进行农中序性遍历芒*/{Th壤re革ad询no卧de*将p;if旋(旱ro堆ot掩){倍p=中ro阿ot撞;wh晕il灰e隔(p遗->lt抢ag==亩0)仁p=广p-萌>lc倾hi碗ld;榜/*找最辰左下花的结牧点*/wh青il榨e斗(p省){vi疯si金te见(p->估da酿ta押);危/煎*访问瞎当前角结点呆*/p=In狂Po崖st概No比de(p贡);细/*寻找谜结点p的后幸继结坛点齐*/}}}中序皆线索铃化的耕二叉候树的必查找善指定眠的xTh舞re京ad救no恩de*In拖Se穴ar喊ch拘Th(Th怠re活ad鬼no酱de*梳ro啦ot，in制tDa皇ta吹Ty吧pex)/*对中扁序线潮索二泰叉树辞进行桑搜索*/{Th忌re颜ad色no巴de*烧p;if顿(驰ro剃ot拼){抱p=顽ro迈ot讯;wh砌il芝e扣(p思->lt邮ag==死0)稍p=龙p-壶>lc睛hi若ld;牢/*找最秩左下涌的结栽点*/wh桶il善e青(p哥&明&p-松>d遇at帽a傻!=旦x)p=In哲Po仆st奸No炒de(p仙);销/*寻找判结点p的后烟继结盖点俊*/}re断tu貌rn勒p冲;}6.仍5树和椅森林一、陈树的爸存储猫结构1、双晋亲表疼示法2、孩领子表抛示法3、孩商子兄缸弟表目示法每个从节点易中存拿储自穿己的志第敌一个脏孩子潮和兄商弟的清地址医（连隙接所摩有的盆兄弟狡），泰链接归方式族存储孩子失兄弟熊表示士法数葵据结拼构定爸义：ty客pe送de夺fst度ru漂cttn稻od阴e{Da慰ta微Ty良peda初ta似;st婶ru拾cttn范od施e*fi潮rs身ts歌on；st份ru锅cttn乖od文e*ne捆xt愚br庭ot峰he矩r;}Tn果od绞e;二、大树、唇森林芒和二列叉树拴的转贝换1、树域转换普为二事叉树树中雄所有详相邻各兄弟浓之间亡加一戒条连厨线。对树吼中的腰每个爽结点角，只塞保留考它与骆第一怜个孩圈子结赵点之业间的岁连线佩，删呀去它僵与其荐它孩次子结解点之诸间的跳连线嚷。以树树的根缎结点黎为轴竞心，静将整绣棵树枕顺时教针转始动一扎定的衰角度雹，使烧之结掩构层港次分孙明树与吧二叉标树的夫转换余图2、森棍林转搏换为供二叉院树由于矿树转垄换成辜二叉绣树形炉式后素根的酸兄弟严指针眉总为魂空，所以站可以腹将森皱林中状的每富棵树陡的根酱互看溜成是颠兄弟斧，将沈第二棵树角接到赚第一灵棵的缠兄弟镇上，炮依次猎类推脆，可振以将n棵树透链成兄婆弟链鸦。方法讽：将森岁林中逝的每温棵树充转换洁成二槐叉树将转栗换好铺的每罗棵二跪叉树箩通过粥根节嘴点的雁右分雨支相笋连二叉庆树转祖换为陪树或冲森林方法禾：若某挨结点喇是其烂双亲伤的左川孩子匠，则似把该丙结点淡的右专孩子攀、右撇孩子挑的右旨孩子……都与辣该结抱点的暂双亲蝇结点连用线妥连起丛来。删去毁原二感叉树升中所钩有的紧双亲泄结点疾与右床孩子揉结点狐的连筐线。整理侦所得疯到的嫁树或滩森林丑，使妈之结葡构层段次分萄明。三、叹树、缠森林依的遍鞋历1、树群的遍枣历树的后根弃遍历飞：（1）按巨照从吐左到听右的愈顺序傻后根柜遍历师根结染点的兆每一瓦棵子肚树。（2）访俘问根沃结点辰；EF母BC凳GD旗A树的棒先根鸭遍历集：（1）访著问根奖结点罪；（2）按蜂照从阔左到四右的渗顺序喘先根投遍历鬼根结浑点的毁每一威棵子见树。AB展EF刊CD宴G看成没二叉咽树后量先序驶遍历:AB渣EF财CD贼G看成石二叉段树后敬中序响遍历EF腔BC笛GD叔AEBACDGF得出胞什么狐结论阻？树的殿先根蛛遍历铺与其冠转换柱的相回应二吴叉树垒的先样序遍蹈历的冠结果铜相同陷；树庙的后志根遍世历与滚其转篮换的怠相应偷二叉暂树的迈中序筑遍历乳的结责果相课同2、森刊林的组遍历前(先)序遍该历：膝若森吵林非坦空（1）访锅问森阻林中乏第一椒棵树竞的根宰结点探；（2）前课序遍责历第飘一棵娱树的疾根结当点的掉子树眼森林容；（3）前贵序遍崭历去捏掉第脚一棵裁树后宾的子物森林兄。中序植遍历波：若邀森林狸非空（1）中芽序遍普历第旬一棵坐树的塑根结符点的光子树燥森林别；（2）访贿问森茂林中箩第一湾棵树吩的根用结点允；（3）中米序遍仪历去衣掉第炸一棵掩树后炎的子志森林鞠。后序许遍历悄：若捎森林率非空（1）后辰序遍惜历第棋一棵险树的闯根结夫点的赔子树牲森林渠；（2）后供序遍银历去阴掉第洋一棵景树后躲的子见森林姻；（3）访存问森钉林中骆第一扭棵树服的根宴结点乱。广度摄优先乌搜索从第欠一层走开始捎，自忽顶向偿下、智同层帖自左权向右枣，依后次访问具森林校中各修棵树忆的结凳点，奴不要铜求一占棵树根一棵驼树地彻解决。6.乓6骆H劳uf壶fm涌an树问题嫩的提沸出：贤在通丧信系蠢统中吐，要谋发送畅由A，B，C，D四个炎字符副组成年的信稼息，A出现捕的概率为0.型5，B出现掉的概率为0.净25，C出现迟的概率为0.腹1，D出现寸的概率为0.豪15。如选何对A、B、C、D四个绕字符列进行汪编码出，能厨使总轨的编本码长剪度最伏短？改进搁编码戏：采长用不说等长岗的编壮码方肢法：前缀霞编码劫：设束计不酷等长斗的编瓜码，景且任第一字亩符的设编码猎都不胶是其涌他字辱符编长码的服前缀结论勿：不庭等长架的编侵码可绣以较办少数佳据量堡，起轮到压棚缩编雅码的屈目的浑。Hu斜ff路ma勤n树的战相关左概念惊：路径屡：从树校中一仍个结拳点到唇另一担个结银点之尖间的赔分支榜构成嗓两个公结点质之间袍的路誉径。路径厚长度浴：路径廊上的栗分支逼数目赚。树的鹊路径倘长度潮：根结技点到愚每个畅结点吊的路腐径长陪度之岗和。树的她带权杠路径蚂长度长：树中筑所有源叶子取结点溉的带甲权路筛径长尊度之坛和。记作:WP缺L＝∑wili(i晋=1中,…博,m更)其中框，wi是第i个叶颈子结吊点的才权值描，li为从忘根到亿第i个叶烧子结畅点的干路径匆长度字，m为树售的叶屑子结事点的船个数Hu留ff委ma毫n树的已定义亩：最优弓二叉非树：设有m个权爬值{w1,w2,…绣,wm}，构与造一铸棵有m个叶购子结斧点的注二叉占树，州第i个叶大子结享点的抄权值蜘为wi，则士带权写路径裹长度WP虫L最小除的二或叉树熟被称另作最龄优二苍叉树,这种半最优芹二叉碌树也榆称之茅为哈夫暮曼树Hu励ff着ma抓n树的末例子巴：wp础l=(尿3+非4+恭9+御15茫)*聋2=苍62wp苗l=1竹5*芬1+起9*采2+殊(3梨+4虽)*彩3=原54wp串l=4改*1妇+1袍5*道2吃+(段9+售3)彻*3务=7劝0Hu围ff到ma筹n树的圾构造鉴：(1矩)根据吃给定动的n个权讯值{w雷1,肢w2途,…，wn}，构普成m棵二尊叉树丈的集芝合T=用{T茫1,垦T2当,…木,Tn}，其厌中每隔个Ti只有读一个血带权膨为wi的根善结点完，其闷左右疤子树触均空秃。(2折)从T中选是两棵泳根结铸点的希权值虽最小午的二庭叉树,不妨胁设为Ti跪′,爷Tj′并作蚂为左歪右子骨树构排成一冷棵新滨的二休叉树Tk’，并烛且置瓶新二优叉树治的根暂值为缠其左忆右子吃树的确根结紧点的悄权值肚之和嫂。(3独)将新兵二叉亮树Tk’并入T中,同时尿从T中删逼除Ti页′,家Tj′。(4讯)重复(2嗽)、(3哗)，直宁到T中只驱有一更棵树精为止福。这论棵树皇便是颈哈夫滔曼树球。假设孩有一悄组权条值{5酬,2失9,奔7,亏8,振14副,2挎3,典3,词11金}，下沾面我绍们将互利用挺这组骄权值捡演示罚构造响哈夫要曼树店的过虽程。52978142331181519294258100带权哨路径匆长度惕为：WP踢L=(2怎3+势29奋)*塘2+招(1燃1+闸14徐)*轮3+(尊3+岁5+弊7+呼8)循*4价=2读71带权般路径僻长度容为：WP捞L=10搁0+尊42嗓+5躁8+护19斤+2称9+冠8+1资5=把27斤1Hu简ff及ma新n树的荷特点焦：特点1：若乓一棵今二叉习树是陈哈夫虏曼树告，则悉该二瞎叉树流不存爬在度盼为1的结节点。特点2：若敌给定慈权值党的叶井子结哗点个昨数为n，则纽奉所构矮造的视哈夫浙曼树赔中的胶结点丙数是2n律-1。特点3：任耕一棵孤哈夫棋曼树垒的带耀权路文径长奶度等涨于所各有分讲支结秩点值盾的累包加和锦。哈夫乒曼编贼码前缀灿编码杏方式侍，能但实现弟一组湿指定望出现究频率酱字符追编码界长度佳之和惹最小A:抵0T:搜10C:仅11芝0S:太11剃1#d寸ef爷in制e厌N颜2复0宅/居*叶子伏结点猜数写*/ty桃pe兼de加fin城tDa走ta幻玉Ty百pe;ty打pe克de秀fst