第06章-1 樹(shù)和二叉樹(shù)

1、第六章 樹(shù)和二叉樹(shù)n 6.1 樹(shù)的定義和基本術(shù)語(yǔ)n 6.2 二叉樹(shù)n 6.3 遍歷二叉樹(shù)和線(xiàn)索二叉樹(shù)n 6.4 樹(shù)和森林n 6.6 赫夫曼樹(shù)及其應(yīng)用 26.1 樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)樹(shù)(Tree)是n(n0)個(gè)結(jié)點(diǎn)的有限集T，非空樹(shù)滿(mǎn)足以下條件:(1)有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn);(2) 除根結(jié)點(diǎn)外的其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2.Tm,其中,每一個(gè)集合本身又是一棵樹(shù), 并且稱(chēng)為根的子樹(shù)。n樹(shù)的定義 3(a)是有13個(gè)結(jié)點(diǎn)的樹(shù),其中A是根,其余結(jié)點(diǎn)分成三個(gè)互不相交的子樹(shù)；(b)是只有一個(gè)根結(jié)點(diǎn)的樹(shù);6.1 樹(shù)的定義和基本術(shù)語(yǔ)n樹(shù)的描述 4樹(shù)型結(jié)構(gòu)的其他表示方法：廣義表表示

2、 (A(B(E(K,L),F),C(G),D(H(M),I,J)集合表示 BHMJIFDAKLECG5ABEFCDGHJKI凹入表示LM6樹(shù)的結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干個(gè)指向其子樹(shù)的分支。結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹(shù)數(shù)。樹(shù)的度：樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值。葉子（終端結(jié)點(diǎn)）：度為零的結(jié)點(diǎn)。非終端結(jié)點(diǎn)（分支結(jié)點(diǎn)）：度不為零的結(jié)點(diǎn)。孩子、雙親、兄弟、祖先、子孫結(jié)點(diǎn)的層次和樹(shù)的深度、堂兄弟有序樹(shù)和無(wú)序樹(shù)森林：是m棵互不相交的樹(shù)的集合6.1 樹(shù)的定義和基本術(shù)語(yǔ)n樹(shù)的基本術(shù)語(yǔ) 7n二叉樹(shù)的定義是結(jié)點(diǎn)的有限集合。該集合或者為空集，或者由一個(gè)根及兩棵互不相交的稱(chēng)為這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)構(gòu)成。二叉樹(shù)中每個(gè)結(jié)點(diǎn)

3、的度不大于2.n二叉樹(shù)的五種基本狀態(tài) (a)空二叉樹(shù)空二叉樹(shù)A (b)根和空的根和空的左右子樹(shù)左右子樹(shù)A (c)根和左根和左子樹(shù)子樹(shù)A(d)根和右根和右子樹(shù)子樹(shù)A (e)根和左根和左右子樹(shù)右子樹(shù)6.2 二叉樹(shù)8n二叉樹(shù)抽象數(shù)據(jù)類(lèi)型定義ADT BinaryTree數(shù)據(jù)對(duì)象D：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：R=H(1) 存在唯一根結(jié)點(diǎn)root。(2) 若D-root不為空，則存在互不相交的集合DL,DR，分別表示左/右子樹(shù)的元素集合。(3) 若DL不為空，則存在唯一結(jié)點(diǎn)xL與root存在有序關(guān)系H，且存在DL上的一組關(guān)系HL H. 若DR不為空(4) (DL,HL) 與 (DR,H

4、R) 是符合本定義的二叉樹(shù).6.2 二叉樹(shù)H=,HL,HR9n二叉樹(shù)抽象數(shù)據(jù)類(lèi)型定義基本操作： InitBiTree(&T)DestroyBiTree(&T) CreateBiTree(&T,definition) BiTreeEmpty(T)BiTreeDepth(T) Parent(T,e)LeftChild(T,e) InsertChild(T,p,LR,C)DeleteChild(T,p,LR) Traverse(T,Visit()6.2 二叉樹(shù)10n二叉樹(shù)的性質(zhì)性質(zhì)1：在二叉樹(shù)的第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i=1)性質(zhì)2：深度為k的二叉樹(shù)至多有2k-1個(gè)結(jié)點(diǎn)

5、。性質(zhì)3：對(duì)于任何一棵二叉樹(shù)T，如果其葉子數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1滿(mǎn)二叉樹(shù)：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)。完全二叉樹(shù)：深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿(mǎn)二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)。6.2 二叉樹(shù)11性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為log2n+1性質(zhì)5：如果對(duì)一棵n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任意結(jié)點(diǎn)編號(hào)i(1in)，有(1)若i=1，該結(jié)點(diǎn)為根，它無(wú)雙親結(jié)點(diǎn)；(2)若i1，該結(jié)點(diǎn)的雙親結(jié)點(diǎn)編號(hào)為i/2；(3)若2in，則結(jié)點(diǎn)i沒(méi)有左孩子,否則有編號(hào)為2i的左孩子；(4)若2i+1n，則結(jié)點(diǎn)i沒(méi)有右

