數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏第6章課件

第六章樹和二叉樹7/22/20231【課前思考】1.你見過家族譜系圖嗎？試以圖形表示從你的祖父起的家族成員關(guān)系。2.這類圖形正是本章要討論的"樹"結(jié)構(gòu)，你試用關(guān)系(即有序?qū)Φ募?表示上列的家族譜系圖。上列家族譜系圖可用如下關(guān)系表示：

<祖父，伯父>，<祖父，父親>，<祖父，叔父>，<伯父，堂兄>，<伯父，堂姐>，<父親，你>，<叔父，堂弟>，<堂兄，侄兒>7/22/20232【學(xué)習(xí)目標(biāo)】

1．領(lǐng)會(huì)樹和二叉樹的類型定義，理解樹和二叉樹的結(jié)構(gòu)差別。

2．熟記二叉樹的主要特性，并掌握它們的證明方法。

3．熟練掌握二叉樹的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。

4．理解二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。

5．熟練掌握二叉樹和樹的各種存儲(chǔ)結(jié)構(gòu)及其建立的算法。

6．學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。

7．了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。7/22/20233【重點(diǎn)和難點(diǎn)】二叉樹和樹的遍歷及其應(yīng)用是本章的學(xué)習(xí)重點(diǎn)，而編寫實(shí)現(xiàn)二叉樹和樹的各種操作的遞歸算法也恰是本章的難點(diǎn)所在?！局R(shí)點(diǎn)】樹的類型定義、二叉樹的類型定義、二叉樹的存儲(chǔ)表示、二叉樹的遍歷以及其它操作的實(shí)現(xiàn)、線索二叉樹、樹和森林的存儲(chǔ)表示、樹和森林的遍歷以及其它操作的實(shí)現(xiàn)、最優(yōu)樹和赫夫曼編碼7/22/20234【學(xué)習(xí)指南】本章是整個(gè)課程的第二個(gè)學(xué)習(xí)重點(diǎn)，也是整個(gè)課程中的一大難點(diǎn)。在本章的學(xué)習(xí)過程中主要應(yīng)該學(xué)會(huì)如何根據(jù)二叉樹和樹的結(jié)構(gòu)及其操作的遞歸定義編寫遞歸算法。本章必須完成的算法設(shè)計(jì)題為:6.27,6.28,6.33,6.41,6.43,6.45,6.46,6.47,6.49,6.50,6.51,6.57,6.59,6.68和6.66。7/22/202356.1樹的類型定義6.2二叉樹的類型定義6.3

二叉樹的存儲(chǔ)結(jié)構(gòu)6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼7/22/202366.1樹的類型定義樹是由n（n≥0）個(gè)結(jié)點(diǎn)組成的有限集合。若n=0，稱為空樹；若n>0，則：（1）其中必有一個(gè)稱為根（root）的特定結(jié)點(diǎn)，它沒有直接前驅(qū)，但有零個(gè)或多個(gè)直接后繼；（2）除根結(jié)點(diǎn)以外的其它n-1結(jié)點(diǎn)可以劃分為m（m≥0）個(gè)互不相交的有限集合T0，T1，…，Tm-1，每個(gè)集合Ti（i=0,1,…,m-1）又是一棵樹，稱為根的子樹，每棵子樹的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。由此可知，樹的定義是一個(gè)遞歸的定義，即樹的定義中又用到了樹的概念。7/22/20237ADTTree{數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數(shù)據(jù)關(guān)系R：7/22/20238

基本操作：查找類

插入類刪除類}ADTTree7/22/20239

Root(T)//求樹的根結(jié)點(diǎn)

查找類：Value(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的元素值

Parent(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的雙親結(jié)點(diǎn)LeftChild(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的最左孩子RightSibling(T,cur_e)//求當(dāng)前結(jié)點(diǎn)的右兄弟TreeEmpty(T)//判定樹是否為空樹TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷7/22/202310InitTree(&T)//初始化置空樹

插入類：CreateTree(&T,definition)//按定義構(gòu)造樹Assign(T,cur_e,value)//給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)//將以c為根的樹插入為結(jié)點(diǎn)p的第i棵子樹7/22/202311

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹7/22/202312ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:7/22/202313(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：子樹之間不存在確定的次序關(guān)系。7/22/202314對(duì)比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點(diǎn)一棵樹的邏輯結(jié)構(gòu)可以用二元組描述為：tree=(k,R)k={ki∣1≤i≤n;n≥0,kielemtype}R={r}其中，n為樹中結(jié)點(diǎn)個(gè)數(shù)，若n=0，則為一棵空樹，n>0時(shí)稱為一棵非空樹，而關(guān)系r應(yīng)滿足下列條件：（1）有且僅有一個(gè)結(jié)點(diǎn)沒有前驅(qū),稱該結(jié)點(diǎn)為樹根;（2）除根結(jié)點(diǎn)以外,其余每個(gè)結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū);（3）樹中每個(gè)結(jié)點(diǎn)可以有多個(gè)直接后繼(孩子結(jié)點(diǎn))。7/22/202315~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個(gè)數(shù)據(jù)元素(無前驅(qū))

根結(jié)點(diǎn)(無前驅(qū))最后一個(gè)數(shù)據(jù)元素(無后繼)多個(gè)葉子結(jié)點(diǎn)(無后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、一個(gè)后繼)其它數(shù)據(jù)元素(一個(gè)前驅(qū)、多個(gè)后繼)7/22/202316基本術(shù)語7/22/202317結(jié)點(diǎn):結(jié)點(diǎn)的度:樹的度:葉子結(jié)點(diǎn):分支結(jié)點(diǎn):數(shù)據(jù)元素+若干指向子樹的分支分支的個(gè)數(shù)樹中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)HIJMDD7/22/202318(從根到結(jié)點(diǎn)的)路徑：孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)、堂兄弟祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)結(jié)點(diǎn)的層次:樹的深度：

