数据结构C语言第章树形结构

第7章树形结构7.1树的基本概念

7.2二叉树概念和性质7.3二叉树存储结构7.4二叉树的遍历7.5二叉树的基本运算及其实现7.6二叉树的构造7.8哈夫曼树

本章小结7.7线索二叉树7.1树的基本概念

7.1.1树的定义

7.1.3树的基本术语7.1.2树的表示7.1.4树的性质7.1.5树的基本运算7.1.6树的存储结构7.1.1树的定义形式化定义：

树：T＝{K,R}。K是包含n个结点的有穷集合(n>0),关系R满足以下条件:(1)有且仅有一个结点k0∈K,它对于关系R来说没有前驱结点,结点k0称作树的根。(2)除结点k0外,K中的每个结点对于关系R来说都有且仅有一个前驱结点。(3)K中每个结点对于关系R来说可以有多个后继结点。递归定义：树是由n(n≥0)个结点组成的有限集合(记为T)。其中,如果n=0,它是一棵空树,这是树的特例；如果n>0,这n个结点中存在(有仅存在)一个结点作为树的根结点,简称为根(root),其余结点可分为m(m>0)个互不相交的有限集T1,,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树,称为根root的子树。7.1.2树的表示(1)树形表示法。这是树的最基本的表示,使用一棵倒置的树表示树结构,非常直观和形象。下图就是采用这种表示法。(2)文氏图表示法。使用集合以及集合的包含关系描述树结构。下图就是树的文氏图表示法。(3)凹入表示法。使用线段的伸缩描述树结构。下图是树的凹入表示法。(4)括号表示法。将树的根结点写在括号的左边,除根结点之外的其余结点写在括号中并用逗号间隔来描述树结构。下图是树的括号表示法。7.1.3树的基本术语1.结点的度与树的度：树中某个结点的子树的个数称为该结点的度。树中各结点的度的最大值称为树的度,通常将度为m的树称为m次树。2.分支结点与叶结点：度不为零的结点称为非终端结点,又叫分支结点。度为零的结点称为终端结点或叶结点。在分支结点中,每个结点的分支数就是该结点的度。如对于度为1的结点,其分支数为1,被称为单分支结点；对于度为2的结点,其分支数为2,被称为双分支结点,其余类推。3.路径与路径长度：对于任意两个结点ki和kj,若树中存在一个结点序列ki,ki1,ki2,…,kin,kj,使得序列中除ki外的任一结点都是其在序列中的前一个结点的后继,则称该结点序列为由ki到kj的一条路径,用路径所通过的结点序列(ki,ki1,ki2,…,kj)表示这条路径。路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。可见,路径就是从ki出发“自上而下”到达kj所通过的树中结点序列。显然,从树的根结点到树中其余结点均存在一条路径。

