第六章樹和二叉樹一、樹的基本概念二、二叉樹、遍歷、線索化三、樹和森林四、哈夫曼樹【教學目的】掌握樹的基本概念，二叉樹的基本概念，二叉樹的邏輯結構、存儲結構以及二叉樹的操作的實現；掌握二叉樹與樹和森林的轉換，進而掌握樹和森林的存儲結構，利用二叉樹解決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