由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1，第l層的結(jié)點(diǎn)的子樹根結(jié)點(diǎn)（即孩子結(jié)點(diǎn)）的層次為l+1樹中葉子結(jié)點(diǎn)所在的最大層次7/22/202319任何一棵非空樹是一個(gè)二元組Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點(diǎn)F被稱為子樹森林森林：是m（m≥0）棵互不相交的樹的集合ArootBCDEFGHIJMKLF7/22/2023206.2

二叉樹的類型定義7/22/202321

二叉樹或?yàn)榭諛?，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹7/22/202322二叉樹的特點(diǎn)：（1）每個(gè)結(jié)點(diǎn)的度都不大于2，即每個(gè)結(jié)點(diǎn)的度為0、1或2；（2）每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)次序不能任意顛倒。即每個(gè)孩子有左右之分。我們把位于左邊的孩子叫做左孩子，位于右邊的孩子叫做右孩子。7/22/202323二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點(diǎn)NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹7/22/202324

二叉樹的主要基本操作：查找類插入類刪除類7/22/202325

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());查找類7/22/202326

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);插入類7/22/202327ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);刪除類7/22/202328二叉樹

的重要特性7/22/202329

性質(zhì)1：

在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。(i≥1)用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

層時(shí)，只有一個(gè)根結(jié)點(diǎn)：

2i-1=20=1；假設(shè)對(duì)所有的j，1≤j

i，命題成立；二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹，則第i層的結(jié)點(diǎn)數(shù)=2i-22=2i-1

。7/22/202330性質(zhì)2：

深度為k的二叉樹上至多含2k-1

個(gè)結(jié)點(diǎn)（k≥1）。證明：基于上一條性質(zhì)，深度為k的二叉樹上的結(jié)點(diǎn)數(shù)至多為

20+21+

+2k-1=2k-1。7/22/202331

性質(zhì)3：

對(duì)任何一棵二叉樹，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1。證明：設(shè)二叉樹上結(jié)點(diǎn)總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)(即邊數(shù))b=n1+2n2

而n

=b+1=>b=n-1=n0+n1+n2-1由此，n0=n2+1

。7/22/202332兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789101112131415abcdefghij滿二叉樹必為完全二叉樹，而完全二叉樹不一定是滿二叉樹。

7/22/202333

性質(zhì)4：

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

log2n+1

。證明：設(shè)完全二叉樹的深度為k則根據(jù)第二條性質(zhì)得2k-1-1<n≤

2k–1或2k-1≤n<2k

即k-1≤log2n<k,log2n<k≤log2n+1因?yàn)閗只能是整數(shù)，因此，k=log2n

+1。7/22/202334性質(zhì)5：若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行1至n的編號(hào)，則對(duì)完全二叉樹中任意一個(gè)編號(hào)為i的結(jié)點(diǎn)：

(1)若i=1，則該結(jié)點(diǎn)是二叉樹的根，無雙親，否則，編號(hào)為i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)；

(2)若2i>n，則該結(jié)點(diǎn)無左孩子，

否則，編號(hào)為2i的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；

(3)若2i+1>n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)，

否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。7/22/202335

可以用歸納法證明其中的（2）和（3）：當(dāng)i=1時(shí)，由完全二叉樹的定義知，如果2×i=2≤n，說明二叉樹中存在兩個(gè)或兩個(gè)以上的結(jié)點(diǎn)，所以其左孩子存在且序號(hào)為2；反之，如果2>n，說明二叉樹中不存在序號(hào)為2的結(jié)點(diǎn)，其左孩子不存在。同理，如果2×i+1=3≤n，說明其右孩子存在且序號(hào)為3；如果3>n，則二叉樹中不存在序號(hào)為3的結(jié)點(diǎn)，其右孩子不存在。假設(shè)對(duì)于序號(hào)為j(1≤j≤i)的結(jié)點(diǎn)，當(dāng)2×j≤n時(shí)，其左孩子存在且序號(hào)為2×j，當(dāng)2×j>n時(shí)，其左孩子不存在；當(dāng)2×j+1≤n時(shí)，其右孩子存在且序號(hào)為2×j+1，當(dāng)2×j+1>n時(shí)，其右孩子不存在。

7/22/202336

當(dāng)i=j+1時(shí)，根據(jù)完全二叉樹的定義，若其左孩子存在，則其左孩子結(jié)點(diǎn)的序號(hào)一定等于序號(hào)為j的結(jié)點(diǎn)的右孩子的序號(hào)加1，即其左孩子結(jié)點(diǎn)的序號(hào)等于（2×j+1）+1=2（j+1）=2×i，且有2×i≤n；如果2×i>n，則左孩子不存在。若右孩子結(jié)點(diǎn)存在，則其右孩子結(jié)點(diǎn)的序號(hào)應(yīng)等于其左孩子結(jié)點(diǎn)的序號(hào)加1，即右孩子結(jié)點(diǎn)的序號(hào)為2×i+1，且有2×i+1≤n；如果2×i+1>n，則右孩子不存在。故（2）和（3）得證。7/22/202337

由（2）和（3）我們可以很容易證明（1）。當(dāng)i=1時(shí)，顯然該結(jié)點(diǎn)為根結(jié)點(diǎn)，無雙親結(jié)點(diǎn)。當(dāng)i>1時(shí)，設(shè)序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為m，如果序號(hào)為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，根據(jù)（2）有i=2×m，即m=i/2;如果序號(hào)為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的右孩子，根據(jù)（3）有i=2×m+1，即m=（i-1）/2=i/2-1/2，綜合這兩種情況，可以得到，當(dāng)i>1時(shí)，其雙親結(jié)點(diǎn)的序號(hào)等于i/2。證畢。

