二叉樹的基本知識

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

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

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

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

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

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

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

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

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

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

否那么，編號為2i的結(jié)點為其左孩子結(jié)點；

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

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

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

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

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

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

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

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

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