哈工大數(shù)據(jù)結(jié)構(gòu)6

第6章樹和二叉樹1樹是一種重要的非線性結(jié)構(gòu)。樹是以分支關(guān)系定義的層次結(jié)構(gòu)，其中以二叉樹最為常用。樹型結(jié)構(gòu)在計算機中有廣泛應(yīng)用：在微機操作系統(tǒng)中，文件和文件夾以樹形結(jié)構(gòu)存儲。在編譯系統(tǒng)中，可以用樹來表示源程序的語法結(jié)構(gòu)。在數(shù)據(jù)庫系統(tǒng)中，樹型結(jié)構(gòu)是信息的重要組織形式。26.1樹的定義和基本術(shù)語6.2二叉樹6.3遍歷二叉樹6.4恢復(fù)二叉樹6.7樹和森林6.8哈夫曼樹及其應(yīng)用6.5線索二叉樹6.6二叉樹的基本運算及其應(yīng)用36.1樹的定義和基本術(shù)語4數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

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

R：1.樹的定義5

基本操作：查找類

插入類刪除類6

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

Parent(T,cur_e)//求當(dāng)前結(jié)點的雙親結(jié)點LeftChild(T,cur_e)//求當(dāng)前結(jié)點的最左孩子RightSibling(T,cur_e)//求當(dāng)前結(jié)點的右兄弟TreeEmpty(T)//判定樹是否為空樹

TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷7InitTree(&T)

//初始化置空樹

插入類：CreateTree(&T,definition)

//按定義構(gòu)造樹Assign(T,cur_e,value)

//給當(dāng)前結(jié)點賦值InsertChild(&T,&p,i,c)

//將以c為根的樹插入為結(jié)點p的第i棵子樹8

ClearTree(&T)

//將樹清空

刪除類：DestroyTree(&T)

//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)

//刪除結(jié)點p的第i棵子樹9ABCDEFGHIJMKLA(

B(E,F(K,L)),

C(G),D(H,I,J(M)))T1T3T2樹根例:10

樹的特點：

在非空樹中：樹中至少有一個結(jié)點——根。樹中各子樹是互不相交的集合。

樹的定義是遞歸的，即在樹的定義中又用到樹的概念，正好反映了樹的固有特性。

11A只有根結(jié)點的樹ABCDEFGHIJKLM有子樹的樹根子樹12(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：子樹之間存在確定的次序關(guān)系。無序樹：子樹之間不存在確定的次序關(guān)系。13對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點14~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素(無前驅(qū))

根結(jié)點(無前驅(qū))最后一個數(shù)據(jù)元素(無后繼)多個葉子結(jié)點(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)15結(jié)點(node)——表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支。結(jié)點的度(degree)——結(jié)點擁有的子樹個數(shù)。葉子(leaf)——度為0的結(jié)點。孩子(child)——結(jié)點子樹的根稱為該結(jié)點的孩子。雙親(parents)——孩子結(jié)點的上層結(jié)點叫該結(jié)點的雙親或父結(jié)點。兄弟(sibling)——同一雙親的孩子。樹的度——一棵樹中各結(jié)點的度的最大值稱為該樹的度。2.樹的基本術(shù)語16結(jié)點的層次(level)——根結(jié)點的層數(shù)為1，其余結(jié)點的層數(shù)等于它雙親結(jié)點的層數(shù)加1。樹的深度(depth)——樹中結(jié)點的最大層次數(shù)。森林(forest)——m(m0)棵互不相交的樹的集合。(從根到結(jié)點的)路徑——由從根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成。ABCDEFGHIJMKL17任何一棵非空樹是一個二元組：

Tree=（root，F(xiàn)）其中：root被稱為根結(jié)點。

F被稱為子樹森林。森林：是m（m≥0）棵互不相交的樹的集合。ArootBCDEFGHIJMKLF18任何一棵樹，只要刪去根結(jié)點就成了森林。如圖：(a)

樹

(b)

移去根結(jié)點后成為森林19ABCDEFGHIJKLM結(jié)點A的度：3結(jié)點B的度：2結(jié)點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點A的孩子：B，C，D結(jié)點B的孩子：E，F(xiàn)結(jié)點I的雙親：D結(jié)點L的雙親：E結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟樹的度：3結(jié)點A的層次：1結(jié)點M的層次：4樹的深度：4結(jié)點F，G為堂兄弟結(jié)點A是結(jié)點F，G的祖先20bacghdefij樹型表示樹的表示：21凹入表表示abdeijfcgh22嵌套集合表示嵌套括號表示ijdfghabcea(b(d,e(i,j),c(g,h)

)

)236.2二叉樹241.二叉樹的定義

二叉樹是有n（n>=0）個結(jié)點的有限集合。（1）該集合或者為空（n=0）；（2）該集合或者只有一個根結(jié)點；（3）該集合或者由一個根結(jié)點及兩個不相交的分別稱為左子樹和右子樹組成的非空樹；（4）左子樹和右子樹同樣又都是二叉樹。二叉樹的定義是遞歸的：在一棵非空的二叉樹中，每個結(jié)點至多只有兩棵子樹，分別稱為左子樹和右子樹，左子樹和右子樹同樣又都是二叉樹。二叉樹是有序樹：二叉樹的左右子樹的次序不能交換。25ABCDEFGHK根結(jié)點左子樹右子樹26二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹27

二叉樹的基本操作：查找類插入類刪除類28

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());29

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);30ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);31二叉樹的主要基本操作：