對(duì)完全二叉樹，還有以下性質(zhì)：（1）若結(jié)點(diǎn)j序號(hào)為奇數(shù)且不等于1，則它的左兄弟為j-1；（2）若結(jié)點(diǎn)j序號(hào)為偶數(shù)且不等于n，它的右兄弟為j+1；（3）結(jié)點(diǎn)j所在層數(shù)(層次)為log2j+1；7/22/2023386.3二叉樹的存儲(chǔ)結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示一、二叉樹的順序存儲(chǔ)表示二叉樹的結(jié)構(gòu)是非線性的，每一結(jié)點(diǎn)最多可有兩個(gè)后繼。二叉樹的存儲(chǔ)結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。7/22/202339#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點(diǎn)數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)SqBiTreebt;一、二叉樹的順序存儲(chǔ)表示7/22/202340例如:ABCDEF

ABDCEF

0123456789101112131401326將一棵二叉樹按完全二叉樹順序存放到一個(gè)一維數(shù)組中，若該二叉樹為非完全二叉樹，則必須將相應(yīng)位置空出來，使存放的結(jié)果符合完全二叉樹形狀。7/22/202341二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示1.二叉鏈表2．三叉鏈表3．雙親鏈表4．線索鏈表對(duì)于一棵二叉樹,若采用順序存貯時(shí),當(dāng)它為完全二叉樹時(shí),比較方便,若為非完全二叉樹,將會(huì)浪費(fèi)大量存貯存貯單元。最壞的非完全二叉樹是全部只有右分支,設(shè)高度為K,則需占用2K-1個(gè)存貯單元,而實(shí)際只需k個(gè)存儲(chǔ)單元。因此，對(duì)于非完全二叉樹，宜采用下面的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。7/22/202342ADEBCFrootlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):1.二叉鏈表7/22/202343typedefstruct

BiTNode

{//結(jié)點(diǎn)結(jié)構(gòu)TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述如下:7/22/202344結(jié)論：若一個(gè)二叉樹含有n個(gè)結(jié)點(diǎn)，則它的二叉鏈表中必含有2n個(gè)指針域，其中必有n＋1個(gè)空的鏈域。此結(jié)論證明如下：證明：分支數(shù)目B=n-1，即非空的鏈域有n-1個(gè)，故空鏈域有2n-(n-1)=n+1個(gè)。二叉鏈表的建立 為了后面遍歷二叉樹方便，先介紹建立二叉鏈表的算法（假設(shè)datatype為char型）。 根據(jù)遍歷方法，可采用相應(yīng)的遞歸方法建立二叉樹，如教科書P131算法6.4采用先序遞歸建立二叉樹。

7/22/202345Status

CreateBiTree(BiTree&T)

{ch=getchar();

if(ch=='')T=NULL;

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);T->data=ch;//生成根結(jié)點(diǎn)

CreateBiTree(T->lchild);//構(gòu)造左子樹

CreateBiTree(T->rchild);//構(gòu)造右子樹

}

returnOK;}//CreateBiTree7/22/202346AB

C

D

ABCD上頁算法執(zhí)行過程舉例如下：ATBCD^^^^^7/22/202347下面討論用隊(duì)列（按層次進(jìn)隊(duì)出隊(duì)）實(shí)現(xiàn)二叉樹的建立。

假設(shè)二叉鏈表的數(shù)據(jù)類型描述如剛才所述，為建立二叉鏈表，用一個(gè)一維數(shù)組來模擬隊(duì)列，存放輸入的結(jié)點(diǎn)，但是，輸入結(jié)點(diǎn)時(shí)，必須按完全二叉樹形式，才能使結(jié)點(diǎn)間滿足性質(zhì)5，若為非完全二叉樹，則必須給定一些假想結(jié)點(diǎn)(虛結(jié)點(diǎn))，使之符合完全二叉樹形式。為此，我們?cè)谳斎虢Y(jié)點(diǎn)值時(shí)，存在的結(jié)點(diǎn)則輸入它對(duì)應(yīng)的字符，不存在的結(jié)點(diǎn)(虛結(jié)點(diǎn))，輸入逗號(hào)，最后以一個(gè)特殊符號(hào)“#”作為輸入的結(jié)束,表示建二叉鏈表已完成。建成的二叉鏈表可以由根指針root唯一確定。7/22/202348算法描述如下：#include<iostream.h>typedefcharDataType;typedefstructNode{DataTypedata;structNode*Lchild，*RChild;}BiTNode,*BiTree;bitree*create(){bitree*q[100];//定義q數(shù)組作為隊(duì)列存放二叉鏈表中結(jié)點(diǎn)，100為最大容量bitree*s;//二叉鏈表中的結(jié)點(diǎn)bitree*root;//二叉鏈表的根指針intfront=1,rear=0;//定義隊(duì)列的頭、尾指針基本思想：用一個(gè)隊(duì)列來存放所有結(jié)點(diǎn)（實(shí)結(jié)點(diǎn)或虛結(jié)點(diǎn)）。輸入所有結(jié)點(diǎn)，并將其進(jìn)隊(duì)，若是實(shí)結(jié)點(diǎn)，則生成該結(jié)點(diǎn)將其作為隊(duì)首結(jié)點(diǎn)的左或右孩子插入，若是虛結(jié)點(diǎn)，則以空指針進(jìn)隊(duì)。然后根據(jù)當(dāng)前隊(duì)尾判斷是否出隊(duì)，即根據(jù)性質(zhì)5，當(dāng)隊(duì)尾為奇數(shù)時(shí)，隊(duì)首的左右孩子已處理結(jié)束，應(yīng)該出隊(duì)。7/22/202349

