二叉樹的基本知識(shí)數(shù)據(jù)對(duì)象D：D是具有一樣特性的數(shù)據(jù)元素的集合。假設(shè)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：結(jié)點(diǎn):結(jié)點(diǎn)的度:樹的度:葉子結(jié)點(diǎn):分支結(jié)點(diǎn):數(shù)據(jù)元素+假設(shè)干指向子樹的分支分支的個(gè)數(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)的層次:樹的深度：

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

二叉樹或?yàn)榭諛洌换蚴怯梢粋€(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹EFG兩類特殊的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789101112131415abcdefghij二叉樹的五種根本形態(tài)：NLRLR空樹只含根結(jié)點(diǎn)NNN右子樹為空樹左子樹為空樹左右子樹均不為空樹二叉樹的主要根本操作：查找類插入類刪除類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())//遍歷InitTree(&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棵子樹ClearTree(&T)//將樹清空刪除類：DestroyTree(&T)//銷毀樹的構(gòu)造DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹二叉樹

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

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

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

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

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

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

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

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

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

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

012345678910111213ABCDEF1401326(k+1)2-1=2k+1CEF二、二叉樹的鏈?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語言的類型描繪如下: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語言的類型描繪如下:結(jié)點(diǎn)構(gòu)造:3．雙親鏈表dataparentABDCEF0B41D42C03E14A-15F36LRTagLRRRL根n=6typedefstruct{//結(jié)點(diǎn)構(gòu)造TElemTypedata;int*parent;//指向雙親的指針charLRTag;//左、右孩子標(biāo)志域}BPTNodetypedefstruct{//樹構(gòu)造BPTNodenodes[MAX_NODE_SIZE];intnum_node;//樹中含結(jié)點(diǎn)數(shù)目introot;//根結(jié)點(diǎn)的位置}BPTree樹的三種存儲(chǔ)構(gòu)造一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟〕存儲(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語言的類型描繪:typedefstruct{PTNodenodes[MAX_TREE_SIZE];intr,n;//根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù)

}PTree;樹構(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語言的類型描繪:typedefstruct{Elemdata;ChildPtrfirstchild;//孩子鏈的頭指針

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

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

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