第六章樹和二叉樹（一）6.1樹的類型定義6.2二叉樹的類型定義6.3二叉樹的存儲(chǔ)結(jié)構(gòu)6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7

樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼數(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：樹的類型定義

基本操作：查找類

插入類刪除類

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)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點(diǎn)p的第i棵子樹基本術(shù)語(yǔ)樹（Tree)：是n個(gè)結(jié)點(diǎn)的有限集（n>=0)。在任意一棵非空樹中，有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)（root)；當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m（m>0)個(gè)互不相交的有限集T1,T2,…,Tm,其中每個(gè)集合Ti本身又是一棵符合本定義的樹，并且稱為根root的子樹。ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),D(H,I,J(M)))T1T3T2樹根例如:1、結(jié)點(diǎn):2、結(jié)點(diǎn)的度:3、樹的度:4、葉子結(jié)點(diǎn):5、分支結(jié)點(diǎn):數(shù)據(jù)元素+若干指向子樹的分支分支的個(gè)數(shù)樹中所有結(jié)點(diǎn)的度的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM（終端結(jié)點(diǎn)）（非終端結(jié)點(diǎn)）6、(從根到結(jié)點(diǎn)的)路徑：7、孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)、堂兄弟結(jié)點(diǎn)祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)8、結(jié)點(diǎn)的層次:9、樹的深度：

由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點(diǎn)的層次為1，依次加1樹中葉子結(jié)點(diǎn)所在的最大層次樹的示意圖：根結(jié)點(diǎn)葉子結(jié)點(diǎn)分支結(jié)點(diǎn)子樹子樹子樹Level1Level2Level3Level4結(jié)點(diǎn)的層次任何一棵非空樹是一個(gè)二元組

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

F被稱為子樹森林10、森林：是m（m≥0）棵互不相交的樹的集合。ArootBCDEFGHIJMKLF(１)有確定的根；(２)樹根和子樹根之間為有向關(guān)系。有向樹：有序樹：樹中結(jié)點(diǎn)的各子樹之間的先后次序是有意義的，不能互換，否則就成為另一棵樹了。子樹之間存在確定的次序關(guān)系。無(wú)序樹：樹中結(jié)點(diǎn)的各子樹之間的先后次序無(wú)意義，可以互換。子樹之間不存在確定的次序關(guān)系。二叉樹的類型定義二叉樹是樹的基礎(chǔ)，一般的樹可以轉(zhuǎn)化為二叉樹來(lái)處理。1、二叉樹的定義：

二叉樹或?yàn)榭諛?，或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成（即左、右子樹次序不能顛倒）。ABCDEFGHK根結(jié)點(diǎn)左子樹右子樹2、二叉樹的五種基本形態(tài)：N空樹只含根結(jié)點(diǎn)NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹

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

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

InitBiTree(&T);Assign(&T,&e,value);CreateBiTree(&T,definition);InsertChild(&T,p,LR,c);ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(&T,p,LR);二叉樹的重要特性

性質(zhì)1

：在二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)。(i≥1)用歸納法證明：

歸納基：

歸納假設(shè)：

歸納證明：i=1

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

2i-1=20=1；假設(shè)對(duì)所有的j，1≤j

i，命題成立；由歸納假設(shè)知：第i-1層上至多有2i-2個(gè)結(jié)點(diǎn)。又因?yàn)槎鏄渖厦總€(gè)結(jié)點(diǎn)至多有兩棵子樹，則第i層的結(jié)點(diǎn)數(shù)=2i-22=2i-1

。性質(zhì)2

：

深度為i的二叉樹上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。證明：[證明用求等比數(shù)列前i項(xiàng)和的公式]

基于上一條性質(zhì)，深度為i的二叉樹上的結(jié)點(diǎn)數(shù)至多為

20+21+

+2i-1=2i-1

。

性質(zhì)3

：

對(duì)任何一棵二叉樹，若它含有n0個(gè)葉子結(jié)點(diǎn)、n2個(gè)度為

2

的結(jié)點(diǎn)，則必存在關(guān)系式：n0=n2+1。證明：設(shè)二叉樹上結(jié)點(diǎn)總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n0*0+n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。兩類特殊形態(tài)的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。完全二叉樹：樹中所含的n個(gè)結(jié)點(diǎn)和滿二叉樹中編號(hào)為1至n的結(jié)點(diǎn)一一對(duì)應(yīng)。123456789101112131415abcdefghij性質(zhì)4

：

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

log2n+1。證明：設(shè)完全二叉樹的深度為k，則由性質(zhì)2和完全二叉樹的定義知：深度為k-1的二叉樹應(yīng)該是一棵滿二叉樹，故結(jié)點(diǎn)數(shù)為2k-1-1；深度為k的完全二叉樹當(dāng)為滿二叉樹時(shí)結(jié)點(diǎn)數(shù)最多為2k–1。所以得2k-1-1

<n≤2k–1

2k-1≤n<2k

即

k-1≤log2n<k因?yàn)閗只能是整數(shù)，因此，k=log2n

+1。性質(zhì)5：若對(duì)含n個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行1

至n

的編號(hào)，則對(duì)完全二叉樹中任意一個(gè)編號(hào)為i

的結(jié)點(diǎn)：

(1)若i=1，則該結(jié)點(diǎn)是二叉樹的根，無(wú)雙親，否則，編號(hào)為i/2的結(jié)點(diǎn)為其雙親結(jié)點(diǎn)；

(2)若2i>n，則該結(jié)點(diǎn)無(wú)左孩子，

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

(3)若2i+1>n，則該結(jié)點(diǎn)無(wú)右孩子結(jié)點(diǎn)，

否則，編號(hào)為2i+1的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。6.3二叉樹的存儲(chǔ)結(jié)構(gòu)二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示一、二叉樹的順序存儲(chǔ)表示（適合存儲(chǔ)完全二叉樹）即用一組地址連續(xù)的存儲(chǔ)單元依次從上至下，從左至右存儲(chǔ)完全二叉樹上的結(jié)點(diǎn)元素。也就是說(shuō)，將完全二叉樹上編號(hào)為i的結(jié)點(diǎn)存放在數(shù)組下標(biāo)為（i-1)的分量中。若要存儲(chǔ)一棵一般的二叉樹，結(jié)點(diǎn)的存放應(yīng)與完全二叉樹上的結(jié)點(diǎn)對(duì)照，存儲(chǔ)在數(shù)組的相應(yīng)分量中。用“0”表示不存在該結(jié)點(diǎn)?？赡軙?huì)浪費(fèi)很多存儲(chǔ)空間，單支樹就是一個(gè)極端情況。一、二叉樹的順序存儲(chǔ)表示完全二叉樹的數(shù)組表示一般二叉樹的數(shù)組表示數(shù)組表示順序存儲(chǔ)的C語(yǔ)言描述#defineMAX_TREE_SIZE100//二叉樹的最大結(jié)點(diǎn)數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號(hào)單元存儲(chǔ)根結(jié)點(diǎn)ADEBCFrootlchilddatarchild結(jié)點(diǎn)結(jié)構(gòu)1.二叉鏈表二、二叉樹的鏈?zhǔn)酱鎯?chǔ)表示二叉鏈表的C語(yǔ)言描述typedefstruct

BiTNode

{

//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;

struct

BiTNode

*lchild,*rchild;

//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu):ADEBCFroot2．三叉鏈表parent

lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu)三叉鏈表的C語(yǔ)言描述typedefstructTriTNode{