charch;//結(jié)點(diǎn)的data域值root=NULL;ch=getchar();while(ch!='#')//輸入值為#號(hào),算法結(jié)束{s=NULL;if(ch!=',')//輸入數(shù)據(jù)不為逗號(hào),表示不為虛結(jié)點(diǎn),否則為虛結(jié)點(diǎn) {s=(bitree*)malloc(sizeof(BiTNode));s->data=ch; s->lchild=NULL;s->rchild=NULL;}rear++;q[rear]=s;//新結(jié)點(diǎn)或虛結(jié)點(diǎn)進(jìn)隊(duì)if(rear==1)root=s;else

{if((s!=NULL)&&(q[front]!=NULL))

{if(rear%2==0)q[front]->lchild=s;

//rear為偶數(shù),s為雙親左孩子 elseq[front]->rchild=s;}

}

//rear為奇數(shù),s為雙親右孩子if((rear!=1)&&(rear%2==1))front++;//出隊(duì)ch=getchar();}returnroot;}7/22/202350例如，對(duì)下圖左所示的二叉樹，建立的二叉鏈表如右圖所示。對(duì)左圖(a)所示的二叉樹，要用算法建成右圖所示的二叉樹鏈表，從鍵盤輸入的數(shù)據(jù)應(yīng)為：AB,,C,,,,D#↙其中#為輸入結(jié)束，↙為回車符。7/22/202351ADEBCFroot2．三叉鏈表parent

lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):7/22/202352

typedefstruct

TriTNode

{//結(jié)點(diǎn)結(jié)構(gòu)TElemTypedata;

structTriTNode*lchild,*rchild;//左右孩子指針

structTriTNode

*parent;//雙親指針

}TriTNode,*TriTree;parentlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述如下:7/22/2023530123456dataparent結(jié)點(diǎn)結(jié)構(gòu):3．雙親鏈表LRTagLRRRLData:數(shù)據(jù)Parent:指向雙親的指針LRTag:左右孩子標(biāo)志域7/22/202354

typedefstruct

BPTNode

{//結(jié)點(diǎn)結(jié)構(gòu)TElemTypedata;

int

*parent;//指向雙親的指針

charLRTag;//左、右孩子標(biāo)志域

}BPTNode

typedefstructBPTree{//樹結(jié)構(gòu)

BPTNodenodes[MAX_TREE_SIZE];

intnum_node;//結(jié)點(diǎn)數(shù)目

introot;//根結(jié)點(diǎn)的位置

}BPTree7/22/2023556.4二叉樹的遍歷7/22/202356一、問題的提出二、先左后右的遍歷算法三、算法的遞歸描述四、遍歷算法的非遞歸描述五、遍歷算法的應(yīng)用舉例7/22/202357

順著某一條搜索路徑巡訪二叉樹中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一次，而且僅被訪問一次。一、問題的提出“訪問”的含義可以很廣，如：輸出結(jié)點(diǎn)的信息等。7/22/202358

“遍歷”是任何類型均有的操作，對(duì)線性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)有兩個(gè)后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。7/22/202359對(duì)“二叉樹”而言，可以有三條搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。7/22/202360二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法7/22/202361

若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：7/22/202362

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹。中（根）序的遍歷算法：7/22/202363

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)。后（根）序的遍歷算法：7/22/202364

最早提出遍歷問題是對(duì)存儲(chǔ)在計(jì)算機(jī)中的表達(dá)式求值。例如：（a+b*c）-d/e。該表達(dá)式用二叉樹表示如下圖所示。當(dāng)對(duì)此二叉樹進(jìn)行先序、中序、后序遍歷時(shí)，便可獲得表達(dá)式的前綴、中綴、后綴書寫形式：前綴：-+a*bc/de中綴：a+b*c-d/e后綴：abc*+de/-

其中中綴形式是算術(shù)表達(dá)式的通常形式，只是沒有括號(hào)。前綴表達(dá)式稱為波蘭表達(dá)式。算術(shù)表達(dá)式的后綴表達(dá)式被稱作逆波蘭表達(dá)式。在計(jì)算機(jī)內(nèi)，使用后綴表達(dá)式易于求值。

圖算術(shù)式的二叉樹表示