（1）CreateBT（）：

創(chuàng)建一棵二叉樹。

（2）ShowTree(BT*T)：按凹入法顯示二叉樹。（3）Preorder(BT*T)：按先序（根、左、右）遍歷二叉樹上所有結(jié)點。（4）Inorder(BT*T)：按中序（左、根、右）遍歷二叉樹上所有結(jié)點。（5）Postorder(BT*T)：按后序（左、右、根）遍歷二叉樹上所有結(jié)點。32（6）Levelorder(BT*T)：按層次遍歷二叉樹上所有結(jié)點。（7）Leafnum(BT*T)：

求二叉樹葉子結(jié)點總數(shù)。（8）TreeDepth(BT*T)：求二叉樹的深度。332.二叉樹的性質(zhì)性質(zhì)1：一棵非空二叉樹的第i層上最多有2i–1個結(jié)點（i≥1）。證明：用歸納法證明之

i=1時，只有一個根結(jié)點，

成立假設(shè)對所有j(1j<i)命題成立，即第j層上至多有個

結(jié)點。那么，第i-1層至多有個結(jié)點。

須證明

j=i時命題也成立。因為二叉樹每個結(jié)點的度至多為2

第i層上最大結(jié)點數(shù)是第i-1層的2倍，即

故命題得證。34性質(zhì)2：

深度為k的二叉樹中，最多具有2k-1個結(jié)點。證明：根據(jù)性質(zhì)1，當(dāng)深度為k的二叉樹每一層都達到最多結(jié)點時，它的和最大，即：35兩類特殊的二叉樹：滿二叉樹：定義：一棵深度為k且有2k–1個結(jié)點的二叉樹稱為滿二叉樹。特點：滿二叉樹每一層上的結(jié)點都具有最大的結(jié)點數(shù)。123114589121367101415深度為k=4的滿二叉樹36完全二叉樹：定義：深度為k，有

n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點

都與深度為

k的滿二叉樹中編號從

1

至

n的結(jié)點一一對

應(yīng)時，稱為完全二叉樹。特點：葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)。對任一結(jié)點，若其右分支下子孫的最大層次為L，則其左分

支下子孫的最大層次必為

L或

L+1完全二叉樹123114589126710371234567123456特點：完全二叉樹除最后一層外，其余各層都是滿的；并且最后一層或者為滿，或者僅在右邊缺少連續(xù)若干個結(jié)點。38性質(zhì)3：不大于x的最大整數(shù)證明：設(shè)完全二叉樹的深度為k，結(jié)點數(shù)為n，

