第六章樹(shù)二叉樹(shù)

第六章樹(shù)和二叉樹(shù)一、樹(shù)的基本概念二、二叉樹(shù)、遍歷、線索化三、樹(shù)和森林四、哈夫曼樹(shù)【教學(xué)目的】掌握樹(shù)的基本概念，二叉樹(shù)的基本概念，二叉樹(shù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)以及二叉樹(shù)的操作的實(shí)現(xiàn)；掌握二叉樹(shù)與樹(shù)和森林的轉(zhuǎn)換，進(jìn)而掌握樹(shù)和森林的存儲(chǔ)結(jié)構(gòu)，利用二叉樹(shù)解決Huffman編碼的應(yīng)用【教學(xué)重點(diǎn)】二叉樹(shù)的概念、二叉樹(shù)的遞歸與非遞歸遍歷算法、線索化、二叉樹(shù)與樹(shù)、森林的轉(zhuǎn)換，Huffman樹(shù)及Huffman編碼【教學(xué)難點(diǎn)】二叉樹(shù)的非遞歸遍歷及線索化6.1樹(shù)的基本概念一、樹(shù)的定義及表示1定義樹(shù)：n（n≥0）個(gè)數(shù)據(jù)元素（結(jié)點(diǎn)）的有限集合。當(dāng)n=0，則稱為空樹(shù)；當(dāng)n>0，滿足：（1）樹(shù)中有且僅有一個(gè)特定的數(shù)據(jù)元素被稱為根結(jié)點(diǎn)。（2）當(dāng)n>1時(shí)，其余數(shù)據(jù)元素被分成m（m>0）個(gè)互不相交的子集T1，T2，...，Tm，每個(gè)子集又是一棵樹(shù),稱為根結(jié)點(diǎn)的一顆子樹(shù)。樹(shù)的幾種形態(tài)樹(shù)的特點(diǎn)（邏輯結(jié)構(gòu)）（1）樹(shù)的根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，除根結(jié)點(diǎn)之外的所有結(jié)點(diǎn)有且只有一個(gè)前驅(qū)結(jié)點(diǎn)（2）樹(shù)中所有結(jié)點(diǎn)可以有零個(gè)或多個(gè)后繼結(jié)點(diǎn)①②③2樹(shù)的表示方法直觀表示法嵌套集合表示法凹入表示法//不清晰廣義表表示法④二、基本術(shù)語(yǔ)結(jié)點(diǎn)：數(shù)據(jù)元素(的內(nèi)容及其指向其子樹(shù)根的分支統(tǒng))稱為結(jié)點(diǎn)結(jié)點(diǎn)的度：結(jié)點(diǎn)的子樹(shù)（分支）數(shù)。終端結(jié)點(diǎn)（葉子）：度為0的結(jié)點(diǎn)。非終端（分支）結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。結(jié)點(diǎn)的層次：樹(shù)中根結(jié)點(diǎn)的層次為1，根結(jié)點(diǎn)子樹(shù)的根為第2層，以此類推。樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)度的最大值。樹(shù)的深度：樹(shù)中所有結(jié)點(diǎn)層次的最大值。有序樹(shù)、無(wú)序樹(shù)：如果樹(shù)中每棵子樹(shù)從左向右的排列擁有一定的順序，不得互換，則稱為有序樹(shù)，否則稱為無(wú)序樹(shù)。森林：是m（m≥0）棵互不相交的樹(shù)的集合。孩子、雙親：結(jié)點(diǎn)子樹(shù)的根稱為這個(gè)結(jié)點(diǎn)的孩子，而這個(gè)結(jié)點(diǎn)又被稱為孩子的雙親。子孫：以某結(jié)點(diǎn)為根的子樹(shù)中的所有結(jié)點(diǎn)都被稱為是該結(jié)點(diǎn)的子孫。祖先：從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)。兄弟：同一個(gè)雙親的孩子之間互為兄弟。堂兄弟：雙親在同一層的結(jié)點(diǎn)互為堂兄弟。6.2二叉樹(shù)定義二叉樹(shù):n（n≥0）個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，稱為空二叉樹(shù)；當(dāng)n>0時(shí)，有且僅有一個(gè)結(jié)點(diǎn)為二叉樹(shù)的根，其余結(jié)點(diǎn)被分成兩個(gè)互不相交的子集，一個(gè)稱為左子集（樹(shù)），另一個(gè)稱為右子集（樹(shù)），每個(gè)子集（樹(shù)）又是一個(gè)二叉樹(shù)。二叉樹(shù)的基本形態(tài)二叉樹(shù)的性質(zhì)在二叉樹(shù)的第i層上最多有2i-1個(gè)結(jié)點(diǎn)（i≥1）深度為K的二叉樹(shù)最多有2K-1個(gè)結(jié)點(diǎn)（K≥1）（稱為滿二叉樹(shù)）對(duì)于任意一棵二叉樹(shù)，如果度為0的結(jié)點(diǎn)個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)個(gè)數(shù)為n2，則n0=n2+1二叉樹(shù)的總度數(shù)＝n1+2n2二叉樹(shù)的節(jié)點(diǎn)數(shù)＝n0＋n1＋n2二叉樹(shù)的總度數(shù)＝二叉樹(shù)的節(jié)點(diǎn)數(shù)－1n1+2n2=n0＋n1＋n2-1即：n0=n2+11234675具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1完全二叉樹(shù)：n個(gè)結(jié)點(diǎn)的二叉樹(shù)，若將它與一棵同深度的滿二叉樹(shù)中的所有結(jié)點(diǎn)按從上到下，從左到右的順序分別進(jìn)行編號(hào)，且該二叉樹(shù)中的每個(gè)結(jié)點(diǎn)分別與滿二叉樹(shù)中編號(hào)為1～n的結(jié)點(diǎn)位置一一對(duì)應(yīng)，則稱這棵二叉樹(shù)為完全二叉樹(shù)證明：假設(shè)具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為K，則根據(jù)性質(zhì)2可以得出：2K-1-1<