7/22/202365三、算法的遞歸描述voidPreorder(BiTreeT,

void(*visit)(TElemType&e)){//

先序遍歷二叉樹

if(T){

visit(T->data);//訪問結(jié)點(diǎn)

Preorder(T->lchild,visit);//遍歷左子樹

Preorder(T->rchild,visit);//遍歷右子樹

}}7/22/202366voidInorder(BiTreeT,

void(*visit)(TElemType&e)){//

中序遍歷二叉樹

if(T){

Ineorder(T->lchild,visit);//遍歷左子樹

visit(T->data);//訪問結(jié)點(diǎn)

Ineorder(T->rchild,visit);//遍歷右子樹

}}7/22/202367voidPostorder(BiTreeT,

void(*visit)(TElemType&e)){//

后序遍歷二叉樹

if(T){

Postorder(T->lchild,visit);//遍歷左子樹

Postorder(T->rchild,visit);//遍歷右子樹visit(T->data);//訪問結(jié)點(diǎn)

}}7/22/202368四、遍歷算法的非遞歸描述利用一個(gè)一維數(shù)組作為棧，來存儲(chǔ)二叉鏈表中結(jié)點(diǎn)。算法思想為： 從二叉樹根結(jié)點(diǎn)開始，沿左子樹一直走到末端(左孩子為空)為止，在走的過程中，訪問所遇結(jié)點(diǎn)，并依次把所遇結(jié)點(diǎn)進(jìn)棧，當(dāng)左子樹為空時(shí)，從棧頂退出某結(jié)點(diǎn)，并將指針指向該結(jié)點(diǎn)的右孩子。如此重復(fù)，直到棧為空或指針為空止。1.先序遍歷二叉樹的非遞歸算法7/22/202369算法如下：voidpreorder1(bitree*root){bitree*p,*s[100];inttop=0;//top為棧頂指針p=root;while((p!=NULL)||(top>0)){while(p!=NULL){printf(“%c”,p->data);s[++top]=p;p=p->lchild;}p=s[top--];p=p->rchild;}}【算法】先序遍歷二叉樹的非遞歸算法7/22/202370圖中序遍歷二叉樹的非遞歸算法處理流程

2.中序遍歷二叉樹的非遞歸算法

利用一個(gè)一維數(shù)組作棧，來存貯二叉鏈表中結(jié)點(diǎn)。算法思想為：從二叉樹根結(jié)點(diǎn)開始，沿左子樹一直走到末端(左孩子為空)為止，在走的過程中，把依次遇到的結(jié)點(diǎn)進(jìn)棧,待左子樹為空時(shí),從棧中退出結(jié)點(diǎn)并訪問,然后再轉(zhuǎn)向它的右子樹。如此重復(fù)，直到?？栈蛑羔槥榭罩埂?/22/202371voidInOrder（BiTreeroot）/*中序遍歷二叉樹的非遞歸算法*/{InitStack(&S);p=root;while(p!=NULL||!IsEmpty(S)){if(p!=NULL)/*根指針進(jìn)棧，遍歷左子樹*/Push(&S,p);p=p->lchild;}else{/*根指針退棧，訪問根結(jié)點(diǎn)，遍歷右子樹*/Pop(&S,&p);Visit(p->data);p=p->rchild;}}}【算法(a)中序遍歷二叉樹的非遞歸算法(調(diào)用棧操作的函數(shù))】7/22/202372/*s［m］表示棧，top表示棧頂指針*/voidinorder(BiTreeroot)/*中序遍歷二叉樹，root為二叉樹的根結(jié)點(diǎn)*/{top=0;p=root;do{dowhile(p!=NULL){top=top+1;s［top］=p;p=p->lchild};/*遍歷左子樹*/if(top>=0){p=s［top］;top=top-1;Visit(p->data);/*訪問根結(jié)點(diǎn)printf(“%c”,p->data);*/p=p->rchild;}/*遍歷右子樹*/}}while(p!=NULL||top!=0)}【算法(b)中序遍歷二叉樹的非遞歸算法(直接實(shí)現(xiàn)棧操作)7/22/2023733.后序遍歷二叉樹的非遞歸算法利用棧來實(shí)現(xiàn)二叉樹的后序遍歷要比前序和中序遍歷復(fù)雜得多，在后序遍歷中，當(dāng)搜索指針指向某一個(gè)結(jié)點(diǎn)時(shí)，不能馬上進(jìn)行訪問，而先要遍歷左子樹，所以此結(jié)點(diǎn)應(yīng)先進(jìn)棧保存，當(dāng)遍歷完它的左子樹后，再次回到該結(jié)點(diǎn)，還不能訪問它，還需先遍歷其右子樹,所以該結(jié)點(diǎn)還必須再次進(jìn)棧，只有等它的右子樹遍歷完后，再次退棧時(shí)，才能訪問該結(jié)點(diǎn)。為了區(qū)分同一結(jié)點(diǎn)的兩次進(jìn)棧，引入一個(gè)棧次數(shù)的標(biāo)志，一個(gè)元素第一次進(jìn)棧標(biāo)志為0，第二次進(jìn)標(biāo)志為1，并將標(biāo)志存入另一個(gè)棧中，當(dāng)從標(biāo)志棧中退出的元素為1時(shí)，訪問結(jié)點(diǎn)。7/22/202374后序遍歷二叉樹的非遞歸算法如下：voidpostorder1(bitree*root){bitree*p,*s1[100];//s1棧存放樹中結(jié)點(diǎn)ints2[100],top=0,b;//s2棧存放進(jìn)棧標(biāo)志p=root;do{while(p!=NULL){s1[top]=p;s2[top++]=0;//第一次進(jìn)棧標(biāo)志為0p=p->lchild;}if(top>0) {b=s2[--top]; p=s1[top];7/22/202375

if(b==0) {s1[top]=p;s2[top++]=1;//第二次進(jìn)棧標(biāo)志為1

p=p->rchild;}else {printf(“%c”,p->data); p=NULL; } }}while((p!=NULL)||(top>0));;}【算法后序遍歷二叉樹的非遞歸算法(調(diào)用棧操作的函數(shù))】7/22/202376五、遍歷算法的應(yīng)用舉例1、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)(先序遍歷)2、求二叉樹的深度(后序遍歷)3、復(fù)制二叉樹(后序遍歷)4、建立二叉樹的存儲(chǔ)結(jié)構(gòu)7/22/2023771、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)算法基本思想:

先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問結(jié)點(diǎn)”的操作改為：若是葉子，則計(jì)數(shù)器增1。7/22/202378void

CountLeaf

