數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案第六章

數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案第六章數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案第六章數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案第六章資料僅供參考文件編號：2022年4月數(shù)據(jù)結(jié)構(gòu)課后習(xí)題答案第六章版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：第六章樹和二叉樹（下載后用閱讀版式視圖或web版式可以看清）習(xí)

題一、選擇題

1．有一“遺傳”關(guān)系：設(shè)x是y的父親，則x可以把它的屬性遺傳給y。表示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為(

)。

A.向量

B.樹

C圖

D.二叉樹

2．樹最合適用來表示(

)。

A.有序數(shù)據(jù)元素

B元素之間具有分支層次關(guān)系的數(shù)據(jù)

C無序數(shù)據(jù)元素

D.元素之間無聯(lián)系的數(shù)據(jù)

3．樹B的層號表示為la，2b，3d，3e，2c，對應(yīng)于下面選擇的(

)。

A.la(2b(3d,3e),2c)

B.a(b(D,e),c)

C.a(b(d,e),c)

D.a(b,d(e),c)

4.高度為h的完全二叉樹至少有(

)個結(jié)點，至多有(

)個結(jié)點。

A.2h_l

C．2h-1

D.2h

5.在一棵完全二叉樹中，若編號為f的結(jié)點存在右孩子，則右子結(jié)點的編號為(

)。

A.2i

B.2i-l

C.2i+l

D.2i+2

6.一棵二叉樹的廣義表表示為a(b(c)，d(e(，g(h))，f))，則該二叉樹的高度為

(

)。

7.深度為5的二叉樹至多有(

)個結(jié)點。

A.31

B.32

C.16

D.10

8.假定在一棵二叉樹中，雙分支結(jié)點數(shù)為15，單分支結(jié)點數(shù)為30個，則葉子結(jié)點數(shù)為(

)個。

A.15

B.16

C.17

D.47

9.題圖6-1中，(

)是完全二叉樹，(

)是滿二叉樹。

10.在題圖6-2所示的二叉樹中：

(1)A結(jié)點是

A.葉結(jié)點

B根結(jié)點但不是分支結(jié)點

C根結(jié)點也是分支結(jié)點

D.分支結(jié)點但不是根結(jié)點

(2)J結(jié)點是

A.葉結(jié)點

B．根結(jié)點但不是分支結(jié)點

C根結(jié)點也是分支結(jié)點

D.分支結(jié)點但不是根結(jié)點

(3)F結(jié)點的兄弟結(jié)點是

C．空

(4)F結(jié)點的雙親結(jié)點是

(5)樹的深度為

(6)B結(jié)點的深度為

(7)A結(jié)點所在的層是

11.在一棵具有35個結(jié)點的完全二叉樹中，該樹的深度為(

)。

12.一棵有124個葉結(jié)點的完全二叉樹，最多有(

)個結(jié)點。

A．247

B．248

C．249

D．250

13.用順序存儲的方法將完全二叉樹中所有結(jié)點逐層存放在數(shù)組R[1…n]中，結(jié)點R[i]若有左子樹，則左子樹是結(jié)點(

)。

A.R[2i+l]

B.R[2i]

[i/2]

D.R[2i-1]

14.在一非空二叉樹的中序遍歷序列中，根結(jié)點的右邊(

)。

A.只有右子樹上的所有結(jié)點

B.只有右子樹上的部分結(jié)點

C.只有左子樹上的部分結(jié)點

D.只有左子樹上的所有結(jié)點

15．一棵度為m的樹中，有ni個度為1的結(jié)點，有n2個度為2的結(jié)點……，有nm個度為m的結(jié)點，則該樹的葉結(jié)點數(shù)為(

)。

A.n1+n2+...+nm

B.

(m-l)nm+...+n2+1

+n2+1

D.nl-n2

16.已知某二叉樹的中序遍歷序列是debac，后序遍歷序列是dabec，它的前序遍歷序列是(

)。A.acbed

B.decab

C.deabc

D.cedba17.在一棵二叉樹的二叉鏈表中，空指針域等于所有非空指針域數(shù)加(

)。

