課后答案網(wǎng) 6 章 樹和二叉樹 一、 基礎知識題 的度為 4，其中度為 1， 2， 3和 4的結(jié)點個數(shù)分別為 4， 2， 1， 1，求樹 T 中的葉子數(shù)。 【解答】 設度為 ,1,2,m 的結(jié)點數(shù)分別為 , n m，結(jié)點總數(shù)為 n，分枝數(shù)為 B，則下面二式成立 n= n0+n1+n m (1) n=B+1= +mn m+1 (2) 由 (1)和 (2)得葉子結(jié)點數(shù) + 即： +(14+(22+(31+(41=8 棵完全二叉樹上有 1001 個結(jié)點，求葉子結(jié)點的個數(shù)。 【解答】因為在任意二叉樹中度為 2 的結(jié)點數(shù) 葉子結(jié)點數(shù) 如下關系：n2=以設二叉樹的結(jié)點數(shù)為 n, 度為 1 的結(jié)點數(shù)為 n= n2 n=2n0+002=2n0+于在完全二叉樹中，度為 1的結(jié)點數(shù) 多為 1，葉子數(shù) 整數(shù)。本題中度為 1的結(jié)點數(shù) 能是 0， 故 葉子結(jié)點的個數(shù) 501. 棵 124 個葉結(jié)點的完全二叉樹，最多有多少個結(jié)點。 【解答】由公式 n=2n0+ 1時，結(jié)點數(shù)達到最多 247個。 棵完全二叉樹有 500 個結(jié)點，請問該完全二叉樹有多少個葉子結(jié)點？有多少個度為 1的結(jié)點？有多少個度為 2 的結(jié)點？如果完全二叉樹有 501 個結(jié)點，結(jié)果如何？請寫出推導過程。 【解答】由公式 n=2n0+帶入具體數(shù)得， 500=2n0+子數(shù)是整數(shù)，度為 1的結(jié)點數(shù)只能為 1，故葉子數(shù)為 的結(jié)點數(shù)是 249. 若 完全二 叉樹有 501 個結(jié)點，則葉子數(shù) 251， 度為 2 的結(jié)點數(shù)是 250，度為 1的結(jié)點數(shù)為 0. 某二叉樹有 20個葉子結(jié)點，有 30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)是多少。 【解答】由公式 n=2n0+得 該二叉樹的總結(jié)點數(shù)是 69。 一棵具有 1025 個結(jié)點的二叉樹的高 h。 【解答】該二叉樹最高為 1025（單支樹），最低為完全二叉樹高 11。 課后答案網(wǎng) 棵二叉樹高度為 h，所有結(jié)點的度或為 0，或為 2，則這棵二叉樹最少有多少結(jié)點。 【解答】第一層只一個根結(jié)點，其余各層都兩個結(jié)點， 這棵二叉樹最 少結(jié)點數(shù)是 2 一棵有 244 個結(jié)點的完全三叉樹的高度是多少。 【解答】 設含 n 個結(jié)點的完全三叉樹的高度為 h，則有 0)的滿二叉樹對應的森林由多少棵樹構(gòu)成。 【解答】 結(jié)點，根結(jié)點的右子女，右子女的右子女，都是樹的根。 二叉樹結(jié)點的中序序列為 序序列為 該二叉樹對應的森林包括幾棵樹？ 【解答】 3棵樹。（只需畫出右子樹就可求解） 任意一棵樹，設它有 n 個結(jié)點，這 【解答】 數(shù)其實就是分支個數(shù)。根結(jié)點無分支所指，其余結(jié)點有且只有一個分支所指。 棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是多少？ 【解答】 2個。 棵左、右子樹 均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是多少 ? 【解答】 1個。 變換得的二叉樹。若 B 中右指針域為空的結(jié)點有幾個？ 【解答】 n+1 個。 分別找出滿足以下條件的所有二叉樹： (1) 二叉樹的前序序列與中序序列相同； (2) 二叉樹的中序序列與后序序列相同； (3) 二叉樹的前序序列與后序序列相同； (4) 二叉樹的前序序列與層次序列相同； 課后答案網(wǎng) 5) 二叉樹的前序、中序與后序序列均相同。 【解答】 前 序遍歷二叉樹的順序是“根 左子樹 右子樹”，中序遍歷的順序是“左子樹 根 右子樹”，后序遍歷順序是：“左子樹 右子樹根，根據(jù)以上原則，本題解答如下： 若 前 序序列與中序序列相同，則或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹。 若中序序列與后序序列相同，則或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹。 若 前 序序列與后序序列相同，則或為空樹，或為只有根結(jié)點的二叉樹。 若 二叉樹的前序、中序與后序序列均相同 ，則或為空樹，或為只有根結(jié)點的二叉樹。 知一棵二叉樹的前序遍歷的結(jié)果是 序遍歷的結(jié)果是畫出這棵二叉樹，對二叉樹進行中序線索化，并將該二叉樹轉(zhuǎn)換為森林。 B A J C E D G F H I n u l l n u l l 【解答】 課后答案網(wǎng) 知一棵二叉樹的后序遍歷序列為 時知道該二叉樹的中序遍歷序列為 畫出該二叉樹。 F E C I A B G D H 【解答】 二叉樹中每個結(jié)點均用一個字母表示，若一個結(jié)點的左子樹或右子樹為空，用 #表示，現(xiàn)前序遍歷二叉樹，訪問的結(jié)點序列為 C#E#F#，寫出中序和后序遍歷二叉樹時結(jié)點的訪問序列。 【解答】中序遍歷二叉樹時結(jié)點的訪問序列： #D#B#C#E#A#F# 后序遍歷二叉樹時結(jié)點的訪問序列。 #D#n 個結(jié)點的 k 叉樹（ k2）用 多少個空指針？ 課后答案網(wǎng) 解答】 k 叉樹（ k2）用 每個結(jié)點有 根結(jié)點沒有指針指向外 ，其余每個結(jié)點都有一個指針指向，故空指針的個數(shù)為： n(1 棵高度為 h 的滿 k 叉樹有如下性質(zhì)：根結(jié)點所在層次為 0；第 余各層上每個結(jié)點都有 果按層次自頂向下，同一層自左向右，順序從 1開始對全部結(jié)點進行編號，試問： (1)各層的結(jié)點個數(shù)是多少 ? (2)編號為 i 的結(jié)點的雙親結(jié)點（若存在）的編號是多少 ? (3)編號為 i 的結(jié)點的第 存在）的編號是多少？ (4)編號為 i 的結(jié)點有右兄弟的條件是 什么？其右兄弟結(jié)點的編號是多少？ 【解答】 (1)kl(l 為層數(shù)，按題意，根結(jié)點為 0層 ) （ 2）因為該樹每層上均有 根開始編號為 1，則結(jié)點 n 為結(jié)點 i 的子女，則關系式(k+21)的前一結(jié)點編號為 最右邊子女編號是 (k+1），故結(jié)點 k+1+m。 (4) 根據(jù)以上分析，結(jié)點 i 有右兄弟的條件 是，它不是雙親的從右數(shù)的第一子女，即 (k!=0，其右兄弟編號是 i+1。 明任一結(jié)點個數(shù)為 n(n0) 的二叉樹的高度至少為 (+1。 【解答】 最低高度二叉樹的特點是，除最下層結(jié)點個數(shù)不滿外，其余各層的結(jié)點數(shù)都應達到各層的最大值。設 n 個結(jié)點的二叉樹的最低高度是 h，則 n 應滿足2n 2此不等式，并考慮 有 h=1，即 任一結(jié)點個數(shù)為 n 的二叉樹的高度至少為 O( 知 A1.一棵順序存儲的完全二叉樹，如何求 出 Ai和 Aj的最近的共同祖先？ 【解答】 根據(jù)順序存儲的完全二叉樹的性質(zhì)，編號為 i/2，故 Ai和 Aj的最近公共祖先可如下求出： i/2!=j/2) if(ij) i=i/2; j=j/2; 退出 ，若 i/2=0,則最近公共祖先為根結(jié)點，否則最近公共祖先是 i/2。 知一棵滿二叉樹的結(jié)點個數(shù)為 20到 40 之間的素數(shù)，此二叉樹的葉子結(jié)點有多少個？ 【解答】 結(jié)點個數(shù)在 20 到 40的滿二叉樹且結(jié) 點數(shù)是素數(shù)的數(shù)是 31，其葉子數(shù)是 16。 含有 用順序存儲結(jié)構(gòu)的完全二叉樹中的序號最小的葉子結(jié)點的下標。要求寫出簡要步驟。 課后答案網(wǎng) 解答】 根據(jù)完全二叉樹的性質(zhì)，最后一個結(jié)點（編號為 n）的雙親結(jié)點的編號是 n/2，這是最后一個分枝結(jié)點，在它之后是第一個終端（葉子）結(jié)點，故序號最小的葉子結(jié)點的下標是 n/2+1。 證明 :同一棵二叉樹的所有葉子結(jié)點，在前序序列。中序序列以及后序序列中都按相同的相對位置出現(xiàn)（即先后順序相同），例如前序 序 序 【 證明】 前序遍歷是“根左右”，中序遍歷是“左根右”，后序遍歷是“左右根”。三種遍歷中只是訪問“根”結(jié)點的時機不同，對左右子樹均是按左右順序來遍歷的，因此所有葉子都按相同的相對位置出現(xiàn)。 具有四個結(jié)點的二叉樹的前序遍歷序列為；為長度等于 4 的由，排列構(gòu)成的字符序列，若任取作為上述算法的中序遍歷序列，試問是否一定能構(gòu)造出相應的二叉樹，為什么？試列出具有四個結(jié)點二叉樹的全部形態(tài)及相應的中序遍歷序列。 【解答】 若前序序列是 非由這四個字母的任意組合（ 4!=24）都能構(gòu)造出二叉樹。因為以 過棧只能得到 1/(n+1)*2n!/(n!*n!)=14 種，即以 前序序列的二叉樹的數(shù)目是 14。任取以 為中序遍歷序列，并不全能與前序的 列構(gòu)成二叉樹。例如：若取中序序列 不能。 該 14棵二叉樹的形態(tài)及中序序列略。 知某二叉樹的每個結(jié)點，要么其左、右子樹皆為空，要么其左、右子樹皆不空。又知該二叉樹的前序序列為： J、 F、 D、 B、 A、 C、 E、 H、 X、 I、 K；后序序列為： A、 C、 B、 E、 D、 X、 I、 H、 F、 K、 J。 請給出該二叉樹的中序序列（即中根次序），并畫出相應的二叉樹樹形。 【解答】 二叉樹中序序列 相應的二叉樹樹形略。 知一個森林的先序序列和后序序列如下，請構(gòu)造出該森林。 先序序列： 序序列： 【解答】森林的先序序列和后序序列對應其轉(zhuǎn)換的二叉樹的先序序列和中序序列，應先據(jù)此構(gòu)造二叉樹，再構(gòu)造出森林。 F A E B D C J H G I 課后答案網(wǎng) O N L 出同時滿足下列兩條件的兩棵不同的二叉樹。 (1)按先根序遍歷二叉樹順序為 (2)高度為 5 其對應的樹（森林）的高度最大為 4。 【解答】 A B D C E A B C D E 課后答案網(wǎng) 一維數(shù)組存放的一棵完全二叉樹； 寫出后序遍歷該二叉樹的結(jié)點訪問序列。 【解答】后序 遍歷該二叉樹的結(jié)點訪問序列為： 棵二叉樹的先序、中序和后序序列如下，其中有部分未標出，試構(gòu)造出該二叉樹。 先序序列為： C D E G H I K 中序序列為： C B F A _ J K I G 后序序列為： E F D B J I H A A B C E D G I H F J K 【解答】 樹形 應的度數(shù)如下： 后根次序： 次 數(shù)： 請畫出的樹形結(jié)構(gòu)圖。 I C A B G 課后答案網(wǎng) D F K J L H 【解答】 森林共有 n 個結(jié)點和 b 條邊 (& t-; if(t-& !t-| !t-& t-; ; if(t-t- if(t-t- 棵 n 個結(jié)點的完全二叉樹存放在二叉樹的順序存儲結(jié)構(gòu)中，試編寫非遞歸算法對該樹進行 先序遍歷。 【 題目分析】 二叉樹的順序存儲是按完全二叉樹的順序存儲格式，雙親與子女結(jié)點下標間有確定關系。順序存儲結(jié)構(gòu)的二叉樹用結(jié)點下標大于 n（完全二叉樹）或 0（對一般二叉樹的“虛結(jié)點”）判空。本題是完全二叉樹。 ,n) 對以順序結(jié)構(gòu)存儲的完全二叉樹 行前序遍歷 i=1,s; 棧 s 的棧頂指針，棧容量足夠大 i=s 取出棧頂元素 結(jié)束 二叉鏈表作為存儲結(jié)構(gòu)的二叉樹 ，按后序遍歷時輸出的結(jié)點順序為 ， 編寫一算法，要求輸出后序序列的逆序 ， 【題目分析】 二叉樹后序遍歷是按“左子樹右子樹根結(jié)點”的順序遍歷二叉樹，根據(jù)題意，若將遍歷順序改為“根結(jié)點右子樹左子樹”，就可以實現(xiàn)題目要求。 “先根”遍歷 if( /訪問根結(jié)點 /先根遍歷右子樹 /先根遍歷左子樹 二叉鏈表作為存儲結(jié)構(gòu)，設計 算法交換二叉樹中所有結(jié)點的左、右子樹。 將二叉樹 有結(jié)點的左右子樹交換 if(s； s=s; 左右子女交換 交換左子樹上所有結(jié)點的左右子樹 交換右子樹上所有結(jié)點的左右子樹 結(jié)束 【算法討論】 將上述算法中兩個遞歸調(diào)用語句放在前面，將交換語句放在最后，則是以后序遍歷方式交換所有結(jié)點的左右子樹。中序遍歷不適合本題。 二叉鏈表為存儲結(jié)構(gòu)，寫出在二叉樹中求值為 x 的結(jié)點在樹中層次數(shù)的算法。 題目分析 按層次遍歷，設一隊列 Q，用 別指向隊頭和隊尾元素， 向各層最右結(jié)點位置。 求值為 if(,; 層次數(shù) ;Q1=根結(jié)點入隊 x) %3dn” , 值為 if(Q+左子女入隊列 if(Q+右子女入隊列 if(; 本層最后一個結(jié)點已處理完 算法結(jié)束 知深度為 作為存儲結(jié)構(gòu)。試編寫算法求該二叉樹中葉子的個數(shù)。 【題目分析】 按完全二叉樹形式順序存儲二叉樹時，無元素的位置要當作“虛結(jié)點”。設虛結(jié)點取二叉樹結(jié)點以外的值（這里設為 0）。設結(jié)點序號為 i,則當i(22時，若 必為葉子結(jié)點。 T,n) 計算深度為 h 以一維數(shù)組 為存儲結(jié)構(gòu)的二叉樹的葉子結(jié)點數(shù)， ; 記葉子結(jié)點數(shù) i=0;i=i/2; 下標為 i 的結(jié)點的雙親結(jié)點的下標 j=j/2; 下標為 j 的結(jié)點的雙親結(jié)點的下標 所查結(jié)點的最近公共祖先的下標是 %d，值是 %d” ,i,Ai); 設元素類型整型。 知一棵完全二叉樹順序存儲于向量 s1.，試編寫算法由此順序存儲結(jié)構(gòu)建立該二叉樹的二叉鏈表。 ,i) 中，本算法建立二叉鏈表表示的完全二叉樹 if(i; *in) ,2*i)； *i+1n) ,2*i+1)； 算法討論】 初始調(diào)用時 ,i=1。 寫算法判別給定二叉樹是否為完全二叉樹。 【題目分析】 判定是否是完全二叉樹，可以使用隊列，在遍歷中利用完全二叉樹“若某結(jié)點無左子女就不應有右子女”的原則進行判斷。 判斷二叉樹是否是完全二叉樹 ,如是，返回 1，否則，返回 0 ; p=Q; 素是二叉樹結(jié)點指針，容量足夠大 if(p=1); ); ,p); 初始化隊列，根結(jié)點指針入隊 ) p=); 出隊 if(p-& !,p- 左子女入隊 if(p-; 前邊已有結(jié)點為空，本結(jié)點不空 課后答案網(wǎng) ; 首次出現(xiàn)結(jié)點為空 if(p-& !,p- 右子女入隊 if(p-; ; ; 算法討論 完全二叉樹證明還有其它方法。判斷時易犯的錯誤是證明其左子樹和右子樹都是完全二叉樹，由此推出整棵二叉樹必是完全二叉樹的錯誤結(jié)論。 樹以雙親表示法存儲，編寫計算樹的深度 的算法。 【題目分析】 以雙親表示法作樹的存儲結(jié)構(gòu)，對每一結(jié)點，找其雙親，雙親的雙親，直至（根）結(jié)點 ,就可求出每一結(jié)點的層次，取其結(jié)點的最大層次就是樹的深度。 t) 求以雙親表示法為存儲結(jié)構(gòu)的樹的深度 ; i=1; ; f=f 深度加 1,并取新的雙親 if( 最大深度更新 返回樹的深度 結(jié)束 知在二叉樹中， *根結(jié)點， *p 和 *q 為二叉樹中兩個結(jié)點，試編寫求距離它們最近的共同祖先的算法。 【題目分析】 后序遍歷最后訪問根結(jié)點，即在遞歸算法中，根是壓在棧底的。采用后序非遞歸遍歷，棧中存放二叉樹結(jié)點的指針，當訪問到某結(jié)點時，棧中所有元素均為該結(jié)點的祖先。本題要找 p和 q 的最近共同祖先結(jié)點 r ,不失一般性，設 p 在 序遍歷必然先 遍歷到結(jié)點 p，棧中元素均為 p 的祖先。將?？饺肓硪惠o助棧中。再繼續(xù)遍歷到結(jié)點 棧中元素從棧頂開始逐個到輔助棧中去匹配，第一個匹配（即相等）的元素就是結(jié)點 p 和 t; 表示結(jié)點的左子女已訪問， 為右子女已訪問 s,;棧，容量夠大 課后答案網(wǎng) p,q,r) 求二叉樹上結(jié)點 p 和 q 的最近的共同祖先結(jié)點 r ; |) & p & q) 結(jié)點入棧 s+t=s; bt= 沿左分枝向下 if(p) 不失一般性，假定 p在 遇結(jié)點 p 時，棧中元素均為 i=1;i0; 將棧中元素的樹結(jié)點到 匹配 pp=sij=j0;if(s1j共同的祖先已找到 n” )； 0 & s1) 退棧 if(0) s;bt=st-沿右分枝向下遍歷 結(jié)束 |) 、 結(jié)束 二叉鏈表作為存儲結(jié)構(gòu)，設計按層次遍歷二叉樹的算法。 層次遍歷二叉樹 if(); , ) p=); 出隊 p- 訪問結(jié)點 if(p-,p- 非空左子女入隊 if(p-,p- 非空右子女入隊 if(課后答案網(wǎng) 寫算法查找二叉鏈表中數(shù)據(jù)域值為 定各結(jié)點的數(shù)據(jù)域值各不相同），并打印出 x 所有祖先的數(shù)據(jù)域值。 【題目分析】 后序遍歷最后訪問根結(jié)點，當訪問到值為 x 的結(jié)點時，棧中所有元素均為該結(jié)點的 祖先。 x) 在二叉樹 ，查找值為 打印其所有祖先 t; 表示左子女被訪問， 右子女被訪問 s; 棧容量足夠大 ; ) & x) 結(jié)點入棧 s+t=s; bt= 沿左分枝向下 if(x) 所查結(jié)點的所有祖先結(jié)點的值為 :n” );找到 x i=1; 輸出祖先值后結(jié)束 0 & s1) 退棧（空遍歷） if(0) s;bt=st- 沿右分枝向下遍歷 ) 結(jié)束 計這樣的二叉樹，用它可以表示父子、夫妻和兄弟三種關系，并編寫一個查找任意父親結(jié)點的所有兒子結(jié)點的過程。 【題目分析】 用二叉樹表示出父子，夫妻和兄弟三種關系，可以用根結(jié)點表示父（祖先），根結(jié)點的左子女表示妻，妻的右子女表示子。這種二叉樹可以看成類似樹的孩子兄弟鏈表表示法；根結(jié)點是父，根無右子女，左子女表示妻，妻的右子女（右子 女的右子女等）均可看成兄弟（即父的所有兒子），兄弟結(jié)點又成為新的父，其左子女是兄弟（父的兒子）妻，妻的右子女（右子女的右子女等）又為兒子的兒子等等。首先遞歸查找某父親結(jié)點，若查找成功，則其左子女是妻，妻的右子女及右子女的右子女等均為父親的兒子。 課后答案網(wǎng) t,在二叉樹上查找值為 結(jié)點 ; if(t=p= 二叉樹上無 點 if(t-; p=t; 查找成功 p=t- if(0)p=t- p; 結(jié)束 t,x) 在二叉樹上查找結(jié)點值為 x 的所有的兒子 p=t,x); 在二叉樹 x if(p & p- 存在父結(jié)點 ,且有妻 q=p-q=q- 先指向其妻結(jié)點，再找到第一個兒子 q!= q- q=q-輸出父的所有兒子 結(jié)束 寫遞歸算法判定兩棵二叉樹是否相等。 t, x) 判定二叉樹 x 是否相等 t & !x) if(t & x & t-x-& t-x-& t-x- 知一棵高度為具有個結(jié)點的二叉樹，按順序方式存儲編寫將樹中最大序號葉子結(jié)點的祖先結(jié)點全部打印輸出的算法。 【題目分析】二叉樹中最大序號的葉子結(jié)點 ,是在順序存儲方式下編號最大的結(jié)點 ) 打印最大序號葉子結(jié)點的全部祖先 c=m; m=2btc=0) 找最大序號葉子結(jié)點 ,該結(jié)點存儲時在最后 f=c/2; f 課后答案網(wǎng) f!=0) 從結(jié)點 徑上所有結(jié)點均為祖先結(jié)點 btf); f=f/2; 逆序輸出，最老的祖先最后輸出 結(jié)束 二叉樹以二叉鏈表作為存儲結(jié)構(gòu) ，編寫算法對二叉樹進行非遞歸的中序遍歷。 對二叉樹進行非遞歸中序遍歷 s,p= s 是元素為二叉樹結(jié)點指針的棧，容量足夠大 ; p | ) p) s+p; bt=p- 沿左子樹向下 if() p=s p- p=p- 退棧，訪問，轉(zhuǎn)右子樹 結(jié)束 一個把 【 題目分析】 對一般二叉樹，僅根據(jù)一個先序、中序、后序遍歷，不能確定另一個遍歷序列。但對于滿二叉樹，任一結(jié)點的左右子樹均含有數(shù)量相等的結(jié)點，根據(jù)此性質(zhì)，可將任一遍歷序列轉(zhuǎn)為另一遍歷序列。 ,l1,h1,l2,將滿二叉樹的后序序列轉(zhuǎn)為先序序列， l1,h1,l2,序列初始和最后結(jié)點的下標。 if( 根結(jié)點 ; 訪問根結(jié)點 2; 左或右子樹的結(jié)點數(shù) l1,l1+,l2+將左子樹后序序列轉(zhuǎn)為先序序列 l1+l2+, 將右子樹后序序列轉(zhuǎn)為先序序列 t 課后答案網(wǎng) 二叉樹 左、右子樹都為空 ，或者其左、右子樹都不空，這種二叉樹有時稱為“嚴格二叉樹”。由“嚴格二叉樹”的前序序列和后序序列可以唯一確定該二叉樹。寫出根據(jù)這種二叉樹的前序序列和后序序列確定該二叉樹的遞歸算法。 【問題分析】前序序列的第一個結(jié)點是二叉樹的根，若該結(jié)點后再無其它結(jié)點，則該結(jié)點是葉子；否則，該結(jié)點必有左右子樹，且根結(jié)點后的第一個結(jié)點就是左子樹的根。到后序序列中查找這個左子樹的根，它將后序序列分成左右兩部分：左部分 (包括所查到的結(jié)點 )是二叉樹的左子樹 (可能為空 )，右部分 (除去最后的根結(jié)點 )則是右子樹 (可能為空 )。這樣，在確定根 結(jié)點后，可遞歸確定左右子樹。 BT,n,n,l1,h1,l2,由嚴格二叉樹的前序序列 l1:后序序列 l2:立二叉樹 p=*if(前序序列的第一個是根 if(p-p-葉子結(jié)點 分支結(jié)點 i=l2; ,l2,i); (p- +1,h1,i+1, 結(jié)束 寫一個遞歸算法，利用葉結(jié)點中空的右鏈指針域 所有葉結(jié)點自左至右鏈接成一個單鏈表，算法返回最左葉結(jié)點的地址（鏈頭）。 【題目分析】 葉子結(jié)點只有在遍歷中才能知道，這里使用中序遞歸遍歷。設置前驅(qū)結(jié)點指針 始為空。第一個葉子結(jié)點由指針 向，遍歷到葉子結(jié)點時，就將它前驅(qū)的 針指向它，最后葉子結(jié)點的 空。 全局變量 中序遍歷二叉樹 葉子結(jié)點從左到右鏈成一個單鏈表，表頭指針為if( 中序遍歷左子樹 課后答案網(wǎng) if(& 葉子結(jié)點 if( 處理第一個葉子結(jié)點 將葉子結(jié)點鏈入鏈表 中序遍歷右子樹 設置鏈表尾 知有一棵二叉鏈表表示的二叉樹，編寫算法，輸出從根結(jié)點到葉子結(jié)點的最長一枝上的所有結(jié)點。 【題目分析】 后序遍歷時棧中保留當前結(jié)點的祖先 的信息，用一變量保存棧的最高棧頂指針，每當退棧時，棧頂指針高于保存最高棧頂指針的值時，則將該棧倒入輔助