由性質(zhì)2和完全二叉樹的定義可知：2k-1-1<n2k-1

即2k-1

n

<2k兩邊取對數(shù)有：

k-1log2n

<k

對k取整數(shù)：

k=log2n+139性質(zhì)4：如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號，

則對任一結(jié)點

i(1in)，有：(1)若i=1，則序號為

i的結(jié)點是根結(jié)點。

若i>1,則序號為i的結(jié)點的父結(jié)點的序號為i/2。(2)若2i<=n，則序號為i的結(jié)點的左孩子結(jié)點的序號為2i。

若2i>n，則序號為i的結(jié)點無左孩子。(3)若2i+1<=n，則序號為i的結(jié)點的右孩子結(jié)點的序號為

2i+1

若2i+1>n，則序號為i的結(jié)點無右孩子。40性質(zhì)5：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為

n0，度為

2

的

結(jié)點數(shù)為

n2，則

n0=n2+1。證明：n1為二叉樹

T中度為

1

的結(jié)點數(shù)因為：二叉樹中所有結(jié)點的度均小于或等于2所以：其結(jié)點總數(shù)n=n0+n1+n2

又二叉樹中，除根結(jié)點外，其余結(jié)點都只有一個分支進入設(shè)B為分支總數(shù)，則

n=B+1

又：分支由度為1和度為2的結(jié)點射出，

B=n1+2n2

于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+1413.二叉樹的存儲結(jié)構(gòu)(1)

順序存儲結(jié)構(gòu)一維數(shù)組存儲法：實現(xiàn)：按完全二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素。特點：結(jié)點間關(guān)系蘊含在其存儲位置中（i的左子2i，右子2i+1）。abcdefgabcde0000fg

123456789101142特點：浪費空間，適于存滿二叉樹和完全二叉樹。aceda0c000d0000

123456789101112131400e43無須按完全二叉樹的結(jié)點層次編號，依次按編號存放二叉樹中的數(shù)據(jù)元素即可。結(jié)點數(shù)據(jù)，左子編號，右子編號均要存儲。故可采用長度為n的結(jié)構(gòu)數(shù)組存放。n為結(jié)點個數(shù)。結(jié)構(gòu)數(shù)組相當(dāng)于一個二維構(gòu)造,第一維是結(jié)構(gòu)數(shù)組元素,每個元素是一個結(jié)構(gòu)變量,第二維是結(jié)構(gòu)成員。

abcdefg0123456Data[0]Lno[1]Rno[2][0]a12[1]b34[2]c-1-1[3]d-1-1[4]e56[5]f-1-1[6]g-1-1二維數(shù)組存儲法：44順序存儲結(jié)構(gòu)小結(jié)：滿二叉樹或完全二叉樹可采用一維數(shù)組；結(jié)點少，層數(shù)高可采用二維數(shù)組；查找方便，找孩子結(jié)點及父結(jié)點均方便；缺點：空間擴充不便；插入和刪除須大量移動數(shù)據(jù)。45二叉鏈表：結(jié)點組成：lchilddatarchildABCDEFG

AB

C

D

E

F

G^^^^^^^^其中：data為數(shù)據(jù)域；

lchild為左指針域，放左子樹的地址；

rchild為右指針域，放右子樹的地址；BT：名字，根，入口(2)

鏈式存儲結(jié)構(gòu)46

二叉鏈表的定義：typedefstructnode{datatypedata;structnode*lchild,*rchild;}BT;47三叉鏈表：三叉鏈表的定義：typedefstructnode{datatypedata;structnode*lchild,*rchild,*parent;}TT;lchilddata

parent

rchildABCDEFG

A

B

C

D

E

F

G^^^^^^^^^結(jié)點組成：48三叉鏈表的靜態(tài)結(jié)構(gòu)：ABCDFErootdata

parent

leftChildrightChild012345A

-11-1B023C1

-1-1D145E3-1-1F3-1-1496.3遍歷二叉樹501.問題的提出