18.線索二叉樹是一種(

)結(jié)構(gòu)。

A.邏輯

B．邏輯和存儲

C．物理

D.線性19.由權(quán)值分別是8，7，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為(

)。

A.23

B.37

C．46

D.4320.設(shè)T是哈夫曼樹，具有5個葉結(jié)點，樹T的高度最高可以是(

)。

二、填空題1.對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為____。2.在樹型結(jié)構(gòu)中，樹根結(jié)點沒有____結(jié)點，其余每個結(jié)點有且只有____個前驅(qū)結(jié)點：葉子結(jié)點沒有____結(jié)點，其余每個結(jié)點可以有____后繼結(jié)點。3.有一棵樹如題圖6-3所示，回答下面的問題。

這棵樹的根點是____；葉子結(jié)點是____；結(jié)點k3的度是____；結(jié)點k3的子女是____；結(jié)點k3的父結(jié)點是____；這棵樹的度為____；這棵樹的深度是____。4.假定一棵樹的廣義表表示為A(B(E)，C(F(H，I，J，G)，D)，則該樹的度為____，樹的深度為____，終端結(jié)點的個數(shù)為____，單分支結(jié)點的個數(shù)為____，雙分支結(jié)點的個數(shù)為____，3分支結(jié)點的個數(shù)為____，C結(jié)點的雙親結(jié)點為____，其孩子結(jié)點為____。5.一棵深度為h的滿k叉樹有如下性質(zhì)：第h層上的結(jié)點都是葉子結(jié)點，其余各層上的每個結(jié)點都有k棵非空子樹。如果按層次順序（同層自左至右）從1開始對全部結(jié)點編號，則：

(1)第i層結(jié)點數(shù)目是____。

(2)編號為n的結(jié)點的雙親結(jié)點（若存在）的編號是____。

(3)編號為n的結(jié)點的第i個孩子結(jié)點（若存在）的編號是____。

(4)編號為n的結(jié)點有右兄弟的條件是____：其右兄弟的編號是____。6．前序遍歷一棵樹相當(dāng)于____樹中對應(yīng)的二叉樹，后序遍歷一棵樹則相當(dāng)于樹中對應(yīng)的二叉樹。

7．二叉樹的遍歷分為____，樹與森林的遍歷包括____。8．一棵二叉樹的第i(i>=1)層最多有____個結(jié)點；一棵有n(n>0)個結(jié)點的滿二叉樹共有____個葉子和____個非終端結(jié)點。9.在一棵二叉樹中，假定雙分支結(jié)點數(shù)為5個，單分支結(jié)點數(shù)為6個，則葉子結(jié)點為____個。10．在一棵二叉樹中，第五層上的結(jié)點數(shù)最多為____。11.對于一棵具有n個結(jié)點的二叉樹，當(dāng)進(jìn)行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)為____個，其中____個用于鏈接孩子結(jié)點，____個空閑著。12.前序遍歷的順序是ABDGEHICFJ，則二叉樹的根是____。13.從概念上講，樹與二叉樹是兩種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是____14.結(jié)點最少的樹為____，結(jié)點最少的二叉樹為____。15.一棵完全二叉樹按層次遍歷的序列為ABCDEFGHI，則在前序遍歷中結(jié)點E的直接前驅(qū)為____，后序遍歷中結(jié)點B的直接后繼是____。16.某二叉樹的中序遍歷序列為ABCDEFG，后序序列為BDCAFGE，則該二叉樹結(jié)點的前序序列為____，該二叉樹對應(yīng)的森林包括____棵樹。17.用一維數(shù)組存放的一棵完全二叉樹如題圖6-4所示。