6、孩子，否則有編號(hào)為2i+1的右孩子。n二叉樹(shù)的性質(zhì)6.2 二叉樹(shù)12順序存儲(chǔ)結(jié)構(gòu) 連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)完全二叉樹(shù)上的結(jié)點(diǎn)元素。abcdefghijklabcdefghijkln二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.2 二叉樹(shù)優(yōu)勢(shì)：結(jié)構(gòu)簡(jiǎn)單；便于某些基本操作的實(shí)現(xiàn)13abcdefgabdde0000fgn二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.2 二叉樹(shù)順序存儲(chǔ)結(jié)構(gòu)劣勢(shì)：可能存在空間浪費(fèi)；對(duì)某些操作實(shí)現(xiàn)復(fù)雜14鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)n二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)6.2 二叉樹(shù)datalchild rchilddatalchild parent rchild15abcefghidabcd efi h g 二叉鏈表三叉鏈表n二叉樹(shù)的存儲(chǔ)結(jié)

7、構(gòu)6.2 二叉樹(shù)typedef struct BiTNodeTElemType data;struct BiTNode *lchild, *rchild;BiTNode, *BiTree;166.3 遍歷二叉樹(shù)n樹(shù)ABCDEFGn 二叉樹(shù)有且僅有一個(gè)特定的稱(chēng)為根的結(jié)點(diǎn);除根結(jié)點(diǎn)外的其余結(jié)點(diǎn)可分為m個(gè)互不相交的有限集。每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)17 遍歷：按某種搜索路徑訪(fǎng)問(wèn)結(jié)構(gòu)中的所有元素，且每個(gè)元素只被訪(fǎng)問(wèn)一次。 遍歷是任何結(jié)構(gòu)均有的操作，對(duì)線(xiàn)性結(jié)構(gòu)而言，只有一條搜索路徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)，故不需要另加討論。而二叉樹(shù)是非線(xiàn)性結(jié)構(gòu)，每個(gè)結(jié)點(diǎn)最多有兩個(gè)直接后繼，則存在如何遍歷即按什么樣的

8、搜索路徑遍歷的問(wèn)題。按層次搜索從左(子樹(shù))向右(子樹(shù))搜索從右向左搜索6.3 遍歷二叉樹(shù)18遍歷二叉樹(shù)， 即如何按某條搜索路徑巡訪(fǎng)樹(shù)中每個(gè)結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪(fǎng)問(wèn)一次，而且僅被訪(fǎng)問(wèn)一次。從左向右的操作排列次序： 先序遍歷：根、左子樹(shù)、右子樹(shù)中序遍歷：左子樹(shù)、根、右子樹(shù)后序遍歷：左子樹(shù)、右子樹(shù)、根6.3 遍歷二叉樹(shù)n遍歷二叉樹(shù)19abcefh若遍歷的二叉樹(shù)為空，執(zhí)行空操作；否則(1)訪(fǎng)問(wèn)根結(jié)點(diǎn)；(2)先序遍歷左子樹(shù)；(3)先序遍歷右子樹(shù)。先序(Preorder)遍歷abcehf6.3 遍歷二叉樹(shù)20若遍歷的二叉樹(shù)為空，執(zhí)行空操作；否則(1)中序遍歷左子樹(shù)；(2)訪(fǎng)問(wèn)根結(jié)點(diǎn)；(3)中序遍歷右子樹(shù)

9、。abcefh中序(Inorder)遍歷中序序列：baehcf6.3 遍歷二叉樹(shù)21abcefh若遍歷的二叉樹(shù)為空，執(zhí)行空操作；否則(1)后序遍歷左子樹(shù)；(2)后序遍歷右子樹(shù)；(3)訪(fǎng)問(wèn)根結(jié)點(diǎn)。后序(Postorder)遍歷后序序列：bhefca6.3 遍歷二叉樹(shù)22n例:請(qǐng)分別寫(xiě)出二叉樹(shù)的先序、中序和后序序列后序遍歷：左子樹(shù) 右子樹(shù) 根-中序遍歷：左子樹(shù) 根 右子樹(shù)-前序遍歷：根 左子樹(shù) 右子樹(shù)abfcdhgi6.3 遍歷二叉樹(shù)e23n二叉樹(shù)的遍歷遍歷序與二叉樹(shù)的對(duì)應(yīng)前序遍歷序+中序遍歷序唯一確定二叉樹(shù)后序遍歷序+中序遍歷序唯一確定二叉樹(shù)abcefghid前序遍歷序列：abdceghfi中序