順著某一條搜索路徑巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。訪問的含義可以很廣，如：輸出結(jié)點的信息等。

遍歷是任何類型均有的操作。對線性結(jié)構(gòu)而言，只有一條搜索路徑(因為每個結(jié)點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結(jié)構(gòu)，每個結(jié)點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。51對二叉樹而言，可以有三條搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。52先序（根）的遍歷算法中序（根）的遍歷算法后序（根）的遍歷算法2.先左后右遍歷二叉樹的算法53(1)先序（根）遍歷（DLR）先序遍歷也稱為先根遍歷。其遞歸過程為：若二叉樹為空，則遍歷結(jié)束，返回。否則：（1）訪問根結(jié)點；（2）先序遍歷根結(jié)點的左子樹；（3）先序遍歷根結(jié)點的右子樹。3.遍歷二叉樹的遞歸算法54voidPreorder(BT*T) //先序遍歷T所指向的二叉樹{if(T==NULL)return; //本函數(shù)調(diào)用結(jié)束

{printf(T->data); //輸出結(jié)點的數(shù)據(jù)域

Preorder(T->lchild); //先序遞歸遍歷左子樹

Preorder(T->rchild); //先序遞歸遍歷右子樹

}//本函數(shù)調(diào)用結(jié)束}typedefstructnode{datatypedata;structnode*lchild,*rchild;}BT;算法描述：55ADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC

先序遍歷:56voidpreorder(BT*T){if(T==NULL)return;{printf("%d\t",T->data);preorder(T->lchild);preorder(T->rchild);}}主程序Pre(T)返回返回pre(TR);返回返回pre(TR);ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDC57(2)中序（根）遍歷（LDR）中序遍歷也稱為中根遍歷。其遞歸過程為：若二叉樹為空，則遍歷結(jié)束，返回。否則：（1）中序遍歷根結(jié)點的左子樹；（2）訪問根結(jié)點；（3）中序遍歷根結(jié)點的右子樹。58算法描述：typedefstructnode{datatypedata;structnode*lchild,*rchild;}BT;voidInorder(BT*T) //中序遍歷T所指向的二叉樹{if(T

==NULL)return;

//本函數(shù)調(diào)用結(jié)束

{Inorder(T->lchild);

//中序遞歸遍歷左子樹

printf(T->data);

//輸出結(jié)點的數(shù)據(jù)域

Inorder(T->rchild);//中序遞歸遍歷右子樹

}//本函數(shù)調(diào)用結(jié)束}59ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC

中序遍歷:60(3)后序（根）遍歷（LRD）后序遍歷也稱為后根遍歷。其遞歸過程為：若二叉樹為空，則遍歷結(jié)束，返回。否則：（1）后序遍歷根結(jié)點的左子樹；（2）后序遍歷根結(jié)點的右子樹。（3）訪問根結(jié)點；61算法描述：typedefstructnode{datatypedata;structnode*lchild,*rchild;}BT;voidPostorder(BT*T)//后序遍歷T所指向的二叉樹{if(T

==NULL)return; //本函數(shù)調(diào)用結(jié)束

{Postorder(T->lchild); //后序遞歸遍歷左子樹

Postorder(T->rchild); //后序遞歸遍歷右子樹

printf(T->data);//輸出結(jié)點的數(shù)據(jù)域

}//本函數(shù)調(diào)用結(jié)束}62ADBC

LRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA

后序遍歷:B63（1）先序遍歷的非遞歸算法*提高運算效率基于棧先序遍歷的非遞歸算法：引入棧保存每個結(jié)點的右指針?biāo)惴ǎ?）訪問結(jié)點。2）結(jié)點的右指針入棧。3）若結(jié)點的左指針不空，遍歷左子樹。4）右指針出棧。5）若結(jié)點的右指針不空，遍歷右子樹。4.遍歷二叉樹的非遞歸算法64（2）中序遍歷的非遞歸算法基于棧中序遍歷的非遞歸算法：引入棧保存每個結(jié)點及右指針，由于知道結(jié)點的指針便可知結(jié)點和其右指針，故只須結(jié)點的指針入棧。算法：1）結(jié)點右指針入棧。2）若結(jié)點的左指針不空，遍歷左子樹。3）指針出棧。4）訪問結(jié)點，若結(jié)點的右指針不空，遍歷右子樹。65算法實現(xiàn)：voidinorderse(BT*bt){inti=0;

//棧的初始化BT*p,*s[M];//保存每個結(jié)點的指針的棧

p=bt;do{while(p!=NULL){s[i++]=p;//結(jié)點的指針入棧

p=p->lchild;//進入左子樹}//左子樹為空，退出

if(i>0)//如果棧不空{(diào)p=s[--i];//結(jié)點的指針出棧printf(“%d\t”,p->data);//訪問出棧的結(jié)點p=p->rchild;}}while(i>0||p!=NULL);//右子樹為空同時?？?，結(jié)束循環(huán)}66非遞歸算法棧操作圖ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)P=nullABCDEFGiP->AP->B訪問：C(4)67pABCDEFGiP->A訪問：CB(5)ABCDEFGiP->AP->D訪問：CBp(6)ABCDEFGiP->AP->DP->E訪問：CBp(7)ABCDEFGiP->AP->D訪問：CBEp(8)68ABCDEFGiP->AP->DP->G訪問：CBEP=NULL(9)ABCDEFGiP->A訪問：CBEGDp(11)ABCDEFGiP->AP->F訪問：CBEGDp(12)ABCDEFGiP->AP->D訪問：CBEGp(10)69ABCDEFGiP->A訪問：CBEGDFp=NULL(13)ABCDEFGi訪問：CBEGDFAp(14)i訪問：CBEGDFAp=NULLABCDEFG(15)705.層次遍歷二叉樹的算法

按照自上而下（從根結(jié)點開始），從左到右的順序逐層訪問二叉樹上的所有結(jié)點，稱為按層次遍歷。按層次遍歷時，當(dāng)一層結(jié)點訪問完后，接著訪問下一層的結(jié)點，先遇到的結(jié)點先訪問，這與隊列的操作原則是一致的。在層次遍歷時，可設(shè)置一個數(shù)組來模擬隊列，用于保存被訪問結(jié)點的子結(jié)點的地址。遍歷從二叉樹的根結(jié)點開始，首先將根結(jié)點指針入隊列，然后從隊頭取出一個元素，每取一個元素，執(zhí)行下面兩個操作：（1）訪問該元素所指結(jié)點；（2）若該元素所指結(jié)點的左、右孩子結(jié)點非空，則將該元素所指結(jié)點的左孩子指針和右孩子指針依次入隊。此過程不斷進行，直到隊空為止。71在層次遍歷算法中，以二叉鏈表方式存儲，lchild和rchild分別是被訪問結(jié)點的左、右指針。一維數(shù)組q[MAXLEN]用以實現(xiàn)隊列。72算法描述：

voidLevelorder(BT*T)//按層次遍歷二叉樹BT,T為指向根結(jié)點的指針{inti,j;BT*q[MAXLEN],*p;//q為指針數(shù)組用以模擬隊列,每個元素均為指向BT類型的指針,用來存放結(jié)點地址

p=T;if(p!=NULL) //若二叉樹非空，則根結(jié)點地址入隊

{i=1;q[i]=p;j=2;}//i指向?qū)︻^，j指向?qū)ξ瞱hile(i!=j)//當(dāng)隊列不為空時執(zhí)行循環(huán){p=q[i];printf(p->data);//訪問隊首結(jié)點的數(shù)據(jù)域

if(p->lchild!=NULL){q[j]=p->lchild;j++;}//將出隊結(jié)點的左孩子的地址入隊if(p->rchild!=NULL){q[j]=p->rchild;j++;}//將出隊結(jié)點的右孩子的地址入隊i++;

}}73層次遍歷:ABCDEHIFGK層次遍歷的序列:ABCDEFGHIK74例：

有二叉樹如圖所示，求它的先根遍歷、中根遍歷、后根遍歷和層次遍歷的輸出序列。ABCIKFEDHG先根遍歷的序列：

ABDGEHCFIK中根遍歷的序列：

DGBHEAFKIC后根遍歷的序列：

GDHEBKIFCA層次遍歷的序列：

ABCDEFGHIK75例：設(shè)表達式A–B*（C+D）+E/（F+G）的二叉樹表示如圖所示。試寫出它的先根遍歷、中根遍歷和后根遍歷輸出序列。A*/EF++BDC-+G先根遍歷結(jié)果（即前綴表達式）：

+–A*B+CD/E+FG中根遍歷結(jié)果：

A–B*C+D+E/F+G后根遍歷結(jié)果（即后綴表達式）：

ABCD+*–EFG+/+766.4恢復(fù)二叉樹77根據(jù)已知的先根序列、中根序列、后根序列得到一棵二叉樹稱為恢復(fù)二叉樹。問題的由來：在數(shù)據(jù)量很大的結(jié)構(gòu)中，如在繪圖軟件中，如何存儲一個用樹表示的圖形結(jié)構(gòu)？處理方法：

對于鏈表結(jié)構(gòu)的圖形結(jié)構(gòu)：

（1）把每個結(jié)點去掉指針項，將結(jié)點的數(shù)據(jù)按中序存儲于數(shù)組中得到中序結(jié)點表。

（2）把每個結(jié)點去掉指針項，將結(jié)點的數(shù)據(jù)按先序或后序存儲于數(shù)組中得到序表。圖形結(jié)構(gòu)調(diào)入內(nèi)存時要恢復(fù)二叉樹。有二種方法：

（1）根據(jù)中序數(shù)組、先序數(shù)組恢復(fù)二叉樹。

（2）根據(jù)中序數(shù)組、后序數(shù)組恢復(fù)二叉樹。781.由先根、中根恢復(fù)二叉樹步驟：（1）根據(jù)先根序列的第一個元素確定根結(jié)點；在中根序列中找到該根結(jié)點，

確定該根結(jié)點的左、右子樹的中根序列；再在先根序列中確定此左、右子樹的先根序列；（2）根據(jù)左、右子樹的先根序列分別找出左子樹和右子樹的根結(jié)點，并把左、右子樹的根結(jié)點連到父結(jié)點上去；（3）再對左、右子樹按此方法找出根結(jié)點和左、右子樹；

如此遞歸下去，當(dāng)取盡先根序列中的結(jié)點時，便恢復(fù)了一棵二叉樹。79例：由下列先根序列和中根序列恢復(fù)二叉樹。先根序列：ACBRSEDFMLK中根序列：RBSCEAFDLKM80例：前序：ACBRSEDFMLK中序：RBSCEAFDLKM前序：

A

CBRSEDFMLK中序：

RBSCE

A

FDLKMA左子樹右子樹左子樹右子樹81例：前序：ACBRSEDFMLK中序：RBSCEAFDLKM前序：

A

C

BRSEDFMLK中序：

RBS

CEAFDLKMA左子樹右子樹左子樹右子樹CD82例：前序：ACBRSEDFMLK中序：RBSCEAFDLKM前序：

ACBRSEDFMLK中序：

RBSCEAFDLKMA左子樹左子樹右子樹右子樹CD左子樹右子樹左子樹右子樹83例：前序：ACBRSEDFMLK中序：RBSCEAFDLKMA左子樹左子樹右子樹右子樹CD左子樹右子樹左子樹右子樹BEFM前序：ACBRSEDFMLK中序：RBSCEAFDLKM84例：前序：ACBRSEDFMLK中序：RBSCEAFDLKMA左子樹左子樹右子樹CDBEFM左子樹右子樹左子樹前序：ACBRSEDFMLK中序：RBSCEAFDLKM85例：前序：ACBRSEDFMLK中序：RBSCEAFDLKMA左子樹左子樹右子樹CDBEFMRS左子樹右子樹左子樹LK前序：ACBRSEDFML

K中序：RBSCEAFDLKM862.由后根、中根恢復(fù)二叉樹步驟：（1）根據(jù)后根序列的最后一個元素確定根結(jié)點；在中根序列中找到該根結(jié)點，

確定該根結(jié)點的左、右子樹的中根序列；再在后根序列中確定此左、右子樹的后根序列；（2）根據(jù)左、右子樹的后根序列分別找出左子樹和右子樹的根結(jié)點，并把左、右子樹的根結(jié)點連到父結(jié)點上去；（3）再對左、右子樹按此方法找出根結(jié)點和左、右子樹；

如此遞歸下去，當(dāng)取盡后根序列中的結(jié)點時，便恢復(fù)了一棵二叉樹。87例：由下列中根序列和后根序列恢復(fù)二叉樹。后根序列：CEDBHGJIFA中根序列：CBEDAGHFJI88例：后序：CEDBHGJIFA中序：CBEDAGHFJIA左子樹右子樹左子樹右子樹后序：CEDBHGJIFA中序：CBEDAGHFJI89例：后序：CEDBHGJIFA中序：CBEDAGHFJIA左子樹右子樹左子樹右子樹BF后序：CEDBHGJIFA中序：CBEDAGHFJI90例：后序：CEDBHGJIFA中序：CBEDAGHFJIABF左子樹左子樹右子樹右子樹左子樹右子樹左子樹右子樹后序：CEDBHGJIFA中序：CBEDAGHFJI91例：后序：CEDBHGJIFA中序：CBEDAGHFJIABF左子樹左子樹右子樹右子樹左子樹右子樹左子樹右子樹CDGI后序：CEDBHGJIFA中序：CBEDAGHFJI92例：后序：CEDBHGJIFA中序：CBEDAGHFJIABF左子樹左子樹右子樹CDGIEHJ后序：CEDBHGJIFA中序：CBEDAGHFJI936.5線索二叉樹94對二叉樹的遍歷可得到三種序列：先序、中序、后序序列。均為線性序列。結(jié)點至多有一個直接前驅(qū)和直接后繼。在二叉鏈表中找孩子結(jié)點容易，但找這樣的直接前驅(qū)和直接后繼不行。利用二叉鏈表中的空指針域，存儲直接前驅(qū)和直接后繼的指針（為區(qū)別起見此時指針稱為線索）。帶有線索的二叉樹稱為線索二叉樹。對二叉樹以某種次序遍歷改變空指針域為線索，使其變?yōu)榫€索二叉樹的過程稱為線索化。1.線索二叉樹95∧

