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

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

基本操作：查找類

插入類刪除類6

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())//遍歷7InitTree(&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棵子樹8

ClearTree(&T)

//將樹清空

刪除類：DestroyTree(&T)

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

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

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

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

樹的特點(diǎn)：

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

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

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

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

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

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

樹

(b)

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

)

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

二叉樹是有n（n>=0）個(gè)結(jié)點(diǎn)的有限集合。（1）該集合或者為空（n=0）；（2）該集合或者只有一個(gè)根結(jié)點(diǎn)；（3）該集合或者由一個(gè)根結(jié)點(diǎn)及兩個(gè)不相交的分別稱為左子樹和右子樹組成的非空樹；（4）左子樹和右子樹同樣又都是二叉樹。二叉樹的定義是遞歸的：在一棵非空的二叉樹中，每個(gè)結(jié)點(diǎn)至多只有兩棵子樹，分別稱為左子樹和右子樹，左子樹和右子樹同樣又都是二叉樹。二叉樹是有序樹：二叉樹的左右子樹的次序不能交換。25ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹26二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點(diǎn)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é)點(diǎn)。（4）Inorder(BT*T)：按中序（左、根、右）遍歷二叉樹上所有結(jié)點(diǎn)。（5）Postorder(BT*T)：按后序（左、右、根）遍歷二叉樹上所有結(jié)點(diǎn)。32（6）Levelorder(BT*T)：按層次遍歷二叉樹上所有結(jié)點(diǎn)。（7）Leafnum(BT*T)：

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

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

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

結(jié)點(diǎn)。那么，第i-1層至多有個(gè)結(jié)點(diǎn)。

須證明

j=i時(shí)命題也成立。因?yàn)槎鏄涿總€(gè)結(jié)點(diǎn)的度至多為2

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

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

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

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

都與深度為

k的滿二叉樹中編號(hào)從

1

至

n的結(jié)點(diǎn)一一對(duì)

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

支下子孫的最大層次必為

L或

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

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

即2k-1

n

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

k-1log2n

<k

對(duì)k取整數(shù)：

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

則對(duì)任一結(jié)點(diǎn)

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

i的結(jié)點(diǎn)是根結(jié)點(diǎn)。

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

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

2i+1

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

n0，度為

2

的

結(jié)點(diǎn)數(shù)為

n2，則

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

T中度為

1

的結(jié)點(diǎn)數(shù)因?yàn)椋憾鏄渲兴薪Y(jié)點(diǎn)的度均小于或等于2所以：其結(jié)點(diǎn)總數(shù)n=n0+n1+n2

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

n=B+1

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

B=n1+2n2

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

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

123456789101142特點(diǎn)：浪費(fèi)空間，適于存滿二叉樹和完全二叉樹。aceda0c000d0000

123456789101112131400e43無(wú)須按完全二叉樹的結(jié)點(diǎn)層次編號(hào)，依次按編號(hào)存放二叉樹中的數(shù)據(jù)元素即可。結(jié)點(diǎn)數(shù)據(jù)，左子編號(hào)，右子編號(hào)均要存儲(chǔ)。故可采用長(zhǎng)度為n的結(jié)構(gòu)數(shù)組存放。n為結(jié)點(diǎn)個(gè)數(shù)。結(jié)構(gòu)數(shù)組相當(dāng)于一個(gè)二維構(gòu)造,第一維是結(jié)構(gòu)數(shù)組元素,每個(gè)元素是一個(gè)結(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ù)組存儲(chǔ)法：44順序存儲(chǔ)結(jié)構(gòu)小結(jié)：滿二叉樹或完全二叉樹可采用一維數(shù)組；結(jié)點(diǎn)少，層數(shù)高可采用二維數(shù)組；查找方便，找孩子結(jié)點(diǎn)及父結(jié)點(diǎn)均方便；缺點(diǎn)：空間擴(kuò)充不便；插入和刪除須大量移動(dòng)數(shù)據(jù)。45二叉鏈表：結(jié)點(diǎn)組成：lchilddatarchildABCDEFG

AB

C

D

E