(BiTreeT,int&count){

if(T){

if((!T->lchild)&&(!T->rchild))count++;//對(duì)葉子結(jié)點(diǎn)計(jì)數(shù)

CountLeaf(T->lchild,count);

CountLeaf(T->rchild,count);}//if}//CountLeaf7/22/2023792、求二叉樹的深度(后序遍歷)算法基本思想:從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點(diǎn)”的操作為：求得左、右子樹深度的最大值，然后加1。

首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系。7/22/202380int

Depth(BiTreeT){//返回二叉樹的深度

if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);

depthval=1+(depthLeft>depthRight?depthLeft:depthRight);

}

returndepthval;}7/22/2023813、復(fù)制二叉樹其基本操作為：生成一個(gè)結(jié)點(diǎn)。根元素T左子樹右子樹根元素NEWT左子樹右子樹左子樹右子樹(后序遍歷)7/22/202382BiTNode

*GetTreeNode(TElemTypeitem,

BiTNode

*lptr,BiTNode*rptr){

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(1);

T->data=item;

T->lchild=lptr;T->rchild=rptr;

returnT;}

生成一個(gè)二叉樹的結(jié)點(diǎn)(其數(shù)據(jù)域?yàn)閕tem,左指針域?yàn)閘ptr,右指針域?yàn)閞ptr)7/22/202383BiTNode

*CopyTree(BiTNode*T){

if(!T)returnNULL;

if(T->lchild)

newlptr=CopyTree(T->lchild);//復(fù)制左子樹

elsenewlptr=NULL;

if(T->rchild)

newrptr=CopyTree(T->rchild);//復(fù)制右子樹

elsenewrptr=NULL;

newT=GetTreeNode(T->data,newlptr,newrptr);

returnnewT;}//CopyTree7/22/202384ABCDEFGHK^D^C^^B^H^^K^G^F^E^A例如：下列二叉樹的復(fù)制過程如下：newT7/22/2023854、建立二叉樹的存儲(chǔ)結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲(chǔ)結(jié)構(gòu)的建立算法7/22/2023

以字符串的形式根左子樹右子樹定義一棵二叉樹例如:ABCD以空白字符“”表示A(B(,C(,)),D(,))空樹只含一個(gè)根結(jié)點(diǎn)的二叉樹A以字符串“A”表示以下列字符串表示7/22/202387Status

CreateBiTree(BiTree&T)

{scanf(&ch);

if(ch=='')T=NULL;

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))

exit(OVERFLOW);T->data=ch;//生成根結(jié)點(diǎn)

CreateBiTree(T->lchild);//構(gòu)造左子樹

CreateBiTree(T->rchild);//構(gòu)造右子樹

}

returnOK;}//CreateBiTree7/22/202388AB

C

D

ABCD上頁算法執(zhí)行過程舉例如下：ATBCD^^^^^7/22/202389

按給定的表達(dá)式建相應(yīng)二叉樹

由先綴表示式建樹例如：已知表達(dá)式的先綴表示式

-×+abc/de

由原表達(dá)式建樹例如：已知表達(dá)式(a+b)×c–d/e7/22/202390對(duì)應(yīng)先綴表達(dá)式-×+abc/de的二叉樹abcde-×+/特點(diǎn)：

操作數(shù)為葉子結(jié)點(diǎn)