A∧

∧

B∧

A∧

兩個結(jié)點的二叉鏈表

單結(jié)點的二叉鏈表圖

在二叉鏈表存儲的二叉樹中：單個結(jié)點的二叉樹有2個空指針域，如圖所示。兩個結(jié)點的二叉樹有3個空指針域，如圖所示。96可以證明：一個具有n個結(jié)點的二叉樹，若采用二叉鏈表存儲結(jié)構(gòu)，在總共2n個指針域中，只有n-1個指針域用來存儲結(jié)點子樹的地址，另外n+1個都是空指針域。證明：度為0的結(jié)點數(shù)為n0每個結(jié)點有2個空鏈域。度為1的結(jié)點數(shù)為n1每個結(jié)點有1個空鏈域。度為2的結(jié)點數(shù)為n2每個結(jié)點沒有空鏈域。

所以空鏈域數(shù)=2n0+n1

把性質(zhì)5（對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1）代入上式得：

空鏈域數(shù)=2n0+n1=n0+n0+n1=n0+n2+1+n1=n0+n1+n2+1=n+1性質(zhì)：含有n個結(jié)點的二叉鏈表中有n+1個空指針域。972.線索化二叉樹的方法同理，對二叉樹的不同遍歷可得到三種序列的線索二叉樹：先序線索二叉樹、中序線索二叉樹（用得多）、后序線索二叉樹。typedefstructnode{intdata;intlt,rt;structnode*lc,*rc;}BT;

