第06章-1 樹和二叉樹

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

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

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

4、R) 是符合本定義的二叉樹.6.2 二叉樹H=,HL,HR9n二叉樹抽象數(shù)據(jù)類型定義基本操作： 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 二叉樹10n二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層上至多有2i-1個結(jié)點(i=1)性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點

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

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

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

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

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

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

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

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

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