二叉樹(shù)的基本知識(shí)

二叉樹(shù)的基本知識(shí)數(shù)據(jù)對(duì)象D：D是具有一樣特性的數(shù)據(jù)元素的集合。假設(shè)D為空集，那么稱為空樹(shù)；否那么:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root,(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定義的樹(shù)，稱為根root的子樹(shù)。

數(shù)據(jù)關(guān)系R：結(jié)點(diǎn):結(jié)點(diǎn)的度:樹(shù)的度:葉子結(jié)點(diǎn):分支結(jié)點(diǎn):數(shù)據(jù)元素+假設(shè)干指向子樹(shù)的分支分支的個(gè)數(shù)樹(shù)中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM(從根到結(jié)點(diǎn)的)途徑：孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn)、堂兄弟祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)結(jié)點(diǎn)的層次:樹(shù)的深度：

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

二叉樹(shù)或?yàn)榭諛?shù)；或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹(shù)和右子樹(shù)的、互不交的二叉樹(shù)組成。ABCDEFGHK根結(jié)點(diǎn)左子樹(shù)右子樹(shù)EFG兩類特殊的二叉樹(shù)：滿二叉樹(shù)：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。完全二叉樹(shù)：樹(shù)中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹(shù)中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789101112131415abcdefghij二叉樹(shù)的五種根本形態(tài)：NLRLR空樹(shù)只含根結(jié)點(diǎn)NNN右子樹(shù)為空樹(shù)左子樹(shù)為空樹(shù)左右子樹(shù)均不為空樹(shù)二叉樹(shù)的主要根本操作：查找類插入類刪除類Root(T)//求樹(shù)的根結(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)//斷定樹(shù)是否為空樹(shù)TreeDepth(T)//求樹(shù)的深度TraverseTree(T,Visit())//遍歷InitTree(&T)//初始化置空樹(shù)插入類：CreateTree(&T,definition)//按定義構(gòu)造樹(shù)Assign(T,cur_e,value)//給當(dāng)前結(jié)點(diǎn)賦值InsertChild(&T,&p,i,c)//將以c為根的樹(shù)插入為結(jié)點(diǎn)p的第i棵子樹(shù)ClearTree(&T)//將樹(shù)清空刪除類：DestroyTree(&T)//銷毀樹(shù)的構(gòu)造DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹(shù)二叉樹(shù)

的重要特性性質(zhì)1：在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。(i≥1)性質(zhì)2：

深度為k的二叉樹(shù)上至多含2k-1個(gè)結(jié)點(diǎn)〔k≥1〕性質(zhì)3：

對(duì)任何一棵二叉樹(shù)，假設(shè)它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為2的結(jié)點(diǎn)，那么必存在關(guān)系式：n0=n2+1。。性質(zhì)4：

具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1性質(zhì)5假設(shè)對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從上到下且從左至右進(jìn)展1至n的編號(hào)，那么對(duì)完全二叉樹(shù)中任意一個(gè)編號(hào)為i的結(jié)點(diǎn)：

(1)假設(shè)i=1，那么該結(jié)點(diǎn)是二叉樹(shù)的根，無(wú)雙親,否那么，編號(hào)為i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn);

(2)假設(shè)2i>n，那么該結(jié)點(diǎn)無(wú)左孩子，

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

(3)假設(shè)2i+1>n，那么該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，

否那么，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)二叉樹(shù)的存儲(chǔ)構(gòu)造二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示一、二叉樹(shù)的順序存儲(chǔ)表示#defineMAX_TREE_SIZE100//設(shè)二叉樹(shù)的最大結(jié)點(diǎn)數(shù)typedefstruct{ElemType*data;//初始化時(shí)分配存儲(chǔ)空間

intnodeNum;//二叉樹(shù)中的結(jié)點(diǎn)數(shù)目}SqBiTree;一、二叉樹(shù)的順序存儲(chǔ)表示//0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)例如:ABD

012345678910111213ABCDEF1401326(k+1)2-1=2k+1CEF二、二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示1.二叉鏈表2．三叉鏈表3．雙親鏈表ADEBCFrootlchilddatarchild結(jié)點(diǎn)構(gòu)造:1.二叉鏈表typedefstruct{//結(jié)點(diǎn)構(gòu)造TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點(diǎn)構(gòu)造:C語(yǔ)言的類型描繪如下:rootADEBCF2．三叉鏈表parent

lchilddatarchild結(jié)點(diǎn)構(gòu)造:typedefstruct{//結(jié)點(diǎn)構(gòu)造TElemTypedata;structTriTNode*lchild,*rchild;//左右孩子指針structTriTNode*parent;//雙親指針}TriTNode,*TriTree;parentlchilddatarchild結(jié)點(diǎn)構(gòu)造:C語(yǔ)言的類型描繪如下:結(jié)點(diǎn)構(gòu)造:3．雙親鏈表dataparentABDCEF0B41D42C03E14A-15F36LRTagLRRRL根n=6typedefstruct{//結(jié)點(diǎn)構(gòu)造TElemTypedata;int*parent;//指向雙親的指針charLRTag;//左、右孩子標(biāo)志域}BPTNodetypedefstruct{//樹(shù)構(gòu)造BPTNodenodes[MAX_NODE_SIZE];intnum_node;//樹(shù)中含結(jié)點(diǎn)數(shù)目introot;//根結(jié)點(diǎn)的位置}BPTree樹(shù)的三種存儲(chǔ)構(gòu)造一、雙親表示法二、孩子鏈表表示法三、樹(shù)的二叉鏈表(孩子-兄弟〕存儲(chǔ)表示法ABCDEFGr=0n=60

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent一、雙親表示法:typedefstructPTNode{Elemdata;intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結(jié)點(diǎn)構(gòu)造:C語(yǔ)言的類型描繪:typedefstruct{PTNodenodes[MAX_TREE_SIZE];intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}PTree;樹(shù)構(gòu)造:r=0n=6datafirstchildABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

4645

123二、孩子鏈表表示法:-1000224parenttypedefstructCTNode{intchild;structCTNode*nextchild;}*ChildPtr;孩子結(jié)點(diǎn)構(gòu)造:

childnextchildC語(yǔ)言的類型描繪:typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針

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

datafirstchildtypedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置

}CTree;樹(shù)構(gòu)造:ABCDEFGrootABCEDFGABCED