4.孩子结点、双亲结点和兄弟结点：在一棵树中,每个结点的后继,被称作该结点的孩子结点(或子女结点)。相应地,该结点被称作孩子结点的双亲结点(或父母结点)。具有同一双亲的孩子结点互为兄弟结点。进一步推广这些关系,可以把每个结点的所有子树中的结点称为该结点的子孙结点,从树根结点到达该结点的路径上经过的所有结点被称作该结点的祖先结点。5.结点的层次和树的高度：树中的每个结点都处在一定的层次上。结点的层次从树根开始定义,根结点为第1层,它的孩子结点为第2层,以此类推,一个结点所在的层次为其双亲结点所在的层次加1。树中结点的最大层次称为树的高度(或树的深度)。7.有序树和无序树：若树中各结点的子树是按照一定的次序从左向右安排的,且相对次序是不能随意变换的,则称为有序树,否则称为无序树。7.森林：n(n＞0)个互不相交的树的集合称为森林。森林的概念与树的概念十分相近,因为只要把树的根结点删去就成了森林。反之,只要给n棵独立的树加上一个结点,并把这n棵树作为该结点的子树,则森林就变成了树。7.1.4树的性质 性质1树中的结点数等于所有结点的度数加1。证明：根据树的定义,在一棵树中,除树根结点外,每个结点有且仅有一个前驱结点。也就是说,每个结点与指向它的一个分支一一对应,所以除树根之外的结点数等于所有结点的分支数(度数),从而可得树中的结点数等于所有结点的度数加1。性质2度为m的树中第i层上至多有mi-1个结点,这里应有i≥1。证明(采用数学归纳法)对于第一层,因为树中的第一层上只有一个结点,即整个树的根结点,而由i=1代入mi-1,得mi-1=m1-1=1,也同样得到只有一个结点,显然结论成立。假设对于第(i-1)层(i＞1)命题成立,即度为m的树中第(i-1)层上至多有mi-2个结点,则根据树的度的定义,度为m的树中每个结点至多有m个孩子结点,所以第i层上的结点数至多为第(i-1)层上结点数的m倍,即至多为mi-2×m=mi-1个,这与命题相同,故命题成立。性质3高度狗为h的m次树霉至多穷有援个头结点名。证明询：由妄树的满性质2可知,第i层上订最多撇结点乒数为mi-方1(i文=1绳,2困,…探,h泻),显然圣当高货度为h的m次树(即度莫为m的树)上每盈一层值都达楚到最唤多结抗点数脑时,整个m次树佩具有鄙最多锄结点泪数,因此寸有：整个缓树的末最多他结点湖数=每一从层最堤多结加点数镇之和=m0+m1+m2+…璃+mh-芳1=。性质4具有n个结苹点的m次树夫的最险小高忌度为lo鹿gm(n虹(m辰-1框)+孤1)。证明徐：设滔具有n个结推点的m次树定的高惯度为h,若在药该树阳中前h-法1层都读是满山的,即每爸一层仅的结斗点数络都等序于mi-脱1个(1很≤i她≤h云-1萝),第h层(即最和后一里层)的结顷点数档可能斤满,也可习能不内满,则该奔树具害有最向小的罢高度庸。其纵高度h可计坡算如飘下：根据弊树的朵性质3可得烤：骗＜n≤乘(m回-1注)后得帝：mh-洪1＜n(险m-削1)蓬+1逐≤mh以m为底举取对禾数后吉得：h-旺1＜lo银gm(n倚(m液-1锯)+劲1)距≤h即lo化gm(n须(m飘-1受)+鸡1)肿≤h＜lo刺gm(n爱(m肺-1骡)+陆1)角+1因h只能驴取整溜数,所以h=lo新gm(n硬(m粒-1蝇)+雨1)结论丹得证队。例7.防1含n个结概点的愧三次洋树的挪最小替高度下是多拦少？解：饼设含n个结旧点的(为完膊全三虎次树慰时高悠度最猎小)的三叔次树馆的最盟小高挂度为h,则有钞：1+笼3+益9+奸…+胃3h-洋2＜n≤窄1+挪3+主9+口…+遍3h-跌1(3h-捎1-1寻)/都2＜n≤桌(亚3h-1轰)/茂23h-弦1＜2n掀+1至≤3h即：h=lo站g3(2懒n+及1)7.找1.格5树的叠基本待运算树的继运算按主要机分为址三大勉类：第一椅类,寻找珠满足衡某种开特定群关系饰的结带点,如寻虎找当常前结顶点的戚双亲府结点唇等；第二吐类,插入游或删途除某拣个结校点,如在脊树的荐当前拌结点着上插戒入一少个新袭结点豆或删番除当唉前结出点的匆第i个孩穷子结乖点等弟；第三昼类,遍历于树中贪每个笼结点,这里舟着重即介绍舍。树的警遍历洒运算封是指稠按某东种方弯式访乐问树闷中的忍每一引个结熟点且宋每一煮个结隔点只廊被访荐问一夏次。前树的世遍历踪蝶运算途的算衔法主嘉要有旋先根壳遍历田和后抢根遍沫历两渴种。贱注意,下面区的先贫根遍云历和摔后根舅遍历乘算法烧都是警递归桌的。1.先根恼遍历先根因遍历扶过程却为：(1耀)访问骆根结盟点；(2兼)按照歼从左辜到右书的次康序先浓根遍旺历根生结点过的每慨一棵包子树永。2.后根千遍历后根亭遍历诞过程晋为：(1允)按照贺从左庙到右府的次摘序后排根遍哗历根竟结点甘的每北一棵心子树看；(2虾)访问教根结娇点。7.呜1.风6树的内存储欧结构1.双亲膀存储碰结构这种厚存储但结构舒是一疫种顺块序存史储结恩构,用一颤组连傅续空址间存买储树蚂的所输有结草点,同时找在每井个结伞点中联附设谊一个烂伪指革针指雹示其璃双亲罚结点美的位河置。树的每双亲燥存储柱结构辅示意陶图2.孩子问链存躺储结赖构孩子帜链存虏储结野构可桨按树远的度(即树累中所桐有结披点度本的最巩大值)设计漏结点晌的孩国子结晓点指残针域治个数榨。下欺图(a搭)的树语对应歼的孩约子链滴存储叶结构逐如图(b衡)所示童。树的孩子武链存储虫结构颤示意仿图3.孩子狱兄弟珠链存鸡储结务构孩子月兄弟僚链存拼储结伟构是肯为每抬个结浊点设钓计三忘个域巧：一税个数嫁据元民素域,一个浸该结染点的华第一否个孩握子结毫点指娘针域,一个贸该结钳点的康下一防个兄除弟结室点指掩针域霞。下收图(a宏)的树禁对应比的孩车子兄味弟链悉存储兆结构籍如图(b度)所示卖。树的孩子评兄弟亮链存储致结构乒示意蛋图7.薪2二叉渣树概汗念和纲性质7.哑2.猾1二叉耕树概引念7.狗2.学2二叉雷树性贪质7.果2.筒3二叉奇树与吧树、裂森林奏之间律的转拾换7.层2.巨1二叉衫树概凉念二叉呈树也拢称为躬二次行树或晴二分步树,它是骄有限厕的结器点集糖合,这个绵集合融或者昆是空,或者谜由一序个根许结点筑和两次棵互测不相闲交的世称为川左子接树和预右子眉树的织二叉欺树组撒成。二叉杠树的黄定义沃是一录种递故归定源义。二叉广树有宴五种斤基本谢形态,如下修图所突示,任何由复杂滚的二均叉树匹都是呆这五挽种基菜本形常态的棉复合扑。从定膏义看麦到,二叉揪树是冻一种率特殊梦的树,其表阵示法樱也与竞树的垄表示饥法一患样,有树省形表押示法泥、文湿氏图族表示钩法、欠凹入旦表示振法和省括号写表示丹法等策。在一拉棵二竭叉树役中,如果乘所有书分支窗结点解都有牲左孩巡寿子结当点和滔右孩控子结哪点,并且习叶结版点都激集中鹅在二石叉树岁的最录下一病层,这样急的二赠叉树鲁称为满二阳叉树。下桶图所说示就搜是一纤棵满沫二叉邪树。校可以滑对满现二叉燥树的链结点桥进行波连续帆编号,约定盐编号控从树拿根为1开始,按照散层数慰从小唱到大饱、同亡一层球从左鹿到右拨的次盟序进共行。朱图中野每个脉结点控外边宋的数露字为玩对该促结点狂的编松号。若二抱叉树叠中最信多只牌有最糊下面搬两层峡的结颜点的借度数抵可以叮小于2,并且偶最下子面一虑层的电叶结浸点都依龙次排脏列在瓜该层他最左箭边的医位置谊上,则这何样的荣二叉象树称不为完全蜘二叉桨树。如骑下图春所示元为一动棵完筐全二问叉树祥。同磁样可坟以对变完全纯二叉亿树中港每个狮结点胆进行畜连续雀编号,编号吧的方倾法同仔满二场叉树述相同雨。图副中每趴个结柳点外踏边的意数字岗为对第该结林点的缓编号互。7.窃2.伤2二叉尺树性犯质性质1非空抄二叉企树上尊叶结剃点数华等于岸双分金支结准点数劈燕加1。证明牙：设缓二叉电树上蜘叶结卸点数猎为n0,单分阁支结依点数疏为n1,双分启支结药点数染为n2,则总困结点薄数=n0+n1+n2。在一彻棵二取叉树灰中,所有匆结点混的分捎支数(即度累数)应等波于单武分支设结点颈数加晒上双叠分支作结点损数的2倍,即总枪的分赖支数=n1+2漫n2。由于丈二叉舱树中么除根柔结点匠以外,每个沾结点板都有打惟一赠的一腐个分光支指且向它,因此饱二叉宪树中且有：集总的愿分支蠢数=总结着点数-1。由上结述三冠个等希式可蜻得：n1+2葬n2=n0+n1+n2-1即：n0=n2+1性质2非空比二叉专树上笨第i层上哀至多懒有2i-袭1个结命点,这里攻应有i≥赚1。由树检的性摄质2可推推出。性质3高度右为h的二闭叉树莲至多石有2h-1个结姻点(h葬≥1柴)。由树伞的性糊质3可推传出。性质4对完痒全二瞒叉树蜡中编喜号为i的结颗点(1堵≤i帽≤n陈,n什≥1免,n为结亿点数)有：(1颂)若i≤n号/2捆,即2i裁≤n溜,则编径号为i的结妇点为劝分支数结点,否则毯为叶哪子结心点。(2富)若n为奇便数,则每躺个分尽支结纱点都伶既有轻左孩及子结硬点,也有侦右孩慌子结钢点；拉若n为偶抄数,则编仔号最针大的局分支肿结点(编号功为)只有左左孩仙子结顷点,没有劲右孩御子结大点,其余租分支庆结点禁都有改左、务右孩末子结然点。(3征)若编岸号为i的结斜点有陷左孩退子结举点,则左召孩子统结点鬼的编虚号为2i；若编基号为i的结振点有输右孩无子结各点,则右抬孩子胀结点卸的编灵号为(2图i+气1)。(4援)除树起根结墙点外,若一流个结晒点的爪编号擦为i,则它提的双灰亲结汗点的傍编号谎为i/温2,也就全是说,当i为偶简数时,其双她亲结会点的风编号陕为i/粪2,它是盾双亲总结点收的左棕孩子其结点,当i为奇俗数时,其双客亲结梁点的贺编号瞒为(i卫-1乌)/宽2,它是篇双亲碑结点着的右缴孩子伏结点枕。性质5具有n个(n＞0)结点蹦的完冬全二对叉树秀的高跑度为lo瓶g2(n自+1丑)或lo闹g2n+1。由完享全二眼叉树汉的定谈义和厕树的卷性质3可推货出。7.盼2.隶3二叉壮树与慰树、揪森林尤之间混的转贯换1．森即林、唇树转姐换为嘱二叉疫树(1渡)在所视有相罗邻兄弓弟结冲点(森林蚁中每朴棵树珍的根缴结点邻可看子成是丹兄弟轿结点)之间偶加一蜘水平钩连线犯。(2裁)对每最个非倍叶结俊点k,除了李其最院左边趣的孩度子结晕点外,删去k与其步他孩涛子结浅点的土连线枝。(3搏)所有悄水平循线段喊以左学边结摆点为侨轴心宪顺时含针旋哥转45度。通过被以上公步骤,原来框的森血林就砍转换相为一泳棵二摄叉树激。一佛般的词树是温森林翼中的有特殊肯情况,由一岔般的沾树转桨换的窗二叉浙树的炕根结惭点的换右孩傅子结枯点始吵终为升空,原因糟是一还般的快树的树根结可点不擦存在竟兄弟急结点彩和相汁邻的炉树。将森丛林转把换为本二叉店树的究过程2.二叉唐树还猎原为性森林仇、树(1伟)对于跨一棵凯二叉亩树中虽任一工结点k0,沿着k1右孩恼子结联点的毁右子合树方节向搜虽索所饶有右羽孩子民结点,即搜填索结僚点序牲列k2,k3,…妙,km,其中ki+负1为ki的右斩孩子惕结点(1皂≤i＜m)璃,km没有忘右孩庄子结说点。(2鸟)删去k1,k2,…慎,km之间享连线火。(3吨)若k1有双蓄亲结剩点k,则连纷接k与ki(2仁≤i漆≤m统)。(4触)将图都形规缘瑞整化,使各做结点亭按层轻次排腥列。将一严棵二薪叉树托还原滥为树丛的过盒程7.值3二叉汇树存脱储结福构7.喊3.芦1二叉的树的虽顺序勺存储扒结构7.步3.六2二叉春树的灰链式计存储绣结构7.淘3.倘1二叉姑树的扛顺序脸存储巨结构二叉液树的衣顺序胡存储穷结构讲中结拼点的损存放粥次序俭是：唤对该贪树中档每个厦结点写进行铃编号,其编迁号从并小到柔大的朴顺序暮就是宽结点盾存放青在连伶续存情储单命元的写先后锅次序姜。若研把二螺叉树雨存储上到一哥维数倘组中,则该舞编号聪就是兵下标倚值加1(注意,C冠/C陡++语言吧中数炸组的学起始图下标置为0)。树摄中各目结点胖的编社号与胃等高铲度的扔完全室二叉经树中穗对应若位置骑上结阴点的葡编号躺相同稼。利用蛋二叉昏树的句性质4。ABCDEFGHIJK123456789101112131415顺序宜存储喊结构7.抽3.挽2二叉览树的监链式糊存储觉结构在二鲁叉树烦的链妇接存节储中,结点而的结腊构如券下:ty贝pe贩de梳fst准ru对ctno肆de{El渔em巩Ty班peda糠ta索;st浪ru岁ctno印de弯*lc摆hi厉ld,*rc求hi塑ld;}BT鸟No骂de;其中,d烛at撒a表示经值域,用于点存储使对应卖的数急据元刮素,lc胜hi蚀ld和rc闭hi哲ld分别耽表示免左指宗针域梯和右蛙指针怪域,用于抛分别骄存储萄左孩啄子结近点和齿右孩召子结尼点(即左监、右层子树水的根纪结点)的存呜储位迫置。二叉体树及哗其链研式存惯储结筑构7.位4二叉精树的虑遍历7.如4.戏1二叉软树遍连历的坟概念7.家4.汪2二叉惜树遍删历递劝归算摧法7.陶4.燃1二叉毒树遍库历的哭概念二叉锅树的断遍历也是指究按照齐一定兵次序肝访问嫩树中帮所有宣结点,并且乌每个堡结点虽仅被欧访问矛一次角的过父程。秆它是差最基欠本的合运算,是二释叉树递中所矩有其斤他运池算的牧基础谅。1.先序掠遍历先序蒙遍历其二叉叮树的沙过程嗓是：(1司)访问芝根结悔点；(2绿)先序葱遍历屠左子乳树；(3绪)先序猜遍历婆右子凭树。2.中序调遍历中序房诚遍历集二叉冷树的历过程衰是：(1步)中序炭遍历奥左子窝树；(2椒)访问砌根结材点；(3往)中序橡遍历甚右子陷树。3.后序殃遍历后序尸遍历勇二叉份树的窜过程铃是：(1亚)后序具遍历玻左子达树；(2箩)后序雨遍历洋右子链树；(3锡)访问罚根结取点。7.晓4.农2二叉关树遍析历递也归算椒法由二秆叉树澡的三筝种遍窄历过乎程直杏接得信到如史下三浙种递勒归算脾法如慈下：vo疼idPr器eO靠rd朴er时(B励TN撑od碎e*b汁)镜/耐*先序踏遍历继的递久归算键法*/{if拘(疗b!笑=N妻UL然L){pr侨in垫tf丘("郊%c",录b-篇>d糟at适a)克;考/*访问移根结奔点*/Pr勤eO冬rd镜er庙(b->lc宿hi列ld);Pr缓eO及rd施er姨(b->rc糠hi效ld);}}vo咬idIn抹Or堆de倚r(葡BT拾No内de*b肠)猫/初*中序坚遍历场的递株归算睛法*/{if孕(墙b!灶=N铜UL氧L){In嗽Or弱de让r(叨b->lc岂hi漆ld);pr端in乖tf汁("量%c",宝b-茅>d暗at事a)拍;返/*访问目根结户点*/In染Or攻de虹r(脑b->rc鲜hi幅ld);}}vo得idPo抚st充Or信de驶r(窄BT她No片de*b届)宗/*后序孝遍历浙递归贴算法厉*/{if蛮(绸b!狗=N局UL肃L){Po醋st协Or亮de邪r(邀b->lc吨hi促ld);Po习st引Or灰de妖r(绍b->rc连hi公ld);pr末in吧tf喝("拆%c",薪b-装>d饥at妨a)收;朵/*访问肥根结岗点*/}}例7.拿2假设谈二叉复树采享用二战叉链灵存储螺结构疑存储,试设疫计一鹊个算防法,输出呀一棵圣给定规二叉纹树的毁所有崭叶子汁结点有。解：佩输出絮一棵伏二叉塞树的峰所有庙叶子适结点财的递寺归模浮型f(息)如下碑：f(咬b)：不做澡任何乒事件鞭若b=剩NU慌LLf(披b)：输出微*b结点偶的da胜ta域刚若*b为叶极子结淡点f(体b)：f(彻b-霜>lc临hi歪ld竞);秆f(捎b->rc箩hi登ld)其他确情况vo认idDi脱sp京Le鼠af假(B担TN胖od悦e*b省){if型(似b!努=N们UL凭L){if伐(妹b-瓶>lc灾hi色ld==种NU严LL堡&涉&游b-扔>rc施hi旷ld==凤NU多LL沾)pr采in强tf蚀("甘%c",闪b-袜>d已at晓a)拜;el早se{Di端sp柳Le脑af呆(b->lc佣hi兵ld);Di舒sp狂Le讽af度(b->rc细hi金ld);}}}7.参5二叉挣树的刃基本冈运算罗及其滥实现7.童5.混1二叉队树的日基本雪运算跨概述7.勒5.仁2二叉孩树的昌基本龙运算终算法括实现7.课5.帅1二叉材树的榨基本灿运算蹈概述归纳袋起来,二叉握树有亏以下扯基本价运算累：(1狸)创建数二叉素树Cr回ea栋te改BT初No焦de(*县b,荣*st见r)：根据直二叉黑树括岗号表蚁示法裙的字悼符串撒*st滑r生成禾对应逆的链阅式存顺储结限构。(2鱼)查找佩结点Fi结nd逗No叮de(*推b,充x)：在二咳叉树b中寻墙找da蚀ta域值宽为x的结陆点,并返恳回指坏向该暴结点帽的指窗针。(3慕)找孩泥子结伏点Lc怠hi亮ld赛No扒de惊(p)和Rc师hi厘ld郊No伐de亩(p)：分别淋求二徒叉树竭中结梢点*p的左厚孩子古结点脾和右亦孩子醒结点快。(4有)求高轻度BT粉No伍de命De讨pt牺h(*领b)：求二症叉树b的高酷度。蔽若二遇叉树骗为空,则其劈燕高度得为0；否剥则,其高器度等恼于左嫌子树缩慧与右班子树杰中的驰最大恨高度搜加l。(5朗)输出袋二叉蹄树Di蓬sp错BT学No捎de(*子b)：以括良号表摇示法木输出侄一棵牺二叉确树。7.授5.踪蝶2二叉糟树的健基本丑运算圾算法滥实现(1券)创建疑二叉欠树Cr汉ea滥te繁BT宅No捕de(*方b,贷*st才r)用ch扫描溉采用岂括号问表示匪法表江示二联叉树功的字芒符串岩。分谊以下纳几种奶情况想：①偿若ch='弯('：则将乓前面洲刚创到建的恭结点斤作为嘉双亲投结点离进栈,并置k=程1,表示瓶其后过创建奋的结久点将外作为瞧这个轻结点追的左个孩子种结点维；②退若ch='戚)'：表示份栈中泡结点集的左很右孩叛子结供点处姿理完蛇毕,退栈渠；③竿若ch='摩,'：表示捧其后蹲创建鞠的结耀点为慢右孩究子结摄点；④赞其他亲情况,表示些要创叙建一赠个结利点,并根睡据k值建贪立它它与栈短中结盗点之浸间的蒙联系,当k=错1时,表示滤这个听结点点作为匆栈中举结点势的左济孩子愤结点,当k=愧2时,表示渣这个雅结点法作为桂栈中膀结点爱的右冶孩子拾结点靠。如滴此循蜓环直把到st良r处理流完毕租。算叠法中衔使用责一个宵栈St保存少双亲犯结点,t尼op为其良栈指仁针,k指定城其后牌处理猫的结恭点是恭双亲稍结点(保存现在栈骄中)的左恭孩子著结点(k表=1兵)还是笨右孩邻子结俊点(k右=2晋)。vo衡idCr辜ea将te助BT卖No勉de舅(B痕TN争od也e*值&b撕,c演ha指r恩*st皂r){BT振No拴de*St搬[M槽ax砖Si嫩ze],傻*p吐=N少UL场L;in激tto聪p=察-1怖,k健,j多=0警;ch萝arch;b=捕NU钱LL井;本/*建立何的二涂叉树怪初始龙时为饿空*/ch=st捏r[野j];wh融il玻e顾(ch!=惠'\吹0'塌)鸣/*st题r未扫怖描完疯时循是环*/{sw音it伶ch含(c葛h){ca壁se暑'陶('权:t贸op嫌++挺;S热t[屈to搅p]键=p胆;k谦=1扯;巧br杏ea朵k;/*为左婆孩子药结点阻*/ca覆se邻'他)'旱:t狱op富--胆;b造re滩ak寸;ca拖se战'惕,'译:k误=2塑;品br岭ea末k;/*为孩叙子结政点右株结点济*/de论fa邮ul铃t:刷p=茶(BT禾No阁de*)ma绵ll织oc颂(s差iz梳eo减f(硬BT博No责de))泪;p-疲>d蜻at炊a=ch饲;p->lc抖hi膊ld=p剂->rc存hi窗ld=N奶UL佛L;if仁(瞒b=简=N盲UL蝴L)壤/*超*p为二之叉树减的根柏结点鸟*/b=浊p;el榆se娘/*已建这立二些叉树北根结尸点*/{舅s踪蝶wi桐tc虑h(彻k){ca活se跟1馅:S丸t[买to禾p]砌->lc乡丰hi洋ld=p功;b义re伸ak慕;ca讨se告2遭:S肉t[伴to朱p]您->rc贵hi斜ld=p监;b张re猎ak杜;}}}j+旗+;柿ch=st豆r[阁j];}}例如,对于战括号靠表示想串A(的B(朱D(插,G裁))吐,C桑(E洲,F械))葵,建立怜二叉耐树链端式存疮储结堵构的役过程犯如下月表所谎示。ch算法执行的操作St中元素A建立A结点,b指向该结点空(A结点进栈,k=1AB建立B结点,因k=1,将其作为A结点的左孩子结点A(B结点进栈,k=1ABD建立D结点,因k=1,将其作为B结点的左孩子结点ABch算法执行的操作St中元素(D结点进栈,k=1ABD,k=2ABDG建立E结点,因k=2,将其作为D结点的右孩子结点ABD)退栈一次AB)退栈一次A,k=2AC建立C结点,因k=2,将其作为A结点的右孩子结点A(C结点进栈,k=1ACE建立E结点,因k=1,将其作为C结点的左孩子结点AC,k=2ACch算法执行的操作St中元素F建立F结点,因k=2,将其作为C结点的右孩子结点AC)退栈一次A)退栈一次空ch扫描完毕算法结束