運(yùn)算符為分支結(jié)點(diǎn)7/22/202391scanf(&ch);if(In(ch,字母集))建葉子結(jié)點(diǎn);else{建根結(jié)點(diǎn);遞歸建左子樹;遞歸建右子樹;}由先綴表示式建樹的算法的基本操作：7/22/202392a+b(a+b)×c–d/ea+b×c分析表達(dá)式和二叉樹的關(guān)系:ab+abc×+abc×+(a+b)×cabcde-×+/7/22/202393基本操作:scanf(&ch);if(In(ch,字母集)){建葉子結(jié)點(diǎn);暫存;}elseif(In(ch,運(yùn)算符集)){和前一個(gè)運(yùn)算符比較優(yōu)先級(jí);若當(dāng)前的優(yōu)先級(jí)“高”，則暫存;否則建子樹;}7/22/202394voidCrtExptree(BiTree&T,charexp[]){InitStack(S);Push(S,#);InitStack(PTR);p=exp;ch=*p;

while(!(GetTop(S)==#&&ch==#)){if(!IN(ch,OP))CrtNode(t,ch);//建葉子結(jié)點(diǎn)并入棧else{}

if(ch!=

#){p++;ch=*p;}

}//whilePop(PTR,T);}//CrtExptree……7/22/202395switch(ch){case

(

:Push(S,ch);break;

case

)

:Pop(S,c);while(c!=(){CrtSubtree(t,c);//建二叉樹并入棧Pop(S,c)}

break;

defult:}//switch……7/22/202396while(!Gettop(S,c)&&(precede(c,ch))){

CrtSubtree(t,c);Pop(S,c);}if(ch!=

#)Push(S,ch);

break;7/22/202397建葉子結(jié)點(diǎn)的算法為：voidCrtNode(BiTree&T,charch){T=(BiTNode*)malloc(sizeof(BiTNode));T->data=char;T->lchild=T->rchild=NULL;

Push(PTR,T);}7/22/202398建子樹的算法為：voidCrtSubtree

(Bitree&T,charc){T=(BiTNode*)malloc(sizeof(BiTNode));T->data=c;Pop(PTR,rc);T->rchild=rc;Pop(PTR,lc);T->lchild=lc;

Push(PTR,T);}7/22/202399

僅知二叉樹的先序序列“abcdefg”

不能唯一確定一棵二叉樹，由二叉樹的先序和中序序列建樹

如果同時(shí)已知二叉樹的中序序列“cbdaegf”，則會(huì)如何？

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根7/22/2023100abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列7/22/2023101voidCrtBT(BiTree&T,charpre[],charino[],

intps,intis,intn){//已知pre[ps..ps+n-1]為二叉樹的先序序列，//ins[is..is+n-1]為二叉樹的中序序列，本算//法由此兩個(gè)序列構(gòu)造二叉鏈表

if(n==0)T=NULL;

else{k=Search(ino,pre[ps]);//在中序序列中查詢

if(k==-1)T=NULL;

else{}}//}//CrtBT……Ps為先序序列的起始位置,is為中序序列的起始位置,n為結(jié)點(diǎn)數(shù)7/22/2023102T=(BiTNode*)malloc(sizeof(BiTNode));T->data=pre[ps];if(k==is)T->Lchild=NULL;else

CrtBT(T->Lchild,pre[],ino[],ps+1,is,k-is);if(k=is+n-1)T->Rchild=NULL;else

CrtBT(T->Rchild,pre[],ino[],ps+1+(k-is),k+1,n-(k-is)-1);7/22/20231036.5

線索二叉樹

何謂線索二叉樹？線索鏈表的遍歷算法如何建立線索鏈表？7/22/2023104一、何謂線索二叉樹？遍歷二叉樹的結(jié)果是，求得結(jié)點(diǎn)的一個(gè)線性序列。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA7/22/2023105指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”與其相應(yīng)的二叉樹，稱作“線索二叉樹”包含“線索”的存儲(chǔ)結(jié)構(gòu)，稱作“線索鏈表”ABCDEFGHK^D^

C^^B

E^7/22/2023106對(duì)線索鏈表中結(jié)點(diǎn)的約定：在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域，并作如下規(guī)定：若該結(jié)點(diǎn)的左子樹不空，則Lchild域的指針指向其左子樹，且左標(biāo)志域的值為“指針Link”；否則，Lchild域的指針指向其“前驅(qū)”，且左標(biāo)志的值為“線索Thread”

。7/22/2023107若該結(jié)點(diǎn)的右子樹不空，則rchild域的指針指向其右子樹，且右標(biāo)志域的值為“指針Link”；否則，rchild域的指針指向其“后繼”，且右標(biāo)志的值為“線索Thread”。

如此定義的二叉樹的存儲(chǔ)結(jié)構(gòu)稱作“線索鏈表”。7/22/2023108typedefstruct

BiThrNod{

TElemTypedata;

structBiThrNode*lchild,*rchild;//左右指針

PointerThrLTag,RTag;//左右標(biāo)志}BiThrNode,*BiThrTree;線索鏈表的類型描述：

typedef

enum{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索7/22/2023109二、線索鏈表的遍歷算法:

for(p=

firstNode(T);p;p=Succ(p))Visit(p);由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡(jiǎn)化了遍歷的算法。7/22/2023110在線索二叉樹中找前驅(qū)、后繼結(jié)點(diǎn)

1）在中序線索樹中找前驅(qū)結(jié)點(diǎn)根據(jù)線索二叉樹的基本概念和存儲(chǔ)結(jié)構(gòu)可知，對(duì)于結(jié)點(diǎn)p，當(dāng)p->Ltag=1時(shí)，p->LChild指向p的前驅(qū)。當(dāng)p->Ltag=0時(shí)，p->LChild指向p的左孩子。由中序遍歷的規(guī)律可知，作為根p的前驅(qū)結(jié)點(diǎn)，它是中序遍歷p的左子樹時(shí)訪問的最后一個(gè)結(jié)點(diǎn)，即左子樹的最右下端結(jié)點(diǎn)。其查找算法如下：7/22/2023111voidInPre(BiTNode*p,BiTNode*pre)/*在中序線索二叉樹中查找p的中序前驅(qū),并用pre指針返回結(jié)果*/{if(p->Ltag==1)pre=p->LChild;/*直接利用線索*/else{/*在p的左子樹中查找“最右下端”結(jié)點(diǎn)*/for(q=p->LChild;q->Rtag==0;q=q->RChild);pre=q;}}【在中序線索樹中找結(jié)點(diǎn)前驅(qū)】7/22/2023112

2）在中序線索樹中找結(jié)點(diǎn)后繼對(duì)于結(jié)點(diǎn)p，若要找其后繼結(jié)點(diǎn)，當(dāng)p->Rtag=1時(shí)，p->RChild即為p的后繼結(jié)點(diǎn)；當(dāng)p->Rtag=0時(shí)，說明p有右子樹，此時(shí)p的中序后繼結(jié)點(diǎn)即為其右子樹的最左下端的結(jié)點(diǎn)。其查找算法如下：7/22/2023113voidInSucc(BiTNode*p,BiTNode*succ)/*在中序線索二叉樹中查找p的中序后繼結(jié)點(diǎn)，并用succ指針返回結(jié)果*/{if(p->Rtag==1)succ=p->RChild;/*直接利用線索*/else{/*在p的右子樹中查找最左下端結(jié)點(diǎn)*/for(q=p->RChild;q->Ltag==0;q=q->LChild);succ=q;}}【在中序線索樹中找結(jié)點(diǎn)后繼】7/22/2023114

3)在先序線索樹中找結(jié)點(diǎn)的后繼(比較容易)根據(jù)先序線索樹的遍歷過程可知:

①若結(jié)點(diǎn)p存在左子樹，則p的左孩子結(jié)點(diǎn)即為p的后繼；

②若結(jié)點(diǎn)p沒有左子樹，但有右子樹，則p的右孩子結(jié)點(diǎn)即為p的后繼；③若結(jié)點(diǎn)p既沒有左子樹，也沒有右子樹，則結(jié)點(diǎn)p的RChild指針域所指的結(jié)點(diǎn)即為p的后繼。用語句表示則為：

if(p->Ltag==0)succ=p->LChildelsesucc=p->RChild7/22/2023115

4)在先序線索樹中找結(jié)點(diǎn)的前驅(qū)(比較困難)

①若結(jié)點(diǎn)p是二叉樹的根，則p的前驅(qū)為空；

②若p是其雙親的左孩子，或者p是其雙親的右孩子并且其雙親無左孩子，則p的前驅(qū)是p的雙親結(jié)點(diǎn)；③若p是雙親的右孩子且雙親有左孩子，則p的前驅(qū)是其雙親的左子樹中按先序遍歷時(shí)最后訪問的那個(gè)結(jié)點(diǎn)。

7/22/20231165)在后序線索樹中查找結(jié)點(diǎn)p的前驅(qū)(很方便)①若結(jié)點(diǎn)p存在右子樹，則p的右孩子結(jié)點(diǎn)即為p的前驅(qū)；

②若結(jié)點(diǎn)p沒有右子樹，但有左子樹，則p的左孩子結(jié)點(diǎn)即為p的前驅(qū)；③若結(jié)點(diǎn)p既沒有左子樹，也沒有右子樹，則結(jié)點(diǎn)p的RLhild指針域所指的結(jié)點(diǎn)即為p的前驅(qū)。用語句表示則為：if(p->Rtag==0)pre=p->RChildelsepre=p->LChild

7/22/20231176)在后序線索樹中查找結(jié)點(diǎn)p的后繼(較復(fù)雜)①若結(jié)點(diǎn)p是二叉樹的根，則p的后繼為空；

②若p是其雙親的右孩子，或者p是其雙親的左孩子并且其雙親無右孩子，則p的后繼是p的雙親結(jié)點(diǎn)；③若p是雙親的左孩子且雙親有右孩子，則p的后繼是其雙親的右子樹中按后序遍歷時(shí)最先訪問的那個(gè)結(jié)點(diǎn)。7/22/2023118例如:對(duì)中序線索化鏈表的遍歷算法

※中序遍歷的第一個(gè)結(jié)點(diǎn)？

※在中序線索化鏈表中結(jié)點(diǎn)的后繼？左子樹上處于“最左下”（設(shè)有左子樹）的結(jié)點(diǎn)。若無右子樹，則為后繼線索所指結(jié)點(diǎn)；否則為對(duì)其右子樹進(jìn)行中序遍歷時(shí)訪問的第一個(gè)結(jié)點(diǎn)。7/22/2023119voidInOrderTraverse_Thr(BiThrTreeT,

void(*Visit)(TElemTypee)){p=T->lchild;//p指向根結(jié)點(diǎn)

while(p!=T){

//空樹或遍歷結(jié)束時(shí)，p==Twhile(p->LTag==Link)p=p->lchild;//第一個(gè)結(jié)點(diǎn)if(!Visit(p->data))returnERROR;while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);//訪問后繼結(jié)點(diǎn)

}p=p->rchild;//p進(jìn)至其右子樹根

}}//InOrderTraverse_Thr7/22/2023120在中序遍歷過程中修改結(jié)點(diǎn)的左、右指針域，以保存當(dāng)前訪問結(jié)點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷過程中，附設(shè)指針pre,并始終保持指針pre指向當(dāng)前訪問的、指針p所指結(jié)點(diǎn)的前驅(qū)。三、如何建立線索鏈表？7/22/2023121void

InThreading(BiThrTreep)

{

if(p){//對(duì)以p為根的非空二叉樹進(jìn)行線索化

InThreading(p->lchild);

//左子樹線索化

if(!p->lchild)//建前驅(qū)線索

{p->LTag=Thread;p->lchild=pre;}

if(!pre->rchild)//建后繼線索

{pre->RTag=Thread;pre->rchild=p;}

pre=p;//保持pre指向p的前驅(qū)

InThreading(p->rchild);

//右子樹線索化

}//if}//InThreading7/22/2023122StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//構(gòu)建中序線索鏈表if(!(Thrt=(BiThrTree)malloc(

sizeof(BiThrNode))))

exit(OVERFLOW);

Thrt->LTag=Link;Thrt->RTag=Thread;Thrt->rchild=Thrt;

//添加頭結(jié)點(diǎn)returnOK;}//InOrderThreading

……7/22/2023123if(!T)

Thrt->lchild=Thrt;

else{Thrt->lchild=T;

pre=Thrt;InThreading(T);

pre->rchild=Thrt;//處理最后一個(gè)結(jié)點(diǎn)pre->RTag=Thread;

Thrt->rchild=pre;

}7/22/2023124

6.6樹和森林的表示方法7/22/2023125樹的三種存儲(chǔ)結(jié)構(gòu)一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法7/22/2023126ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=6dataparent一、雙親表示法:7/22/2023127

typedefstructPTNode{Elemdata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點(diǎn)結(jié)構(gòu):C語言的類型描述:7/22/2023128typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}PTree;樹結(jié)構(gòu):7/22/2023129ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=6datafirstchild123456二、孩子鏈表表示法:-10002247/22/2023130typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子結(jié)點(diǎn)結(jié)構(gòu):

childnextC語言的類型描述:7/22/2023131

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針

}CTBox;雙親結(jié)點(diǎn)結(jié)構(gòu)

datafirstchild7/22/2023132typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置

}CTree;樹結(jié)構(gòu):7/22/2023133ABCDEFGABCEDFGrootABCEDFG

三、樹的二叉鏈表(孩子-兄弟）存儲(chǔ)表示法7/22/2023134typedefstructCSNode{Elemdata;

structCSNode

*firstchild,*