10、遍歷序列：dbagehcfi6.3 遍歷二叉樹(shù)24n二叉樹(shù)的遍歷遍歷的算法描述(采用二叉鏈表結(jié)構(gòu))遞歸描述非遞歸描述abcefghid6.3 遍歷二叉樹(shù)void PreOrder (BiTree T,Status( *visit)(TElemType e) / 先序遍歷二叉樹(shù) if (T) visit(T-data); / 訪(fǎng)問(wèn)根結(jié)點(diǎn) PreOrder(T-lchild, visit); / 先序遍歷左子樹(shù) PreOrder(T-rchild, visit);/ 先序遍歷右子樹(shù) 25n二叉樹(shù)的遍歷遍歷思想的應(yīng)用：創(chuàng)建二叉樹(shù)abcefghid6.3 遍歷二叉樹(shù)void CreatBiTree (

11、BiTree &T) / 按按先序序列建立二叉樹(shù) scanf(“%c”, &ch);if(ch= )T=NULL;else T=(BiTNode *)malloc(sizeof(BiTNode); T-data=ch; CreatBiTree(T-lchild, visit); / 先序遍歷左子樹(shù) CreatBiTree(T-rchild, visit);/ 先序遍歷右子樹(shù) 26n二叉樹(shù)的遍歷遍歷的算法描述遞歸描述非遞歸描述記錄“來(lái)時(shí)未訪(fǎng)問(wèn)的結(jié)點(diǎn)”abcefghid6.3 遍歷二叉樹(shù)27pn二叉樹(shù)的遍歷遍歷的算法描述遞歸描述非遞歸描述abcefghid6.3 遍歷二叉樹(shù)void

12、 InOrder(BiTree T, Status( *visit)(TElemType e) /中序非遞歸遍歷二叉樹(shù) InitStack(S);p=T; while (p|!StackEmpty(S) ) if(p) Push(S, p); p=p-lchild; /根指針進(jìn)棧 else Pop(S,p); visit(p-data); p=p-rchild; ppppppp pppppppp pp pP: dP: bP: a28ADEBCF n線(xiàn)索二叉樹(shù)定義：二叉樹(shù)遍歷后得到的是一個(gè)線(xiàn)性序列，指示該序列中的前驅(qū)和后繼的信息(指針)稱(chēng)為線(xiàn)索。 6.3 遍歷二叉樹(shù)和線(xiàn)索二叉樹(shù)以中序遍歷為例：

13、B C A D F E29n線(xiàn)索二叉樹(shù) 結(jié)構(gòu)定義6.3 遍歷二叉樹(shù)和線(xiàn)索二叉樹(shù)lchildLTagdataRTag rchild 以這種結(jié)構(gòu)構(gòu)成的二叉鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu),叫做線(xiàn)索鏈表,其中指向結(jié)點(diǎn)前驅(qū)與后繼的指針叫做線(xiàn)索.加上線(xiàn)索的二叉樹(shù)稱(chēng)之為線(xiàn)索二叉樹(shù).對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€(xiàn)索二叉樹(shù)的過(guò)程叫做線(xiàn)索化.其中：Ltag=0 lchild域指示結(jié)點(diǎn)的左孩子結(jié)點(diǎn)1 lchild域指示結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)Rtag=0 rchild域指示結(jié)點(diǎn)的右孩子結(jié)點(diǎn)1 rchild域指示結(jié)點(diǎn)的后繼結(jié)點(diǎn)30abcdefihg中序線(xiàn)索化二叉樹(shù)abcd efi h g n線(xiàn)索二叉樹(shù) 例：中序線(xiàn)索化二叉樹(shù)，即在中序遍歷過(guò)程中為“空指針”賦值6.3 遍歷二叉樹(shù)和線(xiàn)索二叉樹(shù)31后繼的尋找方法:若結(jié)點(diǎn)右標(biāo)志為1,則右鏈為線(xiàn)索,指示其后繼;否則遍歷右子樹(shù)時(shí)訪(fǎng)問(wèn)的第一個(gè)結(jié)點(diǎn)為其后繼,即右子樹(shù)中最左下的結(jié)點(diǎn)。前驅(qū)的尋找方法:若結(jié)點(diǎn)左標(biāo)志為1