生成经的二逆叉树遣＝＞(2昂)查找助结点Fi跟nd案No亲de(*叫b,桶x)采用摊先序锋遍历趋递归趴算法王查找叫值为x的结浇点。衰找到恨后返拐回其均指针,否则观返回NU征LL。算法灭如下犯：BT那No物de*Fi冷nd败No液de疯(B势TN辟od立e*b,据El昼em芳Ty然pex){BT像No阶de*p球;if冒(类b=芳=N沿UL它L)习r洒et镇ur樱n桃NU翻LL竟;el舒se律i凯f额(b忽->股da萄ta辫==撇x)蜂r守et掠ur津n螺b;el控se{始p屑=Fi圾nd腐No斥de仆(b->lc饼hi艳ld碎,x);if熔(茅p!喘=N泉UL渐L)港r阴et风ur凉n抱p;el崭se疗r场et帝ur衫nFi愁nd痒No触de片(b->rc植hi貌ld从,x);}}(3盒)找孩桌子结恳点Lc齿hi秀ld掀No绘de咬(p)和Rc应hi最ld彩No越de混(p)直接畏返回闭*p结点尸的左柏孩子束结点爷或右福孩子续结点舱的指蜡针。争算法甩如下装：BT非No景de*Lc得hi专ld迅No估de绑(B眼TN葬od住e*p痰){re失tu舟rn门p减->lc原hi蛮ld;}BT私No导de*Rc愿hi熔ld淹No防de宝(B拐TN责od木e*p借){re村tu生rn联p射->rc营hi附ld;}(4茅)求高河度BT税No铃de挪De尸pt求h(*搂b)求二肯叉树摸的高悦度的余递归化模型f(坝)如下贸：f(缘瑞NU蚁LL虚)=菌0f(胃b)工=M贱AX描{f砖(b余->lc姐hi交ld智),今f(搂b->步rc津hi巩ld鄙)}成+1其他笼情况对应毅的算在法如短下：in膛tBT猎No希de普De跃pt宴h(建BT忠No颗de*b够){in潜tlc搞hi顶ld侵de婶p,凡rc额hi睡ld亏de菜p;if狠(海b=删=N螺UL收L)奏r队et禽ur毙n(逆0)秘;调/*空树灾的高苹度为0*孟/el帜se{lc符hi侄ld臂de另p=BT亡No轻de册De傍pt宣h(辰b->lc票hi抖ld);/*求左宿子树解的高宴度为lc越hi歇ld童de断p*/rc锻hi甲ld盼de挥p=BT朴No帜de土De赶pt深h(同b->rc校hi屿ld);/*求右妇子树缸的高趴度为rc散hi填ld喷de课p*/re定tu什rn诵(l虏ch照il令dd饮ep>rc浪hi句ld类de末p)?(l锋ch嫂il球dd铸ep留+1途):券(r骂ch查il标dd辽ep届+1梅);}}(5恋)输出无二叉软树Di旷sp哀BT燥No亡de(*座b)其过吵程是婚：对映于非打空二日叉树b,先输馒出其网元素掏值,当存炒在左风孩子盏结点猜或右谎孩子均结点残时,输出走一个耽“(”符号,然后穴递归档处理腹左子溪树,输出掌一个瓦“,”符号,递归串处理鞠右子亏树,最后痒输出舅一个臂“)”符号当。对弯应的纪递归初算法反如下肥：vo滩idDi徒sp欠BT姿No残de挥(B千TN帽od顷e*b毕){窝if浇(凭b!秆=N戚UL廊L){pr瞧in规tf丽("请%c挤",旺b->勉da现ta船);if该(肿b-婆>lc怀hi潜ld!=伞NU芽LL糖|采|务b-闻>rc域hi浸ld!=渠NU士LL荣){pr激in趋tf("坡("吨);Di航sp显BT追No馋de歉(b->lc中hi矮ld);/*递归蛛处理趋左子处树*/if涉(掘b-浩>rc害hi萝ld!=欺NU距LL羽)pr屡in赠tf("难,"宏);Di帅sp练BT吨No变de非(b->rc寺hi酿ld);/*递归钳处理术右子躁树*/pr碍in询tf("独)"秧);}}}例7.极3假设轮二叉喝树采题用二否叉链流存储碌结构,设计颤一个金算法既判断棚两棵努二叉劲树是香否相色似,所谓茎二叉写树t1和t2是相辩似的鬼指的闻是t1和t2都是低空的武二叉忆树；颗或者t1和t2的根半结点叠是相六似的,以及t1的左垦子树斩和t2的左你子树钢是相免似的躬且t1的右寄子树欧与t2的右讽子树闹是相孩似的酬。解：凶判断细两棵欧二叉映树是别否相伴似的熟递归屯模型f(湖)如下谈：f(来t1废,t衣2)镜=t息ru茅e若t1鸣=t校2=凶NU香LLf(石t1思,t凶2)仗=f凶al汇se若t1、t2之一裹为NU任LL你,另一衣不为NU涝LLf(汪t1盘,t辽2)耕=f忽(t伪1-稀>l锄ch哀il每d,趋t2导->lc室hi快ld)煤&其他欧情况f(势t1真->冒rc赠hi颜ld射,t遍2-行>rc谦hi及ld)对应右的算仰法如校下：in这tLi勾ke窃(B山TN悟od接e*b笼1,航BT芹No舱de耗*蓝b2银)/*粉t1和t2两棵枕二叉要树相战似时悲返回1,否则齿返回0*僻/{in宅tli塔ke遣1,秤li分ke沫2;if赔(县b1喘==美NU椅LL累&贯&拦b2帅==楚NU邪LL写)适re孝tu株rn闲1游;el变se昆i鞭f氏(b顾1=耳=N阿UL魂L傲||遵b注2=榜=N蕉UL渴L)丝式re伯tu跌rn涛0芬;el螺se{能l担ik贩e1鞠=L季ik涉e(谁b1茅->畅lc骄hi惩ld厨,b瞧2-楚>lc壶hi伶ld);li暴ke旦2=董Li跌ke叙(b瓦1-唇>r饺ch燃il度d,忆b2士->rc辛hi懂ld);re侨tu详rn华(副li绞ke要1旬&致li陆ke伍2)睁;劈燕/次*返回li别ke框1和li毙ke盟2的与犁*/}}例7.衣4假设界二叉痒树采纯用二他叉链离存储罢结构,设计革一个自算法Le惭ve锅l(平)求二迎叉树听中指捡定结薪点的令层数边。并吐利用止本节国的基怜本运乔算编古写一钩个完暖整的汪程序,建立栗教材闪中图7.修8(景a)的二幻玉叉树踩的二找叉链,对于玻用户绩输入团的任塔何结妈点值创计算陡出在香该二宫叉树石中的捎层次纺。解：哲本题尿采用利递归召算法,设h返回p所指坐结点克的高仔度,其初渣值为0。找租到指挑定的否结点灶时返贴回其度层次糊；否疫则返霉回0。lh作为剂一个督中间拢变量陵在计堤算搜辫索层充次时淋使用,其初很值为1。对纯应的诞算法洽如下汪：vo啊idLe毫ve侧l(而BT速No售de*b,驼BT山No赤de*p,嫌in箭t&h,艳in灿tlh)/*找到严*p结点俊后h为其丧层次,否则其为0*号/{芝i序f阴(b斑==竹NU谷LL誓)木h=彼0;妻/*空树产时返草回0*旅/el贴se警i筒f葬(p猾==访b)笨h=lh;敲/逢*找到猴结点p时*/el那se{闯Le顾ve双l(循b-咽>l董ch挪il热d,被p,吓h,竟lh羞+1佣);根/雷*在左地子树甲中递肥归查蚀找*/if接(亭h=虚=0类)速/*左子瓣树中疯未找旺到时扮在右疏子树斜中递歌归查平找*/Le肆ve释l(裙b-震>r悠ch送il叙d,伏p,姐h,指lh趁+1拴);}}例7.日5假设楚二叉寒树采浆用二执叉链贩存储擦结构,设计找一个瓣算法粗输出强从每速个叶经子结艺点到休根结顿点的惯路径凳。解：倚这里洪用层瓶次遍脆历方疲法,设计播的队宽列为雨非循遭环顺肃序队个列(类似关于第3章3.脏2.登4小节务中求型解迷陕宫问栽题时木使用泰的队迫列)将所曾有已您扫描卡过的礼结点跪指针皆进队,并在违队列汁中保全存双兼亲结并点的什位置遥。当东找到击一个猎叶子范结点凝时,在队贸列中融通过漏双亲杆结点灶的位西置输屡出该蚊叶子律结点霉到根军结点卧的路富径。棒对应狐的算技法如砖下：vo议idAl辫lP宗at剧h(悲BT症No休de*b帜){st负ru舰ctsn狂od树e{BT熊No汽de*n味od宋e;亏/哨*存放壶当前缎结点跃指针弟*/in柔tpa桥re跃nt疤;观/糕*存放够双亲留结点虏在队躬列中垫的位惯置*/}q[牛Ma歼xS预iz寺e];贯/*定义姻顺序捡队列扯*/in脊tfr赤on态t,按re到ar研,p五;联/挽*定义俱队头货和队边尾指恼针*/fr律on零t=赴re庆ar决=-抽1;车/*置队巡寿列为干空队祸列*/re翠ar雨++授;q逃[r黑ea扭r]胆.n轨od崖e=们b;关/*根结煮点指氏针进处入队仙列*/q[虾re扩ar蹄].朗pa柱re熄nt皂=-互1;偷/前*根结川点没散有双宿亲结理点*/wh衔il舰e皇(f己ro带nt价<r狮ea肾r)迅/*队列钻不为非空*/{咽f卷ro罗nt诉++范;b=锻q[术fr忌on恋t]症.n哄od幕e;冶/恳*队头努出队习列*/if临(尚b-胀>lc恶hi烦ld==消NU现LL朋&硬&屋b-犬>rc焰hi雹ld==第NU雾LL沸){pr丛in汁tf描("塘%c到根泻结点驳路径:"脖,b举->腥da朝ta缠);p=替fr纳on关t;wh货il尘e膝(q同[p钉].耀pa外re租nt腊!=零-1足){pr哥in软tf堪("泳%c->擦",热q[切p]冠.n年od廉e-普>d订at压a)励;p=专q[巷p]园.p惩ar施en挂t;辱}pr塘in终tf音("浅%c益\n拳",险q[议p]惑.n称od还e->国da插ta流);}if舌(秩b-狠>lc枪hi在ld!=错NU刘LL弟)逝/饶*左孩误子结哪点入颜队列咬*/{精r宏ea颜r+厕+;完q龟[r榨ea驴r]橡.n育od好e=卵b-洪>lc仙hi幼ld;q[挖re买ar丸].感pa柔re羞nt罢=f雁ro跳nt鄙;搭}if刃(愈b-栋>rc疾hi夕ld!=侮NU讽LL公)肃/*右孩孔子结梁点入撞队列吵*/{猴r裕ea内r+颤+;惨q肃[r桶ea耻r]抵.n彼od藏e=鹊b-橡>rc芝hi珠ld;q[诵re瓣ar铜].肠pa坟re怪nt佩=f到ro扑nt档;革}}纺/*葬en沙d颤of肥w软hi摇le妻*/}7.夹6二叉撑树的锣构造同一犬棵二剃叉树靠具有茄惟一耳先序哭序列陕、中溪序序馒列和景后序弄序列,但不绞同的被二叉避树可钳能具仅有相外同的蔽先序增序列语、中饥序序已列和央后序宋序列何。例如,如教跃材中周图7.欣9所示喂的5棵二烦叉树,先序侵序列兵都为AB凝C。如图7.华10所示召的5棵二姜叉树,中序挂序列撕都为AC拥B。如图7.少11所示输的5棵二隶叉树,后序说序列询都为CB屡A。显然,仅由写一个纤先序愚序列(或中扭序序念列、话后序门序列),无法丸确定亿这棵趴二叉耍树的悦树形浮。但凳是,如果饱同时谅知道卫一棵巾二叉铺树的纸先序剃序列翠和中芽序序候列,或者喜同时修知道壮中序久序列石和后糟序序病列,就能悦确定斤这棵探二叉锣树。定理7.灵1：任俊何n(洲n≥含0)个不共同结揉点的查二又便树,都可喜由它帅的中润序序绍列和和先序奸序列妇惟一蒸地确找定。采用号数学贯归纳皮法证枣明。当n=梨0时,二叉四树为科空,结论拿正确叔。假设伍结点迷数小齐于n的任闲何二有叉树,都可融以由况其先轿序序危列和别中序伍序列铲惟一吐地确挥定。已知涌某棵葬二叉愚树具流有n(侧n＞0)个不论同结橡点,其先处序序伴列是a0a1…an-卷1；中序血序列防是b0b1…bk-铃1bkbk+却1…bn-敲1。因为链在先仗序遍员历过亲程中,访问疫根结献点后,紧跟盖着遍错历左豪子树,最后索再遍旦历右派子树巾。所潮以,a0必定掌是二毒叉树马的根乌结点,而且a0必然凉在中争序序椅列中羊出现起。也版就是泪说,在中孙序序踢列中剃必有督某个bk(0福≤k慕≤n都-1依)就是窝根结济点a0。由于bk是根坟结点,而在孝中序莫遍历闷过程蹦中,先遍类历左页子树,再访渗问根阀结点,最后夹再遍筐历右陈子树国。所昆以在望中序贪序列爱中,b0b1…bk-猜1必是跪根结歇点bk(也就俯是a0)左子湾树的羽中序昆序列,即bk的左携子树悔有k个结乔点(注意,k励=0表示伸结点bk没有脆左子堡树。)而bk+枝1…bn-坟1必是袄根结调点bk(也就决是a0)右子悄树的滤中序撒序列,即bk的右镜子树掠有n-他k-进1个结污点(注意,k涌=n罩-1表示杯结点bk没有塞右子什树。)。另外,在先削序序茄列中,紧跟请在根罗结点a0之后览的k个结需点a1…ak就是械左子申树的源先序椒序列,ak+注1…an-雪1这n-妙k-狱1就是态右子英树的用先序断序列赖。根据因归纳般假设,由于屋子先明序序伪列a1…ak和子疗中序欺序列b0b1…bk-塞1可以疾惟一泡地确柴定根炊结点a0的左门子树,而子洽先序煎序列ak+债1…an-啊1和子半中序蛛序列bk+帅1…bn-栽1可以傻惟一揪地确趋定根杜结点a0的右街子树丙。综上纳所述,这棵盯二叉届树的攀根结菊点己歼经确遮定,而且抢其左好、右壁子树什都惟蛇一地交确定姨了,所以采整个你二叉市树也台就惟捆一地窗确定叠了。例如,已知持先序机序列芒为AB兆DG醉CE坑F,中序姨序列梨为DG宣BA散EC鲁F,则构仍造二缘瑞叉树挖的过蚁程如荷下所佣示。根结权点：A左先睬序:B好DG左中渐序:D趣GB右先喇序:C攻EF右中东序:E提CF根结匙点：B左先施序:D尤G左中凭序:D谎G右先岸序:空敌右序中序:空根结伟点：D左先霸序:空汪左中技序:空右先蛛序:G右中更序:G根结杰点：G左先埋序:空税左中江序:空右先论序:空游右中乳序:空根结枯点：C左先奥序:E左中之序:E右先哲序:F右中管序:F根结耻点：E左先许序:空树左中拢序:空右先阁序:空钓右中约序:空根结听点：F左先朝序:空馅左中租序:空右先控序:空坛右中钢序:空由上中述定文理得丈到以末下构炉造二达叉树叼的算粒法：BT忠No放de*C劲re嘉at膀eB懒T1糕(c师ha限r榜*p客re栏,c汇ha芽r拜*in啦,i然ntn){BT顿No正de*s多;絮c剂ha刻r哀*p喝;in庄tk;if住(卡n<坏=0笑)展re旺tu刑rn松N梢UL裂L;s=候(BT皂No佣de*)ma馆ll熄oc祥(s川iz即eo肠f(沃BT念No霸de))竭;毁/着*创建鼠结点跌*s*该/s-茅>d然at拾a=馅*p老re绑;fo绪r畜(p东=i抬n;圣p<荷in渠+n涂;p默++符)泡/尘*在中驳序中库找为彩*pp梦os的位叨置k*穗/if捷(剧*p详==艘*p蛾re蹈)br兆ea郊k;k=苦p-秆in晋;s-寺>lc饮hi娇ld=C瓦re炼at鼠eB悄T1卫(p暮re范+1叛,i思n,扯k)栋;扬/*递归折构造触左子脆树*/s-绩>rc盼hi蜻ld=C馋re悄at使eB亚T1来(p劈燕re欺+k贱+1功,p失+1芹,n烈-k磨-1共);降/跌*构造革右子者树*/re瞧tu限rn晴s走;}定理7.妨2：任何n(莫n＞0)个不周同结情点的越二又煤树,都可闯由它回的中伏序序摩列和汉后序哥序列构惟一栽地确修定。同样狮采用减数学莲归纳足法证赴明。实际永上,对于渴根结榜点ak的左普右子彼树,在确痕定左至右子叶树的良子中怪序序佛列后,不需槐要确挪定左润右子篮树的准整个阳子后神序序却列,只需妻确定江子中庆序序辆列中请全部混字符凝在后泛序序言列中狸最右座边的挂那个爹字符威即可,因为袭这个踢字符裙就是假子树粉的根拢结点班。例如,已知渐中序刊序列颤为DG畅BA奇EC拐F,后序乱序列购为GD级BE迈FC喇A。对应机的构端造二马叉树饼的过刊程如服下所口示。根结刻点：A左中答序:D射GB左根:B右中准序:E叼CF右根:C根结佣点：B左中尺序:D屿G左根:D右中姥序:空锯右根:空根结羊点：D左中豆序:空职左根:空右中痕序:G右根:G根结祝点：G左中闻序:空厘左根:空右中猫序:空暖右根:空根结众点：C左中紫序:E左根:E右中哭序:F右根:F根结玩点：E左中续序:空难左根:空右中羊序:空边右根:空根结恋点：F左中萝序:空昏左根:空右中津序:空跨右根:空由上探述定缘瑞理得臭到以猜下构琴造二帮叉树须的算透法：BT剖No毛de*C字re均at骑eB矛T2脖(c想ha珠r至*p抖os述t,乌ch踩ar躬*in少,i求ntn,养in反tm){BT菌No辩de*s开;c封ha养r掀*p头,*嘴q,蝇*ma垄xp尖;i枯ntma孟xp赔os许t,匙ma鬼xi适n,箱k;if出(调n<猫=0线)酱re资tu绿rn潜N普UL柳L;ma鹿xp垄os般t=-墓1;fo销r跨(p姻=i拴n;蚁p<济in福+n扛;p涨++刑)帽/爽*求in在po户st中最碧右边爬的那告个字唱符*/fo邮r待(q群=p忠os跑t;低q<据po昏st蒜+m校;q叹++抱)萌/*在in中用ma猴xp指向龄这个格字符,用ma肚xi但n标识士它在in中的靠下标疗*/if牙(膜*p文==棚*q桶){拘k=片q-赵po旁st庙;if恶(涛k>ma诵xp库os冷t){ma放xp裹os梳t=k止;ma的xp=p优;ma前xi砍n=p渗-i西n;宏}}s=双(BT警No豪de*)ma际ll戴oc妄(s胁iz推eo刃f(饼BT富No姑de))诉;起/*创建自二叉怕树结隆点*s*蝴/s-最>d逆at脾a=po扣st尼[m吉ax栏po丽st];s-村>lc沫hi烟ld=C民re渗at虹eB增T2祥(p但os徒t,棕in锹,m寄ax针in纹,m市);/*递归野构造坚左子秀树*/s-离>rc队hi杠ld=C伟re以at喂eB揪T2详(p影os捉t,晃ma星xp张+1巧,n嫁-m吩ax孔in垄-1肺,m衰);/*递归拖构造沟右子症树*/re饺tu鞭rn索s紧;}7.延7线索葱二叉烫树7.盖7.彻1线索竖二叉痒树的法概念对于绩具有n个结壳点的酸二叉卵树,采用骨二叉萍链存筛储结叨构时,每个模结点帅有两犬个指见针域,总共阔有2n个指傍针域,又由午于只向有n-来1个结对点被厨有效杰指针段所指倦向(n个结匙点中住只有愈树根犹结点男没有黑被有缴效指获针域刑所指泊向),则共葬有2n正-(员n-筝1)庸=n扒+1个空呼链域,我们盈知道,遍历铸二叉咏树的刃结果湖是一户个结副点的借线性册序列生。可志以利丽用这耗些空炸链域壳存放毙指向借结点鼓的前脑驱和红后继岭结点样的指餐针。蒙这样昼的指贺向该乓线性远序列珍中的搁“前涛驱”盛和“沟后继纤”的珍指针,称作赞线索恼。在结踪蝶点的霸存储纱结构恨上增掉加两端个标滴志位税来区舱分这涨两种童情况猴：左标架志lt悟ag:早0表示lc凑hi篮ld指向螺左孩拔子结传点1表示lc界hi瞧ld指向戏前驱旗结点右标舱志rt鼻ag:狱0表示rc截hi禾ld指向洁右孩咽子结厘点1表示rc过hi茂ld指向仍后继陆结点这样,每个去结点康的存降储结俘构如谜下：ltaglchilddatarchildrtag按上略述原爸则在夸二叉睡树的货每个随结点知上加拼上线堂索的后二叉熄树称瓣作线索抱二叉欠树。对丹二叉粒树以兔某种拿方式抱遍历领使其歼变为威线索防二叉种树的义过程安称作尖按该里方式着对二龙叉树尿进行线索柴化。为使浴算法满设计株方便,在线护索二取叉树厚中再鞭增加畏一个秩头结询点。伶头结闹点的da霜ta域为度空；lc促hi挑ld指向李无线许索时拉的根救结点,lt捧ag为0；rc叨hi休ld指向避按某掉种方离式遍扑历二不叉树李时的报最后还一个逢结点,rt含ag为1。教材流中图7.蛛14为图7.勇8(覆a)所示究二叉旅树的边线索逼二叉粪树。穗其中,图7.柄14岁(a改)是中锋序线框索二吃叉树(中序临序列湿为