在線索二叉樹的結(jié)點中增加兩個標(biāo)志域：lt:若lt=0,lc域為指針指向左孩子

若lt=1,lc域為線索指向其前驅(qū)rt:若rt=0,rc域為指針指向右孩子

若rt=1,rc域為線索

指向其后繼（1）結(jié)點定義

lcltdatartrc98ABCDE

A

B

D

C

ET先序序列：ABCDE先序線索二叉樹00001111^11（2）先序線索二叉樹99ABCDE

A

B

D

C

ET中序序列：BCAED中序線索二叉樹00001111^11^（3）中序線索二叉樹100ABCDE

A

B

D

C

ET后序序列：CBEDA后序線索二叉樹0000111111^(4)

后序線索二叉樹101ABCDE頭結(jié)點：lt=0,lc指向根結(jié)點rt=1,rc指向頭結(jié)點自己遍歷序列中第一個結(jié)點的

lc最后一個結(jié)點的

rc

均指向頭結(jié)點

A

B

D

C

ET中序序列：BCAED中序線索二叉樹00001111^11^(5)

中序線索二叉樹

0A0

1B0

0D1

1C1

1E1T中序序列：BCAED帶頭結(jié)點的中序線索二叉樹

01102(6)

按中序線索化二叉樹算法實現(xiàn)ABCDEt