則后序遍歷該二叉樹時結(jié)點訪問的順序為____。18.由n個權(quán)值構(gòu)成的哈夫曼樹共有____個結(jié)點。19.由帶權(quán)為3，9，6，2，5的5個葉子結(jié)點構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長度為____。20.設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有____個。21.二叉樹的存儲結(jié)構(gòu)分為____，樹的存儲結(jié)構(gòu)分為____。三、判斷題1．樹中任意結(jié)點的子樹不必是有序的。(

)2．樹可以看成特殊的無向圖。(

)3．可以使用雙鏈表表示樹型結(jié)構(gòu)。(

)4．順序存儲方式只能用于存儲線性結(jié)構(gòu)。(

)5．完全二叉樹的某結(jié)點若無左孩子，則必是葉結(jié)點。(

)6．在葉子數(shù)目和權(quán)值相同的所有二叉樹中，最優(yōu)二叉樹一定是完全二叉樹。(

)7．由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹。(

)8．二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子樹結(jié)點的前面。

(

)9．二叉樹的前序和后序遍歷序列能惟一確定這棵二叉樹。

(

)10.中序線索二叉樹中，右線索若不為空，則一定指向其父結(jié)點。(

)四、算法和操作題1．假定一棵二叉樹廣義表表示為a(b(c)，d(e，D)，分別寫出對它進(jìn)行前序、中序、后序遍歷的結(jié)果。

前序：

中序：

后序：2．已知一棵二叉樹的中序和后序序列，求該二叉樹的高度和雙支、單支及葉子結(jié)點數(shù)。

中根序列：c，b，d，e，a，g，i,h,j，f

后根序列：c，e，d，b，i，j，h，g，fa

高度：

雙支：

單支：

葉子：

3．已知一棵樹邊的集合為{<I<SPAN>，M>，<I<SPAN>，N>，<E<SPAN>，I>，<B<SPAN>，E>，<B<SPAN>，D>，<A<SPAN>，B>，<G<SPAN>，J>，<G<SPAN>，K>，<C<SPAN>，G>，<C<SPAN>，F(xiàn)>，<H<SPAN>，L>，<C<SPAN>，H>，<A<SPAN>，C>)，請畫出這棵樹，并回答下列問題：

(1)哪個是根結(jié)點

(2)哪些是葉子結(jié)點

(3)哪個是結(jié)點G的雙親

(4)哪些是結(jié)點G的祖先

(5)哪些是結(jié)點G的孩子

(6)哪些是結(jié)點E的子孫

(7)哪些是結(jié)點E的兄弟哪些是結(jié)點F的兄弟

(8)結(jié)點B和N的層次號分別是什么

(9)樹的深度是多少

(10)以結(jié)點C為根的子樹的深度是多少4．將算術(shù)表達(dá)式((a+b)+c*(d+e)+f*(g+h)轉(zhuǎn)化為二叉樹。5.一棵二叉樹的結(jié)點數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于數(shù)組BT中，如題表6-1所示。畫出該二叉樹的鏈接表示形式。數(shù)組BT的存放形式是相對于滿二叉樹中編號為數(shù)組下標(biāo)值的結(jié)點值。若該結(jié)點不存在，則取0值。

6．假設(shè)前序遍歷某棵樹的結(jié)點次序為SACEFBDGHIJK；后序遍歷該樹的結(jié)點次序為CFEABHGIKJDS，請畫出這棵樹。7．已知一棵樹如題圖6-5所示，將其轉(zhuǎn)換為其孩子兄弟表示的二叉樹。并畫出該二叉樹的后序線索二叉樹。8．試找出分別滿足下列條件的所有二叉樹：

(1)前序遍歷序列和中序遍歷序列相同。

(2)中序遍歷序列和后序遍歷序列相同。

(3)前序遍歷序列和后序遍歷序列相同。9．已知信息為“ABCDBCDCBDBACB”，請按此信息構(gòu)造哈夫曼樹，求出每一字符的最優(yōu)編碼。10.己知中序線索二叉樹采用二叉鏈表存儲結(jié)構(gòu)，鏈結(jié)點的構(gòu)造為：其中若ltag為0，則lchild指向結(jié)點的前驅(qū)，否則lchild指向左孩子結(jié)點；若rtag為0，則rchild指向結(jié)點的后繼，否則rchild指向右孩子結(jié)點。下面的算法返回x所指結(jié)點的直接后繼結(jié)點的位置。若該算法有錯，則請改正錯誤；若無錯，請寫“正確”二字。

BiTree

INSUCC(BiTree

x)

{

s=X->rchild;

if（s->rtag）

while

（s->ltag）

s=s->rchild;

returns；

)五、算法設(shè)計題1．編寫對二叉樹進(jìn)行中序遍歷的非遞歸算法，并對算法執(zhí)行題圖6-6所示的二叉樹的情況進(jìn)行跟蹤（即給出各階段棧的變化及輸出的結(jié)點序列）。棧已經(jīng)定義：InitStack(S)（初始化）、Empty(S)（判棧空）、Push(S，p)（入棧）、Pop(S，p)（出棧）等操作。2．假設(shè)在表示一棵二叉樹的二叉鏈表上增加兩個域：雙親域用于指示其雙親結(jié)點，標(biāo)志域flag（可取0...2）的值，用以區(qū)分在遍歷過程中到達(dá)該結(jié)點時繼續(xù)向右或向左或訪問該結(jié)點。試以此存儲結(jié)構(gòu)編寫不用棧進(jìn)行后序遍歷的遞歸形式的算法。3．一棵具有n個結(jié)點的完全二叉樹，以一維數(shù)組作為存儲結(jié)構(gòu)，試設(shè)計一個對該完全二叉樹進(jìn)行前序遍歷的算法。4．設(shè)中序線索樹的結(jié)點由5個域組成。

Info：給出結(jié)點的數(shù)據(jù)域。

LT:標(biāo)志域，為0或1。

LL：當(dāng)LT為1時，給出該結(jié)點的左孩子的地址。

當(dāng)LT為0時，給出按中序遍歷的前驅(qū)結(jié)點地址。

RT:標(biāo)志域，為0或1。

RL：當(dāng)RT為1時，給出該結(jié)點的右孩子的地址。

當(dāng)RT為O時，給出按中序遍歷的后繼結(jié)點地址。

請編寫程序，在具有上述結(jié)點結(jié)構(gòu)的中序線索二叉樹上，求某一結(jié)點p按后序遍歷次序的后繼結(jié)點的地址q，設(shè)該中序線索二叉樹的根結(jié)點地址為r。

另外，請注意必須滿足：

(l)額外空間的使用只能為O(1)。

(2)程序為非遞歸形式。5．假設(shè)二叉樹采用鏈接方法存儲，編寫一個函數(shù)按凹入表表示法打印出該二叉樹。6．給出中序線索樹的結(jié)點結(jié)構(gòu)，設(shè)計算法在不使用棧和遞歸的情況下前序遍歷一棵中序線索樹，并分析它的時間復(fù)雜度。7．以二叉鏈表為存儲結(jié)構(gòu)，寫出交換各結(jié)點左右子樹的算法。8．假設(shè)二叉樹采用鏈接方法存儲，編寫一個函數(shù)按凹入表表示法打印出該二叉樹。第六章樹和二叉樹第6章樹和二叉樹

一、選擇題（參考答案）

1．B

2．B

3．C

4．A，C

5．C

6．C

7．A

8．B

9．A，B

10.(1)C

(2)A

(3)C

(4)A

(5)C

(6)A

(7)C

11．B

13．B

14．A

15．B

16．D

17．A

18．C

19．D

20．D

二、填空題（參考答案）

1．樹的總結(jié)點數(shù)-1。

2．前驅(qū)：1，后繼，任意多個。

3.kl,k2,k4,k5,k7,2,k5,k6,kl,3,4。

，4，6，1，1，2，A，F(xiàn)，G。

5.(1)ki-l,(2)

,(3)n-l×k+n+1,(4)i≠nk+l(n=0,l,2，…),n+1.

6．前序遍歷，中序遍歷。

7．前序，中序，后序，前序，后序。

8.2i-1，「2/n,2/n.

個。

10.160

11.2n，n-l，n+l。

12．A

13.樹可采用二叉樹的存儲結(jié)構(gòu)并可利用二叉樹的已有算法解決樹的有關(guān)問題。

14.只有1個結(jié)點的樹，空樹。

，F(xiàn)。

16.前序遍歷序列為：EACBDGF，森林包括1棵樹。

17.HIDJKEBLFGCA0

18.2n-l。

19.560

20．n+l。

21.順序存儲和鏈?zhǔn)酱鎯?，雙親鏈表表示法，孩子鏈表表示法，孩子兄弟鏈表表示法

三、判斷題

1.

√

2.

√

3.

√

4.×

5.

√

6.×

7.×

8.

√

9.×

10.×

四、算法和操作題

1．假設(shè)一棵二叉樹廣義表表示為a(b(c)，d(e，D)，分別寫出對它進(jìn)行前序、中序、后序遍歷的結(jié)果。

【解答】前序：a，b，c，d，e，D

中序：c，b，a，e，d，D

后序：c，b，e，D，d，a

2．已知一棵二叉樹的中序和后序序列，求該二叉樹的高度和雙支、單支及葉子結(jié)點數(shù)。

【解答】中序序列：c，b，d，e，a，g，i，h，j，f

后序序列：c，e，d，b，i，j，h，g，f，a

由中序和后序（前序）遍歷序列可惟一確定一棵二叉樹，基本思想是后序（前序）定根，中序分左右。由后序序列可知該樹的根結(jié)點為a，由中序遍歷序列可知該樹的左子樹為{c，b，d，e}，右子樹為{g，i，h，j，f）;再由后序序列可知該樹的左子樹的根結(jié)點為b，右子樹的根結(jié)點為f．再由中序遍歷序列可知b結(jié)點的左子樹為{c}，右子樹為{d，e）;再由后序遍歷序列可知右子樹{d，e}的根結(jié)點為d，再由中序遍歷序列可知d的左子樹為空，右子樹為{e}。對以f為根結(jié)點的子樹可做類似的分析。最后得到由中序和后序序列決定的二叉樹為：

a(b(c，d(，e))，f(g(，h(i，j))))，由此可知該樹：

高度：5

雙分支：3

單分支：3

葉結(jié)點：4。

3．已知一棵樹邊的集合為{<I，M>，<I，N>，<E，I>，<B，E>，<B，D>，<A，B>，<GJ>，<GK>，<C，G>，<C，F(xiàn)>，<H，L>，<C，H>，<A，C>}，請畫出這棵樹，并回答問題

【解答】根據(jù)邊集畫出的樹如下所示：

(1)根結(jié)點是：A。

(2)葉子結(jié)點是：D，M，N，F(xiàn)，J，K，L。

(3)結(jié)點G的雙親是：C。

(4)結(jié)點G的祖先是：A，C。

(5)結(jié)點G的孩子是：J，K。

(6)結(jié)點E的子孫是：I，M，N。

(7)結(jié)點E的兄弟是：D;結(jié)點F的兄弟是：G，H。

(8)結(jié)點B和N的層次號分別是：2，5。

(9)樹的深度是：5。

(10)以結(jié)點C為根的子樹的深度是：3。

4．將算術(shù)表達(dá)式((a+b)+c*(d+e)+f*(g+h)轉(zhuǎn)化為二叉樹。

【解答】轉(zhuǎn)化成如下二叉樹：

5．-棵二叉樹的結(jié)點數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于數(shù)組BT中，如題表6-1所示。畫出該二叉樹的鏈接表示形式。數(shù)組BT的存放形式是相對于滿二叉樹中編號為數(shù)組下標(biāo)值的結(jié)點值。若該結(jié)點不存在，則取0值。題表6-1【解答】二叉樹的鏈?zhǔn)奖硎緸椋?/p>

6．若前序遍歷某樹的結(jié)點次序：SACEFBDGHIJK;后序遍歷的結(jié)點次序為：CFEABHGIKJDS，畫出這棵樹。

【解答】畫出樹如下：

7．將原教材題圖6-5轉(zhuǎn)換為孩子兄弟所表示的二叉樹及該二叉樹的后序線索二叉樹如下：^

8．空樹滿足所有條件。非空樹如下：

(1)前序和中序遍歷序列相同的二叉樹是沒有左子樹的二叉樹（右單支樹）。

(2)中序和后序遍歷序列相同的二叉樹是沒有右子樹的二叉樹（左單支樹）。

(3)前序和后序遍歷序列相同的二叉樹是只有根的二叉樹。

9．在信息“ABCDBCDCBDBACB”中A，B，C，D四個字符出現(xiàn)的頻率依次是：2，5，4，3。

在哈夫曼樹中每個字符的最優(yōu)編碼：

可得編碼為：

A-110B-OC-10D-II1

信息編碼為：1010111

100

1110110100

10.錯誤。修改如下：

BiTree

INSUCC(BiTree

x)

{

S=X->rchild;

if(s->rtag)

while

（s->ltag）

s=s->lchild;

returnS;

}

五、算法設(shè)計題

1．編寫對二叉樹進(jìn)行中序遍歷的非遞歸算法，并對算法執(zhí)行原教材題圖6-6所示的二叉樹的情況進(jìn)行跟蹤（即給出各階段棧的變化及輸出的結(jié)點序列）。

【解答】中序遍歷的非遞歸算法如下：

voidInorderTraverse(BTreeT)

{InitStack(S);

p=T;

while(p&&1Empty(S))

{if(p)

{Push(S,p);p=p->lchild;

)

else

{pop(S,p);

printf("ooC",p->data);

p=p->rchild);

}

}

}

對于給定的二叉樹，算法執(zhí)行情況如下：A入棧，B入棧，D入棧，D出棧，訪問D，B出棧，訪問B，A出棧，訪問A，，C入棧，E入棧，E出棧，訪問E，G入棧，G出棧，訪問G，C出棧，訪問C，F(xiàn)入棧，F(xiàn)出棧，訪問F，棧和指針p均空，結(jié)束。

最后的遍歷序列是：DBAGECF。

2．假設(shè)在表示一棵二叉樹的二叉鏈表上增加兩個域：雙親域用于指示其雙親結(jié)點，標(biāo)志域flag（可取0，…，2）的值，用以區(qū)分在遍歷過程中到達(dá)該結(jié)點時繼續(xù)向右或向左或訪問該結(jié)點。試以此存儲結(jié)構(gòu)編寫不用棧進(jìn)行后序遍歷的遞推形式的算法。

【解答】要解決這一問題必須區(qū)分結(jié)點在訪問過程中的狀態(tài)，這可通過結(jié)點的標(biāo)志域來處理。對一個結(jié)點來說當(dāng)前的結(jié)點可能由：(1)其雙親結(jié)點轉(zhuǎn)換;(2)其左子樹遍歷結(jié)束轉(zhuǎn)換;

(3)其右予樹遍歷結(jié)束轉(zhuǎn)換。所以，算法主要執(zhí)行按這三種狀態(tài)進(jìn)行處理或處理當(dāng)前結(jié)點或轉(zhuǎn)換結(jié)點的狀態(tài)，從而算法可描述為：

voidpostorder(BTreeT)

棵具有n個結(jié)點的完全二叉樹，以一維數(shù)組作為存儲結(jié)構(gòu)，試設(shè)計一個對該完全二叉樹進(jìn)行前序遍歷的算法。

【解答】設(shè)完全二叉樹的結(jié)點以層次為序，按從上至下，由左至右的順序編號，存放在一維數(shù)組R[1，…，n]中。對于編號為t的結(jié)點，若存在子結(jié)點，其左孩子結(jié)點一定是2*t，右孩子結(jié)點是2*t+l，由此可得對完全二叉樹進(jìn)行前序遍歷的遞歸算法。

void

preorder(intR[]，intn，intt)

//前序遍歷二叉樹R[]

{

printf（”%C\n"，R[t]）;

//輸出當(dāng)前結(jié)點值

if(t*2<=n)preorder(R，n，t*2);

//遞歸前序遍歷左子結(jié)點

if(t*2+1<=n)preorder(R，n，t*2+1);

//遞歸前序遍歷右子結(jié)點

}

4．在不使用棧和遞歸的條件下，后序序列遍歷中序線索二叉樹，需要知道任意結(jié)點的后序直接后繼。中序線索樹所能提供的是當(dāng)前訪問結(jié)點的祖先（雙親）信息，利用雙親信息，就可以對中序線索樹進(jìn)行后序遍歷。中序線索樹有如下性質(zhì)：

●

若x是parent的左孩子，則parent是x的最右子孫的右線索。

●

若x是parent的右孩子，則parent是x的最左子孫的左線索。

因此設(shè)計兩個函數(shù)求給定結(jié)點的最左子孫的左線索和最右子孫的右線索;這兩個線索均是T的祖先。具體實現(xiàn)如下：

typedef

enum{Link,Thread}

Pointer

Tag;

//Link==0：指針;Thread==l：線索

typedef

struct

BiThrNode{

//中序線索樹結(jié)點結(jié)構(gòu)

ElemrTypedata

Struct

BiThrHode

lchild,rchild;

PointerTag

ltag,Rtag;

}BiThrNode,

*BiThrNode;

typedef

enum{lEFT,RIGHT)

TagType;

BiTHrNode

*LeftMose(BiTHrTree

T)

//求T的最左子孫的左線索

{

BighrNode

*p=T;

while(p->Ltag!=Thread)

p-p->lchild;

if(p->lchild)

returnp->lchild;

else

returnNULL;

}

BiTHrNode

*RightMost(BiTHrTreeT)

//求T的最右子孫的右線索

{

BiThrNode

*p=T;

while(p->Rtag!=Thread)

p-p->rchild;

if(p->rchild)

returnp->rchild;

else

returnNULL;

}

int

Isrightchild(BiThrTreeT,BiThrTree

&parent)

//判斷T是否是parent的右孩子，若是返回1，否則返回O

{

parent=LeftMost(T);

if(parent＆＆parent->rchild==p)

returnl;

else

(parent=NUIL;return

O;)

}

void

posttraverse—InThrTree(BiTheTreeT)

//后序遍歷中序線索樹，當(dāng)訪問標(biāo)志tag為RIGHT時才訪問當(dāng)前結(jié)點

Tagtypetag;

//待訪問標(biāo)志，表示當(dāng)前結(jié)點是從左孩子還是右孩子返回的

while(p)

{

while

(p->ltag!=Thread)

p=p->lchild;

if(p->rtag==link)tag=LEFT;

//左孩子為線索，右孩子為鏈，相當(dāng)于從左返回

elsetag=RIGHT;//當(dāng)前結(jié)點為葉結(jié)點，相當(dāng)于從右返回

while(tag==RiGHT)

{visit(p);

//僅當(dāng)tag==RIGHT時返回

if(Isrightchild(p,parent)

//從右孩子返回，需訪問parent，修改p指向雙親

{p=parent;

tag=RIGHT;)

else

//p是左孩子，用最右的線索找雙親結(jié)點

{p=RightMost(p);

if

(p＆＆p->Rtag==Thread)tag=RIGHT;

elsetag=LEFT;

}

}

if(tag==LEFT&＆p)

p=p->rchild;

}

}

5．凹入表示法打印二叉樹：

采用前序遍歷的遞歸函數(shù)依次輸出各結(jié)點的值，子結(jié)點比父結(jié)點右縮進(jìn)3個字符寬度，具體實現(xiàn)算法如下：

Void

disp(BiTreeT，

intspace)

//space為空格數(shù)

{

inti;

if(t)

{for(i=l;

i<space;

i++)

printf("");

//輸出space個空格

printf(”%d\n¨,

p->data);

disp(T->lchild,

space+3);

disp(T->rchild,

space+3);

}

}

6．前序遍歷一棵中序線索樹：

在不使用棧和遞歸的情況下對線索二叉樹進(jìn)行前序遍歷，需要知道任意結(jié)點前序的直接后繼。

typedef

enumfLink，Thread)PointerTag;

//Link:0指針，Thread:1線索

typedefstructBiThrNodet

//中序線索樹結(jié)點結(jié)構(gòu)

ElemTypedata;

Struct

BiThrNode

lchild,rchild;

PointerTag

Ltag,Rtag;

}

BiThrNode,*BiThrTree

;

voidpretraverse—thread(BiThrTreeT)

//前序遍歷帶頭結(jié)點的中序線索樹T

{

BiTrhTreep=