F

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

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

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

鏈?zhǔn)酱鎯?chǔ)結(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é)點(diǎn)組成：48三叉鏈表的靜態(tài)結(jié)構(gòu)：ABCDFErootdata

parent

leftChildrightChild012345A

-11-1B023C1

-1-1D145E3-1-1F3-1-1496.3遍歷二叉樹501.問(wèn)題的提出

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

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

{printf(T->data); //輸出結(jié)點(diǎn)的數(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）中序遍歷也稱為中根遍歷。其遞歸過(guò)程為：若二叉樹為空，則遍歷結(jié)束，返回。否則：（1）中序遍歷根結(jié)點(diǎn)的左子樹；（2）訪問(wèn)根結(jié)點(diǎn)；（3）中序遍歷根結(jié)點(diǎn)的右子樹。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é)點(diǎn)的數(shù)據(jù)域

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

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

中序遍歷:60(3)后序（根）遍歷（LRD）后序遍歷也稱為后根遍歷。其遞歸過(guò)程為：若二叉樹為空，則遍歷結(jié)束，返回。否則：（1）后序遍歷根結(jié)點(diǎn)的左子樹；（2）后序遍歷根結(jié)點(diǎn)的右子樹。（3）訪問(wèn)根結(jié)點(diǎn)；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é)點(diǎn)的數(shù)據(jù)域

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

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

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

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

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

p=p->lchild;//進(jìn)入左子樹}//左子樹為空，退出

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

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

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

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

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

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

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

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

ABDGEHCFIK中根遍歷的序列：

DGBHEAFKIC后根遍歷的序列：

GDHEBKIFCA層次遍歷的序列：

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

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

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

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

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

（1）把每個(gè)結(jié)點(diǎn)去掉指針項(xiàng)，將結(jié)點(diǎn)的數(shù)據(jù)按中序存儲(chǔ)于數(shù)組中得到中序結(jié)點(diǎn)表。

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

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

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

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

如此遞歸下去，當(dāng)取盡先根序列中的結(jié)點(diǎn)時(shí)，便恢復(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ù)后根序列的最后一個(gè)元素確定根結(jié)點(diǎn)；在中根序列中找到該根結(jié)點(diǎn)，

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

如此遞歸下去，當(dāng)取盡后根序列中的結(jié)點(diǎn)時(shí)，便恢復(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對(duì)二叉樹的遍歷可得到三種序列：先序、中序、后序序列。均為線性序列。結(jié)點(diǎn)至多有一個(gè)直接前驅(qū)和直接后繼。在二叉鏈表中找孩子結(jié)點(diǎn)容易，但找這樣的直接前驅(qū)和直接后繼不行。利用二叉鏈表中的空指針域，存儲(chǔ)直接前驅(qū)和直接后繼的指針（為區(qū)別起見此時(shí)指針?lè)Q為線索）。帶有線索的二叉樹稱為線索二叉樹。對(duì)二叉樹以某種次序遍歷改變空指針域?yàn)榫€索，使其變?yōu)榫€索二叉樹的過(guò)程稱為線索化。1.線索二叉樹95∧

A∧

∧

B∧

A∧

兩個(gè)結(jié)點(diǎn)的二叉鏈表

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

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

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

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

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

在線索二叉樹的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域：lt:若lt=0,lc域?yàn)橹羔樦赶蜃蠛⒆?/p>

若lt=1,lc域?yàn)榫€索指向其前驅(qū)rt:若rt=0,rc域?yàn)橹羔樦赶蛴液⒆?/p>

若rt=1,rc域?yàn)榫€索

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

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é)點(diǎn)：lt=0,lc指向根結(jié)點(diǎn)rt=1,rc指向頭結(jié)點(diǎn)自己遍歷序列中第一個(gè)結(jié)點(diǎn)的

lc最后一個(gè)結(jié)點(diǎn)的

rc

均指向頭結(jié)點(diǎn)

A

B

D

C

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

中序線索二叉樹

0A0

1B0

0D1

1C1

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

01102(6)

按中序線索化二叉樹算法實(shí)現(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