0

1prpiP->A

A

B

D

C

Ebt^^^^^^0000000000BT*zxxsh(BT*bt){BT*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}p103BT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}ABCDE

A

B

D

C

Ebt^^^^^^t

0

1prpiP->AP->B0000000000104Ch5_20.cABCDE

A

B

D

C

Ebt^^^^^^t

0

1prP=NULLiP->AP->BBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000000000p105Ch5_20.cABCDE

A

B

D

C

Ebt^^^^^^t

0

1prPiP->A輸出:BBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;}if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}00000000001106Ch5_20.cABCDE

A

B

D

C

Ebt^^^^^t

0

1prP輸出:BiP->ABT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;}if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000100000107Ch5_20.cABCDE

A

B

D

C

Ebt^^^^^t

0

1prP輸出:BiP->AP->CBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;}if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000100000108Ch5_20.cABCDE

A

B

D

C

Ebt^^^^^t

0

1prP=NULLiP->AP->C輸出:BBT*zxxsh(BT*bt){BT*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000100000P109Ch5_20.cABCDE

A

B

D

C

Ebt^^^^^t

0

1prPiP->A輸出:BCBT*zxxsh(JD*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}00001000001P->C110Ch5_20.cABCDE

A

B

D

C

Ebt^^^^t

0

1prP=NULLiP->A輸出:BC

BT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000100010111Ch5_20.cABCDE

A

B

D

C

Ebt^^^^t

0

1prPi輸出:BCABT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}00001000101P->A112Ch5_20.cABCDE

A

B

D

C

Ebt^^^t

0

1P輸出:BCA

priP->DBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL) {pr->rt=1;pr->rc=p;}

pr=p;p=p->rc; }}while(i>0||p!=NULL);

pr->rc=t;pr->rt=1;t->rc=pr;}return(t);}0000101010113Ch5_20.cABCDE

A

B

D

C

Ebt^^^t

0

1Pi輸出:BCA

prP->DBT*zxxsh(BT*bt){JD*p,*pr,*s[M],*t;inti=0;

t=(BT*)malloc(sizeof(BT));t->lt=0;t->rt=1;t->rc=t;if(bt==NULL)t->lc=t;else{t->lc=bt;pr=t;p=bt;do{while(p!=NULL) {s[i++]=p;p=p->lc;} if(i>0) {p=s[--i]; printf("%c",p->data);

if(p->lc==NULL) {p->lt=1;p->lc=pr;}

if(pr->rc==NULL