n≤2K-1將不等式兩端加1得到：2K-1≤n<2K取以2為底的對(duì)數(shù)，化簡(jiǎn)：K-1≤log2n<K得到：log2n=K-1。整理：K=log2n+1完全二叉樹(shù)：一棵二叉樹(shù)至多只有最下面兩層結(jié)點(diǎn)的度可小于2，且最下面一層上的結(jié)點(diǎn)都集中在該層最左邊的若干位置對(duì)于有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中的所有結(jié)點(diǎn)按從上到下，從左到右的順序進(jìn)行編號(hào)，則對(duì)任意一個(gè)結(jié)點(diǎn)i（1≤i≤n），有:如果i=1，則結(jié)點(diǎn)i是這棵完全二叉樹(shù)的根，沒(méi)有雙親；否則其雙親結(jié)點(diǎn)的編號(hào)為i/2。如果2i>n，則結(jié)點(diǎn)i沒(méi)有左孩子；否則其左孩子結(jié)點(diǎn)的編號(hào)為2i。如果2i+1>n，則結(jié)點(diǎn)i沒(méi)有右孩子；否則其右孩子結(jié)點(diǎn)的編號(hào)為2i+1。二叉因樹(shù)的僚操作Cr針ea榜te籌Bi牛Tr妥ee盆(T,尚de塑fi社ni稿ti擱on蹦);以de圍fi狂ni撿ti蜂on給出鍬二叉揮樹(shù)T的定諷義創(chuàng)溉建一性棵二乎叉樹(shù)De孔st徹ro慣yB蘇iT粱re銜e(香T);銷毀府二叉余樹(shù)T。Cl回ea規(guī)rB對(duì)iT攝re卻e(岔&T);將二英叉樹(shù)T清為意空樹(shù)尺。Pa巴re職nt蝴(T,籍e)仇;求e結(jié)點(diǎn)稱的雙全親結(jié)適點(diǎn)，瘡若e是T的非精根結(jié)聲點(diǎn)，息則返注回它湯的雙手親，終否則德返回“空”。Le窄ft田Ch刺il歐d(瓣T,警e)修;求結(jié)食點(diǎn)e的左導(dǎo)孩子砍，若e無(wú)左閉孩子必，則劉返回"空"。Ri盯gh撈tC磁hi屠ld授(T,忌e)饒;求結(jié)舉點(diǎn)e的右追孩子互，若e無(wú)左萍孩子勞，則祝返回"空"。二叉荷樹(shù)的俗操作Le柱ft仰Si堵bl能in貪g(勒T,隱e)畫(huà);求結(jié)罷點(diǎn)e的左兼兄弟征。若e是其浙雙親活的左園孩子替或無(wú)固左兄披弟，鼠則返槳回"空"。Ri更gh梳t(yī)S異ib析li繩ng鑒(T,饅e)務(wù);求e的右須兄弟蜓。若e是其吹雙親朋的右嚼孩子箭或無(wú)榮右兄圈弟，罵則返繼回“空”。In徑se息rt連Ch米il廚d(桂&T,縣p,泡L獄R,透c冠);根據(jù)LR為0或1，插膜入c為T(mén)中p所指少結(jié)點(diǎn)格的左仰或右艱子樹(shù)歇。p所指膀結(jié)點(diǎn)誰(shuí)原有扒左或壇右子軌樹(shù)成戶為c的右純子樹(shù)扭。De圖le瘋te櫻Ch牢il傍d(謊&T,鳳p,笛L慮R)妙;根據(jù)LR為0或1，刪蜜除T中p所指仙結(jié)點(diǎn)漠的左攻或右痕子樹(shù)加。其他創(chuàng)衍生融操作二叉串樹(shù)的乎操作Pr勇eO騰rd廚er秧Tr窗av跳er銹se灣(T,激vi譯si閉t(元))貝;先序壓遍歷T，對(duì)尊每個(gè)再結(jié)點(diǎn)暈調(diào)用哲函數(shù)vi聚si狂t。In范Or煮de去rT援ra緊ve衣rs慮e(沙T,vs奏it()患);中序雁遍歷T，對(duì)牢每個(gè)抓結(jié)點(diǎn)痛調(diào)用添函數(shù)Vi盡si娘t。Po器st譯Or骨de番rT造ra傾ve給rs英e(反T,場(chǎng)vi督si寨t(女))精;后序也遍歷T，對(duì)垃每個(gè)焦結(jié)點(diǎn)買(mǎi)調(diào)用巖函數(shù)vi衣si恥t。Le罩ve浙lO妥rd飲er按Tr粘av撞er語(yǔ)se氏(T,弦vi勻si融t(厚))侍;層序儀遍歷T，對(duì)涂每個(gè)媽結(jié)點(diǎn)印調(diào)用褲函數(shù)vi仆si唉t。三蚊二叉鞋樹(shù)的督存儲(chǔ)侍結(jié)構(gòu)1順序撞存儲(chǔ)回憶綢性質(zhì)塔⑤，助完全狂二叉諒樹(shù)二叉長(zhǎng)樹(shù)的帳順序凍存儲(chǔ)蓬定義#d歡ef蜘in磁eMa任xT棗re甜eN耀od金eN伶um10勺0ty褲pe倦de商fst測(cè)ru稿ct{Da議ta賤Ty危peda站ta釣[M耕ax補(bǔ)Tr蹲ee艙No賴de公Nu楊m];/*根存插儲(chǔ)在齡下標(biāo)冠為1的數(shù)招組單逃元中徐*/in屋tn;括/*當(dāng)前盡完全稠二叉啄樹(shù)的嗚結(jié)點(diǎn)伶?zhèn)€數(shù)育*/}QB奪Tr骨ee;二叉族樹(shù)是利完全仿二叉澤樹(shù)時(shí)沫，沒(méi)米有問(wèn)才題。已但是流如果丘是非微完全艷二叉讓樹(shù)怎疏么辦航？方法脹：將輪非完趟全二軟叉樹(shù)具以特寄殊值蚊填充饒成完乏全二舉叉樹(shù)記形式映。新的恨問(wèn)題家：若衛(wèi)為完更全二迅叉樹(shù)笑，空衰間利眼用率創(chuàng)高、場(chǎng)尋找除孩子興和雙名親比充較容蕉易。棗若不襯是完孩全二飼叉樹(shù)涂，造搬成空抹間利憑用率封的下芳降。2二叉劉樹(shù)的鎮(zhèn)鏈?zhǔn)酱啻鎯?chǔ)由于梢二叉勝樹(shù)最懶多只匹有兩顯顆子禾樹(shù)，刻因此毛可以賓采用浮二叉刮鏈表遷形式飽存儲(chǔ)歷。Lc勒hi酬ld和Rc底hi牢ld是分殘別指鬧向該麥結(jié)點(diǎn)辛左孩臟子和靜右孩味子的騰指針二叉翁樹(shù)的殺鏈?zhǔn)皆拼鎯?chǔ)傍定義ty脊pe柴de餃fst殘ru壤ctbn頸od吹e{Da黃ta慚Ty匪peda評(píng)ta拾;st犧r(nóng)u棄ctbn技o(jì)d時(shí)e*lc秤hi壯ld,偽*rc帳hi鉤ld;}Bn沒(méi)od懶e，*BT孩re避e;二叉聲樹(shù)的翼鏈?zhǔn)金^存儲(chǔ)恐結(jié)構(gòu)瞇類似欠線性顯表的乒雙向申鏈表賺存在叢兩個(gè)拜指針料，分餅別指旬向其餓左右潑子樹(shù)原，而腦非雙樓向鏈差表的惰前驅(qū)籮和后呼繼。鏈?zhǔn)桨娼Y(jié)構(gòu)徐可以低根據(jù)男二叉班樹(shù)的后結(jié)點(diǎn)銹數(shù)來(lái)逼動(dòng)態(tài)殊分配迅存儲(chǔ)述空間密，解脅決了住順序預(yù)存儲(chǔ)勾結(jié)構(gòu)怪的問(wèn)摔題，坊因此醉常用腐的二哄叉樹(shù)務(wù)采用額二叉錫鏈表雕的形病式比較較多規(guī)。根據(jù)誰(shuí)操作身的不頑同可搜以對(duì)拾二叉剃樹(shù)進(jìn)只行改跪進(jìn)，脫如：次考慮挎求雙湖親（籠前驅(qū)項(xiàng)）操誘作時(shí)較可以祖采用顫什么騎形式仔？遍歷定義貫：按歸照一向定規(guī)激則訪森問(wèn)二滋叉樹(shù)湊的所哄有節(jié)之點(diǎn)一蹲次。根據(jù)圍根結(jié)鍋點(diǎn)和問(wèn)左右莊子樹(shù)貓?jiān)L問(wèn)賢的先賞后不案同，繭有四攻類七近種遍公歷操嫩作。先序湯遍歷敢：TL脆R或者TR駕L中序蘭遍歷博：LT混R或者RT是L后序呀遍歷薯：LR伸T或者RL粗T層次工遍歷繼：從牢上到是下，從左殃到右依次判訪問(wèn)撥結(jié)點(diǎn)6.未3二叉只樹(shù)的不遍歷先序持遍歷喪：ABDGCEFH先序蜘序列傍：AB沒(méi)DG尤CE飄FH中序絮遍歷漫：DGBAECHF中序序列約：DG場(chǎng)BA砌EC椅HF后序砍遍歷主：GDBEHFCA后序序列寫(xiě)：GD宇BE遍HF股CA層次芬遍歷凱：ABCDEFGH層次茶序列揚(yáng)：GD倆BE勤HF每CA1二叉手樹(shù)的由先序劈燕遍歷算法蜓思想煉：判其斷二懼叉樹(shù)報(bào)是否題為空融？若為寬空，冒則結(jié)墨束遍佳歷；達(dá)否則缺先訪任問(wèn)根鳥(niǎo)；再先腰序遍疼歷根濾的左挑子樹(shù)臘；最后構(gòu)先序腹遍歷司根的孔右子繡樹(shù)vo顯idPr正eO詳rd嚴(yán)er(BT導(dǎo)re癥et漫){}if煎(攔t交){低vi掌si潤(rùn)t斯(t波->嬌da廣ta攏);瓦/臣*訪問(wèn)秧結(jié)點(diǎn)考內(nèi)容冤*/Pr捏eO球rd趨er(貫t-廁>lc童hi化ld);歪/*遍歷流左子堪樹(shù)治*/Pr烘eO倍rd叢er(壓t-堤>rc晉hi訓(xùn)ld);召/*遍歷業(yè)右子只樹(shù)笑*/}2二叉桂樹(shù)的隙中序多遍歷算法堆思想哈：判橫斷二倍叉樹(shù)四是否鍛為空葡？若為勇空，肥則結(jié)錦束遍疾歷；否則幅先中此序遍睜歷根懷的左塊子樹(shù)竊；再訪首問(wèn)根妙；最朽后中蔥序遍踐歷根欄的右條子樹(shù)vo筍idIn沖Or著de柴r(BT刊re泥et閣){}if友(臺(tái)t局){In柳Or彈de剛r(瘡t-汽>lc涂hi昏ld);熔/*遍歷膝左子劇樹(shù)滿*/vi妙si抽t調(diào)(t編->寧da姻ta蛛);炸/善*訪問(wèn)絹結(jié)點(diǎn)羊內(nèi)容辟*/In引Or池de薦r(課t-階>rc卵hi殘ld);靠/*遍歷誘右子坐樹(shù)薪*/}3二叉鞠樹(shù)的皆后序吃遍歷算法胸思想宋：判習(xí)斷二轟叉樹(shù)慚是否態(tài)為空根？若為旨空，培則結(jié)蓮束遍緣瑞歷；否則盲先后劣序遍悶歷根也的左傻子樹(shù)觀；再后汁序遍遙歷根前的右宿子樹(shù)登；最暗好訪壞問(wèn)根vo蔑idPo袍st雪Or腿de央r(BT漸re串et特){}if送(講t番){Po擔(dān)st衛(wèi)Or死de蹈r(素t-繩>lc瞎hi該ld);買(mǎi)/*遍歷閑左子螞樹(shù)天*/Po亭st司Or名de割r(外t-暢>rc特hi鋼ld);妹/*遍歷呈右子雪樹(shù)妙*/vi倉(cāng)si答t文(t歷->賭da帳ta籠);假/翻*訪問(wèn)越結(jié)點(diǎn)厲內(nèi)容擦*/}二叉陷樹(shù)的郵先序杏遍歷反的非饅遞歸燦算法理解列遞歸租算法早的過(guò)遠(yuǎn)程ABCDEFGHABDGCEFH二叉論樹(shù)的齡先序傅遍歷籮的非顧遞歸片算法vo沒(méi)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(利用細(xì)棧進(jìn)康行遍休歷)De短st捉ro肚y_祖Se喜qS學(xué)ta談ck響(&羽S);}二叉代樹(shù)的書(shū)先序贊遍歷月的非社遞歸疼算法A:wh拋il材e菠(天p弄||花!Em懷pt達(dá)y_扛Se納qS落ta沫ck(S肅)構(gòu)){if砍(表p熄){Vi揉si圖t分(p告->仁da海ta監(jiān))妻;Pu蔽sh臣_S護(hù)eq奮St盯ac窄k(屋S,幟p弱);障/麗*預(yù)留p指針還在棧陣中哨*/p膠=炭p-姐>lc幣hi徐ld;}el跌se{Po番p_迷Se針qS潛ta飄ck(S,略&p);p瀉=嘴p-意>rc推hi惱ld;}堅(jiān)/*左子綿樹(shù)為截空,進(jìn)右尸子樹(shù)鹿*/}目的術(shù)是什罰么？從左悅子樹(shù)媽返回垃時(shí)能鳴找到淚右子索樹(shù)二叉眠樹(shù)的歸中序月遍歷高的非倚遞歸足算法理解罷遞歸架算法愧的過(guò)警程ABCDEFGHDGBAECHF二叉么樹(shù)的炭中序性遍歷饒的非瓦遞歸泳算法vo載idIn甜Or核de鍵r(BT孕re山et){PS誕eq竭St撇ac功kS;BT弊re稿e(cuò)p盆=化t;S=In齡it挽_S犯eq段St詞ac服k(擴(kuò));何/皺*棧初討始化蒙*/A(利用根棧進(jìn)僻行遍酒歷)De縫st敲ro且y_匪Se偉qS棵ta準(zhǔn)ck秤(&臟S);}二叉雷樹(shù)的壤中序圣遍歷閑的非鳥(niǎo)遞歸頃算法A:wh爸il距e委(爛p輪||司!Em丈pt會(huì)y_音Se貸qS匪ta筐ck(S艘)喬){if振(儲(chǔ)p朵){Pu碗sh助_S綿eq素St瘋ac悠k(葛S,爺p階);帆/同*預(yù)留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業(yè)ld;}縱/*左子斬樹(shù)為絡(luò)空,進(jìn)右揉子樹(shù)挽*/}目的暑是什筍么？從左禽子樹(shù)蓬返回映時(shí)訪永問(wèn)根個(gè)，并輕且通型過(guò)根雨結(jié)點(diǎn)駐能找早到右圓子樹(shù)二叉廈樹(shù)的庸后序督遍歷陷的非究遞歸判算法方法趁一：逃利用園先序種遍歷糠非遞痰歸算邊法(按先旨根結(jié)嶼點(diǎn)、井再右子集樹(shù)、再左子責(zé)樹(shù)的順惕序)將找磁到的追要訪們問(wèn)的啟結(jié)點(diǎn)岔壓棧遍歷垮結(jié)束沈?qū)０l(fā)中元賊素出全棧訪厭問(wèn)vo倒idPr皮eO乳rd蘋(píng)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環(huán)qS晨ta丸ck(S學(xué))傻){if亡(注p圈){Pu涉sh私_S霧eq作St絕ac厚k(潛S1削,破p)匹;//保存敢到結(jié)恰果棧榮中Pu迅sh蟲(chóng)_S朱eq烏St遵ac兔k(孟S2另,彎p)去;許/車(chē)/預(yù)留p指針鑄在棧工中p谷=秒p-震>rc滴hi破ld;//先右鐮后左}el節(jié)se{Po際p_緒Se帳qS偶ta臺(tái)ck(S母2,銳&p讀)迎;p徒=笛p-今>lc尾hi勵(lì)ld;}}wh雪il伐e蹈(憑!Em偏pt略y_盲Se縫qS枝ta氏ck(S陽(yáng)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旬a(chǎn)c鎮(zhèn)k(井&S蘇2)荷;}方法己二：峰二叉廉樹(shù)的雀后序震遍歷最的非鹿遞歸歐算法理解嘴遞歸尤算法是的過(guò)困程ABCDEFGHGDBEHFCA二叉往樹(shù)的鈴后序膜遍歷昂的非欄遞歸蹈算法ty適pe泳de塵fst常ru考ct{Bn獨(dú)od面e*n督od減e;in熄tfl房誠(chéng)ag犧;}SD觸at對(duì)aT崇yp雨e;vo濁idIn躺Or本de剝r(jià)(BT唇re嘩et){PS夏eq顧St筑ac校kS;BT謊re堡ep贏=拐t;S=In殃it懂_S悔eq潮St濾ac曲k(干);若/湊*棧初罵始化靠*/A(利用積棧進(jìn)丘行遍車(chē)歷)De回st或ro睛y_顆Se礦qS火ta株ck叼(&挨S);}二叉毯樹(shù)的幼后序濕遍歷護(hù)的非怕遞歸淋算法A:wh紐奉il層e瘡(裝p宗||蹦!Em強(qiáng)pt項(xiàng)y_牲Se虹qS繩ta皇ck(S織)容){響if協(xié)(迎p覽){Sq押.f茅la臺(tái)g=0讓;Sq淘.n梅od錯(cuò)e=p徒;Pu工sh悅_S族e(cuò)q望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==礎(chǔ)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昏)紀(jì);p來(lái)=芒NU凈LL懷;}}目的矮是什杠么？目的虹是什吹么？目的圍是什上么？從左歲子樹(shù)嘩返回藍(lán)時(shí)通焦過(guò)根餃結(jié)點(diǎn)震能找非到右瀉子樹(shù)從右舌子樹(shù)普返回腸時(shí)能赴訪問(wèn)惱根結(jié)研點(diǎn)從右件子樹(shù)獄返回認(rèn)訪問(wèn)場(chǎng)根后,結(jié)束捉了這緞?lì)w子飛樹(shù)訪暑問(wèn)應(yīng)貢返回棄該子瓣樹(shù)的泳雙親,應(yīng)彈魂棧，幟設(shè)為nu奶ll使下律次循娛環(huán)能辛彈棧4二叉摟樹(shù)的魄層次反遍歷填算法ABCDEFGH隊(duì)列知：ABCDEFGHvo枝idLe歪ve揉l(xiāng)O窮rd共er王(B規(guī)Tr轉(zhuǎn)eet){Ps挪eq嶄Qu自eu遲eQ;BT窗re劃ep;if糠(喇t){送Q=In蜜it濱_s賭eq鄭Qu偉eu果e()順;緣瑞//設(shè)置旦一空臺(tái)隊(duì)列In評(píng)_s娛eq霧Qu牢eu金e(語(yǔ)Q,遵t);稠//根結(jié)媽點(diǎn)入評(píng)隊(duì)wh涌il付e謀(!Em費(fèi)pt螺y_謎se冶qQ舌ue旅ue(Q素)){金/惹/當(dāng)隊(duì)辮非空榮時(shí)重曉復(fù)執(zhí)如行下些列操制作Ou啟t_邀se牌qQ兄ue賄ue欠(Q辨,&叫p);Vi尺si周t(給p->臺(tái)da駁ta草);眠//出隊(duì)竿訪問(wèn)if牲(勿p-載>Lc思hi翻ld)In嘴_s碰eq姑Qu慰eu目e(肌Q,輔p->Lc匯hi聯(lián)ld);少//左孩千子入別隊(duì)if前(碑p-忌>Rc纖hi消ld)In細(xì)_s悶eq江Qu容eu共e(右Q,腹p->Rc薪hi敗ld);將/殼/右孩世子入應(yīng)隊(duì)}De騎st從ro商y_聽(tīng)Se毯qQ挪ue鉆ue波(&眉Q);}}5遍歷旨算法汗應(yīng)用膛舉例二叉哄樹(shù)是席遞歸魄定義縱，可災(zāi)以寫(xiě)毯出它所的遞程歸遍抵歷算帳法，毅同時(shí)捉借助恰遍歷那算法劣思想癢可以慨實(shí)現(xiàn)懂其它鎮(zhèn)算法善，如換：創(chuàng)建掀二叉始樹(shù)、袋銷毀跨二叉趣樹(shù)等傲；計(jì)算毒二叉繡樹(shù)的告高度盈，計(jì)塵算結(jié)琴點(diǎn)數(shù)密，二緣瑞叉樹(shù)袖的查諸找等辨操作二叉音樹(shù)的沉創(chuàng)建鑰算法在輸野入先增序序零列時(shí)戴，需慎要在旦空節(jié)者點(diǎn)填替補(bǔ)一司個(gè)特潛殊的香字符休，比惠如，毯‘#’。如檔果讀眾入的艱字符聾是‘#’，則丑在相古應(yīng)的竿位置睬上構(gòu)碰造一羞棵空折二叉蔑樹(shù)；肝否則豬，創(chuàng)云建一授個(gè)新宵結(jié)點(diǎn)憲。采鋤用先另序遍庭歷遞是歸算鼓法為纏基礎(chǔ)膛，二計(jì)叉樹(shù)呈中結(jié)判點(diǎn)之烏間的鄙指針執(zhí)連接節(jié)是通抬過(guò)指擇針參騰數(shù)在醋遞歸婆調(diào)用候返回炮時(shí)完桂成。二叉民樹(shù)的劑創(chuàng)建墾算法AB眼D#般G#蹦##奴CE咐##漿FH蠢##挪#ABD#G###CE##FH###BDGCEFHA二叉柄樹(shù)的汪創(chuàng)建睜算法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爹;恩/*讀入例＃時(shí)猶，將茂相應(yīng)票結(jié)點(diǎn)雁指針燭置空觀*/el鼻se{裝t=皇(Bn促od竭e*)ma注ll透oc哈(B梢no芝de);宮/*生成丑結(jié)點(diǎn)盾空間熱*/t-末>d柔at竊a=ch;t-收>lc渡hi啄ld=Cr倦ea圾te郵Bi轉(zhuǎn)nT屑re羞e()扛;t-駝>rc飲hi呆ld=Cr址ea蝕te卡Bi獄nT追re粥e()淋;re永tu譯rn矩t鳳;}}二叉腰樹(shù)的慌創(chuàng)建者算法vo剪idCr瞇ea幫te洪Bi孩Tr疾ee(BT寸re蒼e*t難){葉/*以加孔入空予結(jié)點(diǎn)杯的先邀序序謊列輸測(cè)入，等構(gòu)造禁二叉蟻鏈表嶺*/ch盲arch;ch=ge量tc撒ha斥r()秒;if渾(ch==鎮(zhèn)‘?！?*t洞=N泥UL駝L;枝/顛*讀入皺＃時(shí)紅，將你相應(yīng)些結(jié)點(diǎn)凡指針撥置空條*/el剩se{邁*t作=(Bi班Tr漲ee)ma哀ll茅oc縮慧(B竭no幕de);奸/*生成揚(yáng)結(jié)點(diǎn)乞空間虜*/(*繩t)憲->熔da站ta過(guò)=ch;Cr利ea偵te框Bi本Tr唱ee(&脆((濫*t今)-福>lc偵hi棚ld))碎;Cr茫ea畜te薯Bi仙Tr疏ee(&兼((辜*t紙)-工>rc勤hi互ld))偷;}}二叉洲樹(shù)的汪銷毀康算法算法漸思想深：銷毀膨二叉伯樹(shù)可草以根桂據(jù)先劍序遍概歷類芝似，潛先若怠樹(shù)為蓋空樹(shù)趟，不守用銷防毀直序接返御回；靜若為銷非空典樹(shù)，行則先終銷毀麻左子臟樹(shù)，徒再銷豪毀右敬子樹(shù)胃，最傷后銷鐘毀根德節(jié)點(diǎn)眉。vo侵idDe氧st決ro語(yǔ)yB雜it魄Tr菊ee(BT游re歸e*t艘){盲/*銷毀t表示桐的二拉叉樹(shù)笨*/if容(邪(寧*t攏)料){De辱st史ro枕yB違iT閘re桂e(&風(fēng)((超*t秤)-橡>lc設(shè)hi遲ld))販;De扮st映ro背yB河iT叨re泡e(&鵝((耕*t淺)-畜>rc濃hi塔ld))歸;fr方ee狂(*蒸t)宅;*t梳=N匪UL肅L;}}計(jì)算進(jìn)二叉探樹(shù)的透結(jié)點(diǎn)惡個(gè)數(shù)vo吳idCo災(zāi)un聲t_柱Tr剪ee寇(B說(shuō)Tr垃eet){幻玉i諒f兄(t剩){Co農(nóng)un涼t_奧Tr身ee披(t->lc剛hi蘇ld)；//統(tǒng)計(jì)欺左子果樹(shù)結(jié)撓點(diǎn)個(gè)單數(shù)co柔un咳t+緞+;//躺co沸un縱t為全社局變技量Co沫un涼t_恒Tr鑰ee丟(t->rc刮hi承l(wèi)d)仔;//統(tǒng)計(jì)步左子湖樹(shù)結(jié)口點(diǎn)個(gè)趴數(shù)}}in拼tCo吉un集t_鬼Tr冊(cè)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)余;}求二屈叉樹(shù)純每層洋結(jié)點(diǎn)懇個(gè)數(shù)算法姥思想籠：設(shè)置堂一個(gè)答數(shù)組襲，數(shù)秩組的播下標(biāo)涂表示渾樹(shù)的約層數(shù)杜，該型下標(biāo)稍元素孔的值艦記錄殖該層宏元素蘇的個(gè)院數(shù)；陪通過(guò)擱樹(shù)的夢(mèng)遍歷火算法婚來(lái)得需到最北終數(shù)命組元罷素的毯值。求二浸叉樹(shù)腹每層酬結(jié)點(diǎn)暴個(gè)數(shù)in通tnu克m[蜂20販]；Vo資idLe祥vc鎮(zhèn)ou棉n(BT篩re誰(shuí)et,in勁tL,服in夏tnu匪m[昏]華)//話L是當(dāng)童前結(jié)邁點(diǎn)的弦層次鋤，初徹值1，nu勤m數(shù)組依元素婦初始驕化0{if他(盒t閣){nu倡m[暗L]+貓+;Le汁vc擊ou罵n(t赤->lc林hi續(xù)ld,丈L+振1,奴nu澡m)史;Le異vc答ou纖n(t奮->rc伐hi侄ld,在L+旱1,被nu懸m)系;}}調(diào)用磚前，nu膀m數(shù)組亞元素雨全部青清0初始漏調(diào)用野：Le克vc預(yù)ou塑n(t猴,鋪1,父nu制m)求二傍叉樹(shù)算的高秋度定義縱：樹(shù)紡中節(jié)固點(diǎn)深?yuàn)Z度的賓最大灑值結(jié)舉點(diǎn)個(gè)向數(shù)in程tHe咸ig訊ht糞(BT俘re煉et劣){in晨th1鈔,h制2;if啄(其t=籃=N寶UL叼L)嫁r(nóng)e燭tu對(duì)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探);}求二括叉樹(shù)蜻的復(fù)得制BT化re壩e*Co蓄py性Tr攻ee(BT犯re扁et){BT財(cái)re獎(jiǎng)es;if乘(鈔t=典=壁NU戰(zhàn)LL霉)re俊tu莫rn強(qiáng)(聲NU塌LL爽);s=等(Bi蹈Tr雄ee)ma仿ll梅oc(Bn總od妹e);咐/返/復(fù)制迫根結(jié)理點(diǎn)s-叼>d第at炭a=蚊t-鉤>d翼at就a;s-武>lc麻hi買(mǎi)ld=Co豪py鋼Tr所ee懶(t->lc怖hi弄ld);主//復(fù)制金左子厭樹(shù)s-脂>rc轎hi蘋(píng)ld=Co驗(yàn)py侍Tr禁ee諷(t->rc帆hi其ld);規(guī)/墻/復(fù)制鍛右子徑樹(shù)re脈tu卡rn科s就;}交換鞋二叉回樹(shù)的誓左右偶子樹(shù)vo絲式idch侄an辯ge舅_l谷ef營(yíng)t_咱ri繪gh波t(跨BT萄re綠eBT郊){銀i仗f統(tǒng)(B今T){ch地an葬ge梨_l炮ef灘t_勒ri己gh存t(騰BT->lc芽hi脂ld);ch炒an堡ge倦_l歐ef肝t_牙ri蘋(píng)gh陜t(寇BT->rc粥hi杏ld);BT臉->lc抱hi清ld<-挨>B音T-乏>rc系hi除ld;}}6.幼4線索偉二叉綱樹(shù)研究括二叉術(shù)樹(shù)的繞遍歷案發(fā)現(xiàn)須：通冠過(guò)指究定次捏序的愧遍歷妥發(fā)現(xiàn)攻求結(jié)球點(diǎn)的相前驅(qū)稻或后禁繼，扁費(fèi)時(shí)論間，峽效率俗低。如何幣解決驚？方法1：增傍設(shè)前災(zāi)驅(qū)和狼后繼篩指針——在每閃個(gè)結(jié)戴點(diǎn)中雙增設(shè)覽兩個(gè)眠指針慨，分卻別指圣示該厲結(jié)點(diǎn)報(bào)在指倚定次拿序下亡的前秘驅(qū)或叛后繼霞。從捐而避顯免使兩用遞前歸減窩少了似函數(shù)俱調(diào)用詞的時(shí)蜻間，奪但增騙加了傾空間掀開(kāi)銷花。方法2:二叉樹(shù)中聯(lián)有很枝多閑崗置的罵指針燥，能請(qǐng)否利合用它漫們?yōu)橘€訪問(wèn)勞二叉喉樹(shù)提繳供便病利?利用腔二叉廁鏈表誕中的費(fèi)空指唐針域橡（n個(gè)結(jié)嚷點(diǎn)的賣(mài)二叉咬樹(shù)有n+寬1個(gè)空梨指針華域）休，將跟二叉神鏈表分中的奔空的衫指針劍域改跡為指括向其該前驅(qū)串和后妥繼：體空的幸左孩壟子指舊針指甘向其霸前驅(qū)準(zhǔn)，空焦的右姜孩子脖指針越指向翠其后們繼伏。ABDGCEFH如何努區(qū)分察誰(shuí)是簡(jiǎn)后繼竄結(jié)點(diǎn)撥，誰(shuí)懶是右花孩子棄結(jié)點(diǎn)貍？誰(shuí)是個(gè)前驅(qū)迅結(jié)點(diǎn)品，誰(shuí)加是左霧孩子旨結(jié)點(diǎn)殊？設(shè)立扶標(biāo)志練位：lt年ag=0：lc筐hi督ld指示司該結(jié)滔點(diǎn)的制左孩字子lt惜ag=1：lc里hi認(rèn)ld指針替該結(jié)想點(diǎn)的配前驅(qū)意。rt汽ag=0：rc把hi爐ld指示幟該結(jié)癢點(diǎn)的印右孩蛙子rt抵ag=1：rc喉hi這ld指針散該結(jié)錫點(diǎn)的汗后繼童。中序抖遍歷饑下的擁線索兵化二傳叉樹(shù)修形式球：ABDGCEFH線索錫二叉辮樹(shù)的估數(shù)據(jù)遵結(jié)構(gòu)轉(zhuǎn)定義噸：ty嚷pe講de抹fst煤ru炸ctTh劃re侄ad侍no不de{in攜tlt復(fù)ag；st階ru撒ctTh險(xiǎn)re貫ad泰no涌de*lc唇hi錘ld；Da靜ta災(zāi)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；中序續(xù)二叉狐樹(shù)的壇線索果化vo騎idIn倚Th弊re綿ad(Th捆re股ad榜Bi失tT縫re屈ero地ot鹿,Th色re魂ad恩Bi冰tT推re拉epr億e){罪/*遞歸勻中序效線索售化二僅叉樹(shù)早；加函浴數(shù)調(diào)諷用前pr砌e為空楊*/if允(r浮oo望t){In潤(rùn)Th售re六ad轎(r遠(yuǎn)oo辣t->lc賣(mài)hi缸ld遍,p命re);畫(huà)/*中序熟線索盲化左躬子樹(shù)景*/A：當(dāng)叨前結(jié)脾點(diǎn)線份索化In潮Th穿re稻ad(r持oo側(cè)t-張>rc棟hi幫ld救,p晚re);些/*中序稼線索膽化右竊子樹(shù)姓*/}/撞/en嗽di樓f}中序史二叉濫樹(shù)的惹線索雙化A：當(dāng)川前結(jié)遮點(diǎn)線那索化if沈(漠ro段ot裹->lc側(cè)hi經(jīng)ld==弓nu傻ll伯)國(guó)//建立情前驅(qū)饒線索{橫r掩oo著t-食>lt犁ag=1蘆;ro陽(yáng)ot辦->lc苦hi挎ld=p下re餃;請(qǐng)//左孩亡子域臣指向跟前驅(qū)}if憲(屬ro解ot她->rc婦hi褲ld==濕nu魔ll弊)ro紡ot嚴(yán)->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構(gòu)re->rc兩hi偵ld==朱nu贊ll俯){貞pr萍e-經(jīng)>rt曬ag=1新;pr懸e-荷>rc呆hi相l(xiāng)d=r愈oo枝t;}//為下飄次后鹿繼線渴索做裂準(zhǔn)備//建立賊后繼柳線索中序冤二叉判樹(shù)的援線索踐化的馬非遞網(wǎng)歸算爬法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獨(dú)eq默St辜ac遇k(凈);澤/洞*棧初桃始化拘*/A(利用野棧進(jìn)至行中熊序線鮮索化)De耽st像ro哨yS揉eq桌St獵ac鑄k(某&S);}二叉累樹(shù)的此中序誤遍歷遇的非今遞歸他算法A:wh皇il蠅e(釀p|俗|!俊Em湖pt宅y_僅Se淺qS扮ta歸ck(些S)蔽){辣if梅(日p){Pu娃sh溉_S樸eq稍St級(jí)ac礦k(駕S,膠p彎);剃p喝=課p效->lc栽hi殼ld;費(fèi)}el傘se{po賀p_鑄Se觀qS包ta競(jìng)ck(S,寶&p);if色(p賢re!=澤NU扯LL疾){if詠(!獎(jiǎng)pr綢e->rc秀hi航ld){上pr韻e-薦>rc蠶hi拒ld=p猜;更pr魂e-投>rt墓ag=1煉;儲(chǔ)}if桿(!昂p->lc督hi舍ld){援p-映>rl浸ch格il別d=p沒(méi)re酒;里p-拘>lt著ag=1環(huán);倒}pr被e=僑p;p工=兩p-匆>rc務(wù)hi于ld;}}/參/e士nd重w凱hi饒le中序培線索轎化的姐二叉磁樹(shù)的閉前驅(qū)Th本re缺ad隆no墓de*In電Pr玩eN妹od焰e(Th籮re廊ad途no緞de*驗(yàn)p){遵//在中燃序線貪索二燦叉樹(shù)蒙上尋討找結(jié)貨點(diǎn)p的中召序前毀驅(qū)結(jié)榴點(diǎn)伴，假沸設(shè)p非空Th林re龜ad廢no熊de*否pr流e;pr筆e主=p拖->lc睬hi羊ld;if女(她p-貫>lt蜻ag==加0){磨wh獻(xiàn)il協(xié)e癢(向pr道e勸&&森p赤re糕-升>rt氣ag==竟0)pr蘭e迅=pr趙e->rc夜hi矮ld;}re汽tu疼rn縱(盈pr箱e)鋒;}中序扒線索菜化的柜二叉紙樹(shù)的承后繼Th軍re現(xiàn)ad擁no軋de*In飽Po曉st詞No寇de(Th淹re倚ad凈no啄de*械p){蜜//在中斯序線名索二抵叉樹(shù)互上尋年找結(jié)容點(diǎn)p的中癢序前顛驅(qū)結(jié)仗點(diǎn)馬，假睜設(shè)p非空Th券re挎ad叔no蜜de*坊po奧st噴;po疊st荷=枕p-限>rc梁hi行l(wèi)d;if做(市p-熊>rt沉ag==墻0){引wh第il優(yōu)e愚(錢(qián)po把st編&奪&滔po織st解-胞>lt役ag==趨0)po徑st曉=po漏st->lc柿hi肯ld;}re恢tu暢rn城(晨po員st宣);}中序愉線索貸化的濱二叉彩樹(shù)的叔遍歷vo劈燕idIn百Or姜de繡rT示h(Th單re拉ad培no漏de*鎮(zhèn)ro輸ot疫)/*對(duì)中伐序線室索二灑叉樹(shù)吐進(jìn)行農(nóng)中序性遍歷芒*/{Th壤re革ad詢no臥de*將p;if旋(旱ro堆ot掩){倍p=中ro阿ot撞;wh暈il灰e隔(p遺->lt搶ag==畝0)仁p=廣p-萌>lc傾hi碗ld;榜/*找最辰左下花的結(jié)牧點(diǎn)*/wh青il榨e斗(p省){vi瘋si金te見(jiàn)(p->估da釀ta押);危/煎*訪問(wèn)瞎當(dāng)前角結(jié)點(diǎn)呆*/p=In狂Po崖st概No比de(p貢);細(xì)/*尋找謎結(jié)點(diǎn)p的后幸繼結(jié)壇點(diǎn)齊*/}}}中序皆線索鈴化的耕二叉候樹(shù)的必查找善指定眠的xTh舞re京ad救no恩de*In拖Se穴ar喊ch拘Th(Th怠re活ad鬼no醬de*梳ro啦ot，in制tDa皇ta吹Ty吧pex)/*對(duì)中扁序線潮索二泰叉樹(shù)辭進(jìn)行桑搜索*/{Th忌re顏ad色no巴de*燒p;if頓(馳ro剃ot拼){抱p=頑ro邁ot訊;wh砌il芝e扣(p思->lt郵ag==死0)稍p=龍p-壺>lc睛hi若ld;牢/*找最秩左下涌的結(jié)栽點(diǎn)*/wh桶il善e青(p哥&明&p-松>d遇at帽a傻!=旦x)p=In哲Po仆st奸No炒de(p仙);銷/*尋找判結(jié)點(diǎn)p的后煙繼結(jié)蓋點(diǎn)俊*/}re斷tu貌rn勒p沖;}6.仍5樹(shù)和椅森林一、陳樹(shù)的爸存儲(chǔ)貓結(jié)構(gòu)1、雙晉親表疼示法2、孩領(lǐng)子表拋示法3、孩商子兄缸弟表目示法每個(gè)從節(jié)點(diǎn)易中存拿儲(chǔ)自穿己的志第敵一個(gè)臟孩子潮和兄商弟的清地址醫(yī)（連隙接所摩有的盆兄弟狡），泰鏈接歸方式族存儲(chǔ)孩子失兄弟熊表示士法數(shù)葵據(jù)結(jié)拼構(gòu)定爸義：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;二、大樹(shù)、唇森林芒和二列叉樹(shù)拴的轉(zhuǎn)貝換1、樹(shù)域轉(zhuǎn)換普為二事叉樹(shù)樹(shù)中雄所有詳相鄰各兄弟濃之間亡加一戒條連廚線。對(duì)樹(shù)吼中的腰每個(gè)爽結(jié)點(diǎn)角，只塞保留考它與駱第一憐個(gè)孩圈子結(jié)趙點(diǎn)之業(yè)間的歲連線佩，刪呀去它僵與其薦它孩次子結(jié)解點(diǎn)之諸間的跳連線嚷。以樹(shù)樹(shù)的根緞結(jié)點(diǎn)黎為軸競(jìng)心，靜將整繡棵樹(shù)枕順時(shí)教針轉(zhuǎn)始動(dòng)一扎定的衰角度雹，使燒之結(jié)掩構(gòu)層港次分孫明樹(shù)與吧二叉標(biāo)樹(shù)的夫轉(zhuǎn)換余圖2、森棍林轉(zhuǎn)搏換為供二叉院樹(shù)由于礦樹(shù)轉(zhuǎn)壟換成辜二叉繡樹(shù)形爐式后素根的酸兄弟?chē)?yán)指針眉總為魂空，所以站可以腹將森皺林中狀的每富棵樹(shù)陡的根醬互看溜成是顛兄弟斧，將沈第二棵樹(shù)角接到賺第一靈棵的纏兄弟鎮(zhèn)上，炮依次獵類推脆，可振以將n棵樹(shù)透鏈成兄婆弟鏈鴉。方法諷：將森歲林中逝的每溫棵樹(shù)充轉(zhuǎn)換潔成二槐叉樹(shù)將轉(zhuǎn)栗換好鋪的每羅棵二跪叉樹(shù)籮通過(guò)粥根節(jié)嘴點(diǎn)的雁右分雨支相筍連二叉慶樹(shù)轉(zhuǎn)祖換為陪樹(shù)或沖森林方法禾：若某挨結(jié)點(diǎn)喇是其爛雙親傷的左川孩子匠，則似把該丙結(jié)點(diǎn)淡的右專孩子攀、右撇孩子挑的右旨孩子……都與辣該結(jié)抱點(diǎn)的暫雙親蠅結(jié)點(diǎn)連用線妥連起叢來(lái)。刪去毀原二感叉樹(shù)升中所鉤有的緊雙親泄結(jié)點(diǎn)疾與右床孩子揉結(jié)點(diǎn)狐的連筐線。整理偵所得瘋到的嫁樹(shù)或?yàn)┥殖?，使媽之結(jié)葡構(gòu)層段次分萄明。三、嘆樹(shù)、纏森林依的遍鞋歷1、樹(shù)群的遍棗歷樹(shù)的后根棄遍歷飛：（1）按巨照從吐左到聽(tīng)右的愈順序傻后根柜遍歷師根結(jié)染點(diǎn)的兆每一瓦棵子肚樹(shù)。（2）訪俘問(wèn)根沃結(jié)點(diǎn)辰；EF母BC凳GD旗A樹(shù)的棒先根鴨遍歷集：（1）訪著問(wèn)根獎(jiǎng)結(jié)點(diǎn)罪；（2）按蜂照從闊左到四右的滲順序喘先根投遍歷鬼根結(jié)渾點(diǎn)的毀每一威棵子見(jiàn)樹(shù)。AB展EF刊CD宴G看成沒(méi)二叉咽樹(shù)后量先序駛遍歷:AB渣EF財(cái)CD賊G看成石二叉段樹(shù)后敬中序響遍歷EF腔BC笛GD叔AEBACDGF得出胞什么狐結(jié)論阻？樹(shù)的殿先根蛛遍歷鋪與其冠轉(zhuǎn)換柱的相回應(yīng)二吳叉樹(shù)壘的先樣序遍蹈歷的冠結(jié)果銅相同陷；樹(shù)廟的后志根遍世歷與滾其轉(zhuǎn)籃換的怠相應(yīng)偷二叉暫樹(shù)的邁中序筑遍歷乳的結(jié)責(zé)果相課同2、森刊林的組遍歷前(先)序遍該歷：膝若森吵林非坦空（1）訪鍋問(wèn)森阻林中乏第一椒棵樹(shù)競(jìng)的根宰結(jié)點(diǎn)探；（2）前課序遍責(zé)歷第飄一棵娛樹(shù)的疾根結(jié)當(dāng)點(diǎn)的掉子樹(shù)眼森林容；（3）前貴序遍嶄歷去捏掉第腳一棵裁樹(shù)后賓的子物森林兄。中序植遍歷波：若邀森林貍非空（1）中芽序遍普歷第旬一棵坐樹(shù)的塑根結(jié)符點(diǎn)的光子樹(shù)燥森林別；（2）訪賄問(wèn)森茂林中籮第一灣棵樹(shù)吩的根用結(jié)點(diǎn)允；（3）中米序遍儀歷去衣掉第炸一棵掩樹(shù)后炎的子志森林鞠。后序許遍歷悄：若捎森林率非空（1）后辰序遍惜歷第棋一棵險(xiǎn)樹(shù)的闖根結(jié)夫點(diǎn)的賠子樹(shù)牲森林渠；（2）后供序遍銀歷去陰掉第洋一棵景樹(shù)后躲的子見(jiàn)森林姻；（3）訪存問(wèn)森釘林中駱第一扭棵樹(shù)服的根宴結(jié)點(diǎn)亂。廣度攝優(yōu)先烏搜索從第欠一層走開(kāi)始捎，自忽頂向償下、智同層帖自左權(quán)向右棗，依后次訪問(wèn)具森林校中各修棵樹(shù)憶的結(jié)凳點(diǎn)，奴不要銅求一占棵樹(shù)根一棵駝樹(shù)地徹解決。6.乓6駱H勞uf壺fm涌an樹(shù)問(wèn)題嫩的提沸出：賢在通喪信系蠢統(tǒng)中吐，要謀發(fā)送暢由A，B，C，D四個(gè)炎字符副組成年的信稼息，A出現(xiàn)捕的概率為0.型5，B出現(xiàn)掉的概率為0.凈25，C出現(xiàn)遲的概率為0.腹1，D出現(xiàn)寸的概率為0.豪15。如選何對(duì)A、B、C、D四個(gè)繞字符列進(jìn)行汪編碼出，能廚使總軌的編本碼長(zhǎng)剪度最伏短？改進(jìn)擱編碼戲：采長(zhǎng)用不說(shuō)等長(zhǎng)崗的編壯碼方肢法：前綴霞編碼劫：設(shè)束計(jì)不酷等長(zhǎng)斗的編瓜碼，景且任第一字畝符的設(shè)編碼獵都不膠是其涌他字辱符編長(zhǎng)碼的服前綴結(jié)論勿：不庭等長(zhǎng)架的編侵碼可繡以較辦少數(shù)佳據(jù)量堡，起輪到壓棚縮編雅碼的屈目的渾。Hu斜ff路ma勤n樹(shù)的戰(zhàn)相關(guān)左概念驚：路徑屢：從樹(shù)校中一仍個(gè)結(jié)拳點(diǎn)到唇另一擔(dān)個(gè)結(jié)銀點(diǎn)之尖間的賠分支榜構(gòu)成嗓兩個(gè)公結(jié)點(diǎn)質(zhì)之間袍的路譽(yù)徑。路徑厚長(zhǎng)度浴：路徑廊上的栗分支逼數(shù)目賺。樹(shù)的鵲路徑倘長(zhǎng)度潮：根結(jié)技點(diǎn)到愚每個(gè)暢結(jié)點(diǎn)吊的路腐徑長(zhǎng)陪度之崗和。樹(shù)的她帶權(quán)杠路徑螞長(zhǎng)度長(zhǎng)：樹(shù)中筑所有源葉子取結(jié)點(diǎn)溉的帶甲權(quán)路篩徑長(zhǎng)尊度之壇和。記作:WP缺L＝∑wili(i晉=1中,…博,m更)其中框，wi是第i個(gè)葉頸子結(jié)吊點(diǎn)的才權(quán)值描，li為從忘根到億第i個(gè)葉燒子結(jié)暢點(diǎn)的干路徑匆長(zhǎng)度字，m為樹(shù)售的葉屑子結(jié)事點(diǎn)的船個(gè)數(shù)Hu留ff委ma毫n樹(shù)的已定義畝：最優(yōu)弓二叉非樹(shù)：設(shè)有m個(gè)權(quán)爬值{w1,w2,…繡,wm}，構(gòu)與造一鑄棵有m個(gè)葉購(gòu)子結(jié)斧點(diǎn)的注二叉占樹(shù)，州第i個(gè)葉大子結(jié)享點(diǎn)的抄權(quán)值蜘為wi，則士帶權(quán)寫(xiě)路徑裹長(zhǎng)度WP蟲(chóng)L最小除的二或叉樹(shù)熟被稱另作最齡優(yōu)二蒼叉樹(shù),這種半最優(yōu)芹二叉碌樹(shù)也榆稱之茅為哈夫暮曼樹(shù)Hu勵(lì)ff著ma抓n樹(shù)的末例子巴：wp礎(chǔ)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務(wù)=7勸0Hu圍ff到ma籌n樹(shù)的圾構(gòu)造鑒：(1矩)根據(jù)吃給定動(dòng)的n個(gè)權(quán)訊值{w雷1,肢w2途,…，wn}，構(gòu)普成m棵二尊叉樹(shù)丈的集芝合T=用{T茫1,墾T2當(dāng),…木,Tn}，其厭中每隔個(gè)Ti只有讀一個(gè)血帶權(quán)膨?yàn)閣i的根善結(jié)點(diǎn)完，其悶左右疤子樹(shù)觸均空禿。(2折)從T中選是兩棵泳根結(jié)鑄點(diǎn)的希權(quán)值雖最小午的二庭叉樹(shù),不妨脅設(shè)為T(mén)i跪′,爺Tj′并作螞為左歪右子骨樹(shù)構(gòu)排成一冷棵新濱的二休叉樹(shù)Tk’，并燭且置瓶新二優(yōu)叉樹(shù)治的根暫值為纏其左憶右子吃樹(shù)的確根結(jié)緊點(diǎn)的悄權(quán)值肚之和嫂。(3獨(dú))將新兵二叉亮樹(shù)Tk’并入T中,同時(shí)尿從T中刪逼除Ti頁(yè)′,家Tj′。(4訊)重復(fù)(2嗽)、(3嘩)，直寧到T中只驅(qū)有一更棵樹(shù)精為止福。這論棵樹(shù)皇便是頸哈夫滔曼樹(shù)球。假設(shè)孩有一悄組權(quán)條值{5酬,2失9,奔7,虧8,振14副,2挎3,典3,詞11金}，下沾面我紹們將互利用挺這組驕權(quán)值撿演示罰構(gòu)造響哈夫要曼樹(shù)店的過(guò)雖程。52978142331181519294258100帶權(quán)哨路徑匆長(zhǎng)度惕為：WP踢L=(2怎3+勢(shì)29奮)*塘2+招(1燃1+閘14徐)*輪3+(尊3+歲5+弊7+呼8)循*4價(jià)=2讀71帶權(quán)般路徑僻長(zhǎng)度容為：WP撈L=10擱0+尊42嗓+5躁8+護(hù)19斤+2稱9+冠8+1資5=把27斤1Hu簡(jiǎn)ff及ma新n樹(shù)的荷特點(diǎn)焦：特點(diǎn)1：若乓一棵今二叉習(xí)樹(shù)是陳哈夫虜曼樹(shù)告，則悉該二瞎叉樹(shù)流不存爬在度盼為1的結(jié)節(jié)點(diǎn)。特點(diǎn)2：若敵給定慈權(quán)值黨的葉井子結(jié)嘩點(diǎn)個(gè)昨數(shù)為n，則紐奉所構(gòu)矮造的視哈夫浙曼樹(shù)賠中的膠結(jié)點(diǎn)丙數(shù)是2n律-1。特點(diǎn)3：任耕一棵孤哈夫棋曼樹(shù)壘的帶耀權(quán)路文徑長(zhǎng)奶度等漲于所各有分講支結(jié)秩點(diǎn)值盾的累包加和錦。哈夫乒曼編賊碼前綴燦編碼杏方式侍，能但實(shí)現(xiàn)弟一組濕指定望出現(xiàn)究頻率醬字符追編碼界長(zhǎng)度佳之和惹最小A:抵0T:搜10C:僅11芝0S:太11剃1#d寸ef爺in制e厭N顏2復(fù)0宅/居*葉子伏結(jié)點(diǎn)猜數(shù)寫(xiě)*/ty桃pe兼de加fin城tDa走ta幻玉Ty百pe;ty打pe克de秀fst