【正文】 p = prchild。 while ( plchild ) p = plchild。 // 轉(zhuǎn)右子樹的最左下結(jié)點 } else { // 右子樹為空，下一個在上層 f = pparent。 while ( p == frchild ) { // 若p是右子樹則一直上溯 p = f。 f = fparent。 } } }}7. 遍歷二叉樹的應(yīng)用1176。. 寫出遍歷序列（前、中、后序）ABCDEGHF2176。. 根據(jù)遍歷序列畫出二叉樹(a) 已知前序和中序序列，唯一確定二叉樹。例：前序：ABDEGCFH，中序：DBGEAFHC，畫出二叉樹。分析：前序序列的第一個是根，這是解題的突破口。步驟：①前序序列的第一個是根 ②在中序序列中標出根，分成左右子樹 ③在前序序列中標出左右子樹(根據(jù)結(jié)點個數(shù)即可) ④分別對左右子樹的前序和中序序列重復以上步驟直至完成。(b) 已知后序和中序序列，唯一確定二叉樹。例：后序：DGEBHFCA，中序：DBGEAFHC，畫出二叉樹。分析：后序序列的最后一個是根，這是解題的突破口。步驟：①后序序列的最后一個是根 ②在中序序列中標出根，分成左右子樹 ③在后序序列中標出左右子樹(根據(jù)結(jié)點個數(shù)即可) ④分別對左右子樹的后序和中序序列重復以上步驟直至完成。(c) 已知前序和后序序列，不存在度為1的結(jié)點時能唯一確定二叉樹。例：前序：ABDEC，后序：DEBCA，畫出二叉樹。又前序AB，后序BA則不能唯一確定二叉樹。注：對于不存在度為1的結(jié)點的二叉樹，首先確定根結(jié)點，然后總可以將其余結(jié)點序列劃分成左右子樹，以此類推即可確定二叉樹。說明：畫出二叉樹后可以進行遍歷以便驗證。3176。. 編寫算法思路：按五種形態(tài)(①⑤)分析，適度簡化。例：求二叉樹結(jié)點的個數(shù)。分析：① 0。 ② 1。 ③ L+1。 ④ 1+R。 ⑤ 1+L+R。簡化：② 1+L=0+R=0 ③ 1+L+R=0 ④ 1+L=0+R ⑤ 1+L+R 可合并成⑤一種情況。int NodeCount ( BinTree bt ){ if ( bt==0 ) return 0。 else return 1 + NodeCount(btlchild) + NodeCount(btrchild)。}例：求二叉樹葉子結(jié)點的個數(shù)。分析：① 0。 ② 1。 ③ L。 ④ R。 ⑤ L+R。簡化：③④⑤可合并成⑤。int LeafCount ( BinTree bt ){ if ( bt==0 ) return 0。 else if ( btlchild==0 and btrchild==0 ) return 1。 else return LeafCount(btlchild) + LeafCount(btrchild)。}例：求二叉樹的深度。分析：① 0。 ② 1。 ③ 1+L。 ④ 1+R。 ⑤ 1+max(L,R)。簡化：②③④⑤可合并成⑤。int Depth ( BinTree bt ){ if ( bt==0 ) return 0。 else return 1 + max(Depth(btlchild), Depth(btrchild))。}8. 線索二叉樹1176。. 線索n個結(jié)點的二叉鏈表中有n+1個空指針，可以利用其指向前驅(qū)或后繼結(jié)點，叫線索，同時需附加一個標志，區(qū)分是子樹還是線索。 lchildltagdatartagrchild0/10/1lchild 有左子樹，則指向左子樹，標志ltag == 0； 沒有左子樹，可作為前驅(qū)線索，標志ltag == 1。rchild 有右子樹，則指向右子樹，標志rtag == 0； 沒有右子樹，可作為后繼線索，標志rtag == 1。2176。. 線索化二叉樹利用空指針作為線索指向前驅(qū)或后繼。左邊空指針可以作為前驅(qū)線索，右邊空指針可以作為后繼線索，可以全線索化或部分線索化。表 線索化二叉樹的類型前驅(qū)、后繼線索前驅(qū)線索后繼線索中序線索化中序全線索中序前驅(qū)線索中序后繼線索前序線索化前序全線索前序前驅(qū)線索前序后繼線索后序線索化后序全線索后序前驅(qū)線索后序后繼線索3176。. 畫出線索二叉樹思路：先寫出遍歷序列，再畫線索。步驟： 標出必要的空指針（前驅(qū)224。左指針；后繼224。右指針，要點：“不要多標，也不要少標”）。 寫出對應(yīng)的遍歷序列（前序，中序或后序）。ABCDEGHFABCDEGHF 對照遍歷結(jié)果畫線索。例：畫出圖中二叉樹的后序后繼線索。步驟：先標出所有空的右指針(DGCH)；寫出后序遍歷結(jié)果：DGEBHFCA；標出后繼線索：D224。G, G224。E, C224。A, H224。F。如圖。4176。. 遍歷線索二叉樹反復利用孩子和線索進行遍歷，可以避免遞歸。9. 樹和森林1176。. 樹的存儲結(jié)構(gòu)雙親表示法，孩子表示法，孩子兄弟表示法。特點：雙親表示法容易求得雙親，但不容易求得孩子；孩子表示法容易求得孩子，但求雙親麻煩；兩者可以結(jié)合起來使用。孩子兄弟表示法，容易求得孩子和兄弟，求雙親麻煩，也可以增加指向雙親的指針來解決。2176。. 樹與二叉樹的轉(zhuǎn)換表 樹和二叉樹的對應(yīng)關(guān)系樹對應(yīng)的二叉樹根根第一個孩子左孩子下一個兄弟右孩子特點：由樹轉(zhuǎn)化成的二叉樹，根結(jié)點沒有右孩子例：樹轉(zhuǎn)換成二叉樹。 ABICDFHGJKEABICDFHGJKE3176。. 森林與二叉樹的轉(zhuǎn)換森林中第1棵樹的根作為對應(yīng)的二叉樹的根；其他的樹看作第1棵樹的兄弟；森林中的樹轉(zhuǎn)換成對應(yīng)的二叉樹。則森林轉(zhuǎn)換成對應(yīng)的二叉樹。例：將森林轉(zhuǎn)換成對應(yīng)的二叉樹。參見課本P138。4176。. 樹的遍歷樹的結(jié)構(gòu)：①根，②根的子樹。先根遍歷：①②。例：ABCDEFGHIJK。后根遍歷：②①。例：CEDFBHGJKIA。5176。. 遍歷森林森林的結(jié)構(gòu)：①第一棵樹的根，②第一棵樹的根的子樹森林，③ 其余樹(除第一棵外)組成的森林。先序遍歷：①②③。例：ABCDEFGHIJ。中序遍歷：②①③。例：BDCEAGFIJH。注：先序遍歷森林，相當于依次先根遍歷每一棵樹；中根遍歷森林相當于后根遍歷每一棵樹。ABICDFHGJKEAHBCEGFIJD①①②②③樹的結(jié)構(gòu)劃分森林的結(jié)構(gòu)劃分6176。. 遍歷樹、森林與遍歷二叉樹的關(guān)系表 遍歷樹、森林和二叉樹的關(guān)系樹森林二叉樹先根遍歷先序遍歷先序遍歷后根遍歷中序遍歷中序遍歷10. 赫夫曼樹及其應(yīng)用1176。. 最優(yōu)二叉樹(赫夫曼樹，哈夫曼樹)樹的帶權(quán)路徑長度：所有葉子結(jié)點的帶權(quán)路徑長度之和。 路徑長度lk按分支數(shù)目計算。帶權(quán)路徑長度最小的二叉樹稱為最優(yōu)二叉樹，或赫夫曼樹(哈夫曼樹)。2176。. 構(gòu)造赫夫曼樹算法：參見課本P145。簡單說，“每次取兩個最小的樹組成二叉樹” 不準確的說法，只為便于理解和記憶，不要在正式場合引用。3176。. 赫夫曼編碼(前綴碼)向左分支為0，向右分支為1，從根到葉子的路徑構(gòu)成葉子的前綴編碼。例：字符及其權(quán)值如下：A(6), B(7), C(1), D(5), E(2), F(8)，構(gòu)造哈夫曼樹和哈夫曼編碼，計算帶權(quán)路徑長度。A6B7C1D5E2F8A6B7C1D5E2F83A6B7C1D5E2F88A6B7C1D5E2F8813A6B7C1D5E2F81316A6B7C1D5E2F8ABCDEF0010001111哈夫曼編碼：A:00B:01C:1110D:110E:1111F:10WPL = (6+7+8)*2+5*3+(1+2)*4 = 69哈夫曼樹或采用課本上的算法計算，如下。表 赫夫曼算法weightparentlchildrchildweightparentlchildrchild1A60001A69002B70002B79003C10003C17004D50004D58005E20005E27006F80006F810007000073835800008810479000091311121000001016116811000011290910結(jié)果同上。說明：同樣的一組權(quán)值可能構(gòu)造出不同的哈夫曼樹，結(jié)果不一定唯一，但帶權(quán)路徑長度都是最小的。技巧：要使前一種方法構(gòu)造出的赫夫曼樹和課本上算法產(chǎn)生的一樣，只要把每次合并產(chǎn)生的二叉樹放在樹的集合的末尾，并且總是用兩個最小樹的前者作為左子樹后者作為右子樹。二、 習題 度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，…，nk個度為k的結(jié)點，問該樹中有多少個葉子結(jié)點。 有n個葉子結(jié)點的完全二叉樹的高度是多少? 編寫算法按照縮進形式打印二叉樹。 編寫算法按照逆時針旋轉(zhuǎn)90度的形式打印二叉樹。 編寫算法判斷二叉樹是否是完全二叉樹。 編寫算法求二叉樹中給定結(jié)點的所有祖先。 編寫算法求二叉樹中兩個結(jié)點的最近的共同祖先。 編寫算法輸出以二叉樹表示的算術(shù)表達式（中綴形式），要求在必要的地方輸出括號。 樹采用孩子兄弟鏈表存儲，編寫算法求樹中葉子結(jié)點的個數(shù)。 采用孩子兄弟鏈表存儲樹，編寫算法求樹的度。 采用孩子兄弟鏈表存儲樹，編寫算法求樹的深度。 已知二叉樹的前序和中序序列，編寫算法建立該二叉樹。 樹T的先根遍歷序列為GFKDAIEBCHJ，后根遍歷序列為DIAEKFCJHBG，畫出樹T。 一森林F轉(zhuǎn)換成的二叉樹的先序序列為ABCDEFGHIJKL，中序序列為CBEFDGAJIKLH。畫出森林F。 某通信過程中使用的編碼有8個字符A,B,C,D,E,F,G,H，其出現(xiàn)的次數(shù)分別為20, 6, 34, 11, 9, 7, 8, 5。若每個字符采用3位二進制數(shù)編碼，整個通信需要多少字節(jié)？請給出哈夫曼編碼，以及整個通信使用的字節(jié)數(shù)？ n個權(quán)值構(gòu)造的哈夫曼樹共有多少個結(jié)點？第7章 圖一、 基礎(chǔ)知識和算法1. 圖的有關(guān)概念圖，頂點，弧，弧頭，弧尾；有向圖（頂點集+弧集），0≤e≤n(n1)，無向圖（頂點集+邊集），0≤e≤n(n1)/2；稀疏圖（enlogn），稠密圖；完全圖e=n(n1)/2，有向完全圖e=n(n1)；網(wǎng)，有向網(wǎng)，無向網(wǎng)。子圖，鄰接點，頂點的度，入度，出度；路徑，路徑長度（經(jīng)過邊或弧的數(shù)目），簡單路徑，回路（環(huán)），簡單回路（簡單環(huán)）；連通圖，連通分量，強連通分量。例：有6個頂點組成的無向圖構(gòu)成連通圖，最少需要(_a_)條邊；當邊的數(shù)目大于(_b_)時，該圖必定連通。分析：a. 5。最少有n1條邊就可以構(gòu)成連通圖。 b. 10?？紤]將n個頂點分成兩組，一組有n1個頂點，另一組只有1個頂點。首先在第一組中添加邊，直到n1個頂點構(gòu)成全連通子圖，共(n1)(n2)/2條邊，此后若再在圖中任意添加一條邊將必定連通兩組頂點，從而構(gòu)成連通圖。思考：對有向圖有何結(jié)論。2. 圖的存儲結(jié)構(gòu)(1) 圖的存儲結(jié)構(gòu)常見圖的存儲結(jié)構(gòu)有：鄰接矩陣，鄰接表，逆鄰接表，十字鏈表，鄰接多重表。鄰接多重表只適用于存儲無向圖，其他存儲結(jié)構(gòu)可以存儲無向圖和有向圖。ABCDE例：畫出圖的鄰接矩陣、鄰接表、逆鄰接表和十字鏈表。(2) 鄰接矩陣簡言之，“數(shù)組(頂點)+二維數(shù)組(弧)+個數(shù)” 不準確的說法，只為便于理解和記憶，不要在正式場合引用。const int MAX_VERTEX = 最大頂點個數(shù)。typedef struct Graph { // 圖 VertexType vexs[MAX_VERTEX]。 // 頂點向量 ArcType arcs[MAX_VERTEX] [MAX_VERTEX]。 // 鄰接矩陣 int vexnum, arum。 // 頂點和弧的個數(shù)} Graph。圖：有邊(弧)為1；否則為0。網(wǎng)：有邊(弧)為權(quán)值；否則為∞。存儲空間個數(shù)為n2，與邊的數(shù)目無關(guān)。無向圖的鄰接矩陣是對稱的。 0110000110000101000010010ABCDE(3) 鄰接表簡