1、樹型結構是一類重要的非線性結構。樹型結構是結點之間有分支,并且具有層次關系的結構,它非常類似于自然界中的樹。樹結構在客觀世界中是大量存在的。例如家譜、行政組織機構都可用樹形象地表示。 樹結構在計算機領域中也有著廣泛的應用,例如在編譯程序中,用樹結構來表示源程序的語法結構；在數(shù)據(jù)庫系統(tǒng)中,可用樹結構來組織信息；在分析算法的行為時,可用樹結構來描述其執(zhí)行過程等等。,華中師范大學,課前導學 6.1 二叉樹 6.2 遍歷二叉樹和線索二叉樹 6.3 樹和森林 6.4 樹的應用,第六章 二叉樹和樹,【學習目標】,領會樹和二叉樹的類型定義，理解樹和二叉樹的結構差別。 熟記二叉樹的主要特性，并掌握它們的證明

2、熟練掌握二叉樹的各種遍歷算法，并能靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。 理解二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅和后繼的方法。 熟練掌握二叉樹和樹的各種存儲結構及其建立的算法。 學會編寫實現(xiàn)樹的各種操作的算法。 了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。,【重點和難點】,重點：二叉樹和樹的遍歷及其應用 難點：編寫實現(xiàn)二叉樹和樹的各種 操作的遞歸算法 知識點 樹的類型定義 二叉樹的類型定義 二叉樹的存儲表示 二叉樹的遍歷以及其它操作的實現(xiàn) 線索二叉樹 樹和森林的存儲表示 樹和森林的遍歷以及其它操作的實現(xiàn) 最優(yōu)樹和赫夫曼編碼,【學習指南】,本章是整個課程的第三個學習重

3、點，也是整個課程中的一大難點。在本章的學習過程中主要應該學會如何根據(jù)二叉樹和樹的結構及其操作的遞歸定義編寫遞歸算法。 本章必須完成的算法設計題為: 6.1, 6.3, 6.4, 6.5, 6.6, 6.7, 6.8, 6.9, 6.10, 6.11, 6.12, 6.14, 6.16, 6.17, 6.18, 6.20, 6.21, 6.24, 6.25, 6.26,6.1 二叉樹,二、二叉樹的基本性質,一、二叉樹的定義和基本術語,三、二叉樹的存儲結構,一、二叉樹的定義和基本術語,1、二叉樹的定義 2、二叉樹的基本術語 3、二叉樹的應用舉例 4、二叉樹的基本操作,1、 二叉樹定義,二叉樹T是n

4、個結點的有限集合，其中n0,當n=0時，為空樹，否則，其中有一個結點為根結點，其余結點劃分為兩個互不相交的子集TL、TR，并且TL、TR分別構成叫作左、右子樹的二叉樹。,二叉樹或為空樹；或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成。,根結點,左子樹,右子樹,E,F,二叉樹的五種基本形態(tài)：,N,空樹,只含根結點,N,N,N,L,R,R,右子樹為空樹,L,左子樹為空樹,左右子樹均不為空樹,二叉樹的注意點,二叉樹每個結點的孩子都有左右之分，每個結點都有左右兩個子樹。,三個節(jié)點的二叉樹（五棵）,每個結點最多只有兩棵子樹(不存在度大于2的結點)； 左子樹和右子樹次序不能顛倒(有序

5、樹)。,2、基本術語,結點(node)表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支 結點的度(degree)結點擁有的子樹數(shù) 葉子(leaf)度為0的結點 孩子(child)結點子樹的根稱為該結點的孩子 雙親(parents)孩子結點的上層結點叫該結點的雙親 深度樹中結點的最大層次數(shù) 結點的層次從根結點算起，根為第一層，它的孩子為第二層，,即根結點(沒有前驅) 即上層的那個結點(直接前驅) 即下層結點的子樹的根(直接后繼) 同一雙親下的同層結點（孩子之間互稱兄弟） 即雙親位于同一層的結點（但并非同一雙親） 即從根到該結點所經(jīng)分支的所有結點 即該結點下層子樹中的任一結點,根 雙親 孩子 兄弟

6、 堂兄弟 祖先 子孫,結點A的度：3 結點B的度：2 結點M的度：0,葉子：K，L，F(xiàn)，G，M，I，J,結點A的孩子：B，C，D 結點B的孩子：E，F(xiàn),結點I的雙親：D 結點L的雙親：E,結點B，C，D為兄弟 結點K，L為兄弟,樹的度：3,結點A的層次：1 結點M的層次：4,樹的深度：4,結點F，G為堂兄弟 結點A是結點F，G的祖先,3、二叉樹的應用舉例,國際Morse碼,變色力缺陷遺傳圖 （隔代遺傳）,InitBiTree(,二叉樹的基本操作,查 找 類,插 入 類,刪 除 類,二、二叉樹的基本性質,1、層與結點數(shù) 2、深度與結點數(shù) 3、葉子與結點數(shù) 4、完全二叉樹與深度 5、完全二叉樹與結

7、點序號,1.一棵非空二叉樹的第i 層最多有2i1個結點(i1)。,證明(采用歸納法) (1).當i=1時,結論顯然正確。非空二叉樹的第1層有且僅有一個結點,即樹的根結點.,(2).假設對于第j層(1ji1)結論也正確,即第j層最多有2j-1個結點.,(3).有定義可知, 二叉樹中每個結點最多只能有兩個孩子結點。若第i1層的每個結點都有兩棵非空子樹,則第i層的結點數(shù)目達到最大. 而第i1層最多有2i2個結點已由假設證明,于是,應有22i2 = 2i1,證畢.,討論1：第i層的結點數(shù)至多是多少？ （利用二進制性質可輕松求出）,提問：第i層上至少有 個結點？,2.深度為h 的非空二叉樹最多有2h -

8、1個結點.,證明:,由性質1可知,若深度為h的二叉樹的每一層的結點數(shù)目都達到各自所在層的最大值,則二叉樹的結點總數(shù)一定達到最大。即有 20+21+22+2i-1+ +2h-1 = 2h-1,證畢.,討論2：深度為k的二叉樹，至多有多少個結點？ （利用二進制性質可輕松求出）,提問：深度為k時至少有 個結點？,3. 若非空二叉樹有n0個葉結點,有n2個度為2的結點, 則 n0=n2+1,證明: 設該二叉樹有n1個度為1的結點,結點總數(shù)為n,有 n=n0+n1+n2 -(1),設二叉樹的分支數(shù)目為B,有 B=n-1 -(2),這些分支來自度于為1的結點與度度為2結點,即 B=n1+2n2 -(3),

9、聯(lián)列關系(1),(2)與(3),可得到 n0=n2+1,證畢.,推論： n0=n2+2n3+3n4+ +(m-1)nm +1,討論3：二叉樹的葉子數(shù)和度為2的結點數(shù)之間有關系嗎？,實際意義：葉子數(shù)2度結點數(shù)1,4. 具有n個結點的完全二叉樹的深度h=log2n+1.,證明:,設 完全二叉樹的深度為 k,則根據(jù)第二條性質得 2k-1 n 2k,即 k-1 log2 n k,因為 k 只能是整數(shù)，因此， k =log2n + 1,證畢.,對于兩種特殊形式的二叉樹（滿二叉樹和完全二叉樹），還特別具備以下2個性質：,5. 若對具有n個結點的完全二叉樹按照層次從上到下,每層從 左到右的順序進行編號, 則

10、編號為i 的結點具有以下性質: (1) 當i=1, 則編號為i的結點為二叉樹的根結點; 若i1, 則編號為i 的結點的雙親結點的編號為i/2. (2) 若2in, 則編號為i 的結點無左子樹; 若2in, 則編號為i 的結點的左子樹的根的編號為2i. (3) 若2i+1n, 則編號為i 的結點無右子樹; 若2i+1n, 則編號為i 的結點的右子樹的根的編號為2i+1.,兩種特殊形態(tài)的二叉樹,解釋：完全二叉樹的特點就是，只有最后一層葉子不滿，且全部集中在左邊。 這其實是順序二叉樹的含義。在圖論概念中的“完全二叉樹”是指n1=0的情況。,為何要研究這兩種特殊形式？ 因為它們在順序存儲方式下可以復原

11、!,（特點：每層都“充滿”了結點）,三、二叉樹的存儲結構,1、順序存儲結構 2、鏈式存儲結構,1）完全二叉樹的順序存儲結構,1、二叉樹的順序存儲結構,討論：不是完全二叉樹怎么辦？,答：一律轉為完全二叉樹！ 方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結點”，其內(nèi)容為空。,A B C D E,缺點：浪費空間；插入、刪除不便,1、二叉樹的順序存儲結構,2）一般二叉樹的順序存儲結構,1、二叉樹的順序存儲結構,例如,#define MAX_TREE_SIZE 100 / 二叉樹的最大結點數(shù) typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0號單元存儲根結點 SqBiTre

12、e bt;,1、二叉樹的順序存儲結構,用二叉鏈表即可方便表示。,二叉樹結點數(shù)據(jù)類型定義： typedef struct node *tree_pointer; typedef struct Binode TElemType data; struct BiNode *lchild, *rchild; BiTNode， *BiTree;,一般從根結點開始存儲。（相應地，訪問樹中結點時也只能從根開始） 注：如果需要倒查某結點的雙親，可以再增加一個雙親域（直接前趨）指針，將二叉鏈表變成三叉鏈表。,存儲結點值的數(shù)據(jù)域data,指向右孩子結點的指針,指向左孩子結點的指針,2、二叉樹的鏈式存儲結構,2、二叉

13、樹的鏈式存儲結構,例：,2、二叉樹的鏈式存儲結構,二叉樹的鏈式存儲結構(二叉鏈表),2、二叉樹的鏈式存儲結構,空指針個數(shù)： 2*n0+1*n1+0*n2 =2n0+n1 =n0+n1+n0 =n0+n1+n2+1 =n+1,在n個結點的二叉鏈表中，有n+1個空指針域,6.2 二叉樹的遍歷,二、遍歷算法,一、二叉樹的遍歷,四、線索二叉樹,三、遍歷應用舉例,一. 二叉樹的遍歷,例如：,先序序列：,中序序列：,后序序列：,A B C D E F G H K,B D C A E H G K F,D C B H K G F E A,1、先序遍歷,前序序列:,A,B,D,E,J,C,F,I,G,-,*,A

14、,B,C,先序遍歷 - * A B C,1、前序遍歷,中序序列:,D,B,J,E,A,F,I,C,G,2、中序遍歷,-,*,A,B,C,中序遍歷 A * B - C,2、中序遍歷,后序序列:,D,J,E,B,I,F,G,C,A,3、后序遍歷,-,*,A,B,C,后序遍歷 A B * C -,3、后序遍歷,先序遍歷：,中序遍歷：,后序遍歷：,層次遍歷：,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,-,+,a,*,b,-,c,d,/,e,f,例：用二叉樹表示算術表達式,先序遍歷 + * * / A B C D

15、E 前綴表示 中序遍歷 A / B * C * D + E 中綴表示 后序遍歷 A B / C * D * E + 后綴表示 層序遍歷 + * E * D / C A B,例：用二叉樹表示算術表達式,三、遍歷算法,1、先序遍歷 2、中序遍歷 3、后序遍歷 4、無遞歸中序遍歷,按層次遍歷,按層次遍歷序列: A, B, C, D, E, F, G, J, I,void pre( BiTree T，void(*visit)( BiTree ) ) if (T) visit(T); pre( T-lchild, visit ); pre( T-rchild, visit ); ,返回,返回,返回,返回

16、,A,C,B,D,返回,先序序列：A B D C,遍歷算法的執(zhí)行過程-例題說明,模擬算法對如圖所示二叉樹的中序遍歷的執(zhí)行過程。,輸出序列 CBEDFAHG,4、非遞歸算法,typedef enum Travel, Visit TaskType; / Travel = 1:遍歷， / Visit = 0:訪問 typedef struct BiTree ptr; / 指向根結點的指針 TaskType task; / 任務性質 ElemType;,“遍歷左子樹”,“遍歷右子樹”,“訪問根結點”,4、中序遍歷算法的非遞歸描述,在寫算法之前首先需定義棧的元素類型。,void InOrder_iter

17、( BiTree BT ) / 利用棧實現(xiàn)中序遍歷二叉樹，T為指向二叉樹的根結點的頭指針 InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); / 布置初始任務 while(!StackEmpty(S) Pop(S,e); / 每次處理一項任務 if (e.task=Visit) visit(e.ptr); / 處理訪問任務 else if ( !e.ptr ) / 處理非空樹的遍歷任務 p=e.ptr; e.ptr=p-rchild; Push(S,e); / 最不迫切任務進棧 e.ptr=p; e.task=Visit; Pus

18、h(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); /if /while /InOrder_iter,e.ptr=BT; e.task=Travel; if(BT) Push(S, e);,e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) P

19、ush(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Pu

20、sh(S,e);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,void In

21、Order_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,輸出 B,if(e.task=Visit) v

22、isit(e.ptr);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,輸出

23、B,e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild;

24、 Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,輸出 B,e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEm

25、pty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,輸出 B,輸出 E,if(e.task=Visit) visit(e.ptr);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) P

26、ush(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,輸出 D,輸出 BE,if(e.task=Visit) visit(e.ptr);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=B

27、T; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,輸出 A,輸出 BED,if(e.task=Visit) visit(e.ptr);,void InOrder_iter( BiTree

28、 BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,輸出 BEDA,e.ptr=p-rchild; Push(S,e); e.ptr=

29、p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e); e.ptr=p; e.task=Visit;

30、Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,輸出 BEDA,輸出 C,if(e.task=Visit) visit(e.ptr);,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S

31、,e); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,輸出 BEDAC,OVER,void InOrder_iter( BiTree BT ) InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); while(!StackEmpty(S) Pop(S,e); if (e.task=Visit) visit(e.ptr); else if ( !e.ptr ) p=e.ptr; e.ptr=p-rchild; Push(S,e

32、); e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); ,四、遍歷算法的應用舉例,2、求二叉樹的深度(后序遍歷),1、建立二叉樹的存儲結構,4、計算表達式的值,3、復制二叉樹(后序遍歷),1、建立二叉樹的存儲結構,不同的定義方法相應有不同的存儲結構的建立算法,(1) 以字符串的形式“根-左子樹-右子樹”定義一棵二叉樹,例如:,按先序遍歷序列建立二叉樹的二叉鏈表. 已知先序序列為： A B C D E G F ,Status CreateBiTree(BiTree / CreateBiTree,

33、A B C D,A,B,C,D,void CreatebiTree(BiTree / 遞歸建(遍歷)右子樹 /else /CreateBiTree,2、求二叉樹的深度(后序遍歷),算法基本思想:首先分析二叉樹的深度和它的左、右子樹深度之間的關系。,從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中訪問結點的操作為:求得左、右子樹深度的最大值，然后加1 。,int Depth (BiTree T ) / 返回二叉樹的深度 if (!T) depthval = 0; else depthLeft = Depth( T-lchild );

34、 depthRight= Depth( T-rchild ); depthval = 1+(depthLeftdepthRight?depthLeft:depthRight); return depthval; ,void Depth(BiTree T , int level, int /調用之前 level 的初值為 1, dval 的初值為 0.,void BiTreeDepth(BiTree T, int h, int /BiTreeDepth 主函數(shù)調用： d=0 BiTreeDepth(r,1,d),int BiTreeDepth(BiTree T) / 后序遍歷求T所指二叉樹的深度

35、 if (!T) return 0; else hL=BiTreeDepth(T-lchild); hR=BiTreeDepth(T-rchild); if (hL=hR) return hL+1; else return hR+1; /BiTreeDepth,例如，下列二叉樹的復制過程如下：,newT,3、復制二叉樹(后序遍歷),BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = new BiTNode) exit(1); T- data = item; T- lchild = lptr

36、; T- rchild = rptr; return T; ,生成一個二叉樹的結點(其數(shù)據(jù)域為item,左指針域為lptr,右指針域為rptr),BiTNode *CopyTree(BiTNode *T) if (!T) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild); /復制左子樹 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild); /復制右子樹 else newrptr = NULL; newT = GetTreeNode(T-data, new

37、lptr, newrptr); return newT; / CopyTree,4、計算表達式的值 (a+b*(c-d)-e/f,3.1 4.2 2.4 3.8 7.2 2.4,abcd-*+ef/- （后綴表達式）,opnd,0 1 2 3 4 5,數(shù)據(jù)結構的表示,a+b,(a+b)c d/e,a+bc,表達式的二叉樹的表示:,a,b,+,a,b,c,+,a,b,c,+,(a+b)c,a,b,c,d,e,-,+,/,特點： 操作數(shù)為葉子結點 運算符為分支結點,例右圖所示的二叉樹表達式 (a+b*(c-d)-e/f 若先序遍歷此二叉樹,按訪問結點的先后次序將結點排列起來,其先序序列為： -+a

38、*b-cd/ef （前綴表達式） 按中序遍歷,其中序序列為： a+b*c-d-e/f （中綴表達式） 按后序遍歷,其后序序列為： abcd-*+ef/- （后綴表達式）,double value(BiTree T, float opnd) / 對以T為根指針的二叉樹表示的算術表達式求值， / 操作數(shù)的數(shù)值存放在一維數(shù)組opnd中 if (!T) return 0; / 空樹的值為0 if (T-data=0) return opndT-data; Lv = value(T-lchild,opnd); / 遍歷左子樹求第一操作數(shù) Rv = value(T-rchild,opnd); / 遍歷右子

39、樹求第二操作數(shù) switch (T-data) case PLUS: v = Lv + Rv; case MINUS: v = Lv - Rv; case ASTERISK: v = LV * Rv; case SLANT: v = Lv / Rv; default: ERROR(不合法的運算符); /switch return v; /value,習題討論：,1. 求二叉樹深度，或從x結點開始的子樹深度。 算法思路：只查各結點后繼鏈表指針，若左(右)孩子的左(右)指針非空，則層次數(shù)加1；否則函數(shù)返回。 技巧：遞歸時應當從葉子開始向上計數(shù)，層深者保留。否則不易確定層數(shù)。 2. 按層次輸出二叉樹

40、中所有結點。 算法思路：既然要求從上到下，從左到右，則利用隊列存放各子樹結點的指針是個好辦法，而不必拘泥于遞歸算法。 技巧：當根結點入隊后，令其左、右孩子結點入隊，而左孩子出隊時又令它的左右孩子結點入隊，由此便可產(chǎn)生按層次輸出的效果。,3 中序遍歷的非遞歸(迭代)算法 算法思路：若不用遞歸，則要實現(xiàn)二叉樹遍歷的“嵌套”規(guī)則，必用堆棧?？芍苯佑脀hile語句和push/pop操作。 4.判別給定二叉樹是否為完全二叉樹（即順序二叉樹）。 算法思路：完全二叉樹的特點是：沒有左子樹空而右子樹單獨存在的情況(前k-1層都是滿的，且第k層左邊也滿）。 技巧:按層序遍歷方式，先把所有結點（不管當前結點是否有

41、左右孩子）都入隊列.若為完全二叉樹,則層序遍歷時得到的肯定是一個連續(xù)的不包含空指針的序列.如果序列中出現(xiàn)了空指針，則說明不是完全二叉樹。,三、線索二叉樹,1、何謂線索二叉樹？ 2、線索鏈表的遍歷算法 3、如何建立線索鏈表？,1）什么是線索二叉樹,2）線索二叉樹的構造,1、何謂線索二叉樹？,線索二叉樹（Threaded Binary Tree）的理解,普通二叉樹只能找到結點的左右孩子信息，而該結點的直接前驅和直接后繼只能在遍歷過程中獲得。 若將遍歷后對應的有關前驅和后繼預存起來，則從第一個結點開始就能很快“順藤摸瓜”而遍歷整個樹了。,存放前驅指針,存放后繼指針,如何預存這類信息？,例如中序遍歷結

42、果：B D C E A F H G，實際上已將二叉樹轉為線性排列，顯然具有唯一前驅和唯一后繼！,可能是根、或最左（右）葉子,指向該線性序列中的“前驅”和 “后繼” 的指針，稱作“線索”,與其相應的二叉樹，稱作 “線索二叉樹”,包含 “線索” 的存儲結構，稱作 “線索鏈表”,A B C D E F G H K, D ,C , B,E ,規(guī) 定：,1）若結點有左子樹，則lchild指向其左孩子； 否則，lchild指向其直接前驅(即線索)；,2）若結點有右子樹，則rchild指向其右孩子； 否則，rchild指向其直接后繼(即線索) 。,為了避免混淆，增加兩個標志域，如下圖所示：,約定:,當Tag

43、域為0時,表示正常情況;,當Tag域為1時,表示線索情況.,注：在線索化二叉樹中，并不是每個結點都能直接找到其后繼的，當標志為0時，則需要通過一定運算才能找到它的后繼。,線索鏈表：用前頁結點結構所構成的二叉鏈表 線索：指向結點前驅和后繼的指針 線索二叉樹：加上線索的二叉樹（圖形式樣） 線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程,A,G,E,I,D,J,H,C,F,B,例：帶了兩個標志的某先序遍歷結果如表所示，請畫出對應二叉樹。,懸空？,懸空？,解：該二叉樹中序遍歷結果為:H, D, I, B, E, A, F, C, G 所以添加線索應當按如下路徑進行：,例：畫出以下二叉樹對應的中

44、序線索二叉樹。,為避免懸空態(tài)，應增設一個頭結點,typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指針 PointerThr LTag, RTag; / 左右標志 BiThrNode, *BiThrTree;,3）線索鏈表的類型描述,typedef enum Link, Thread PointerThr; / Link=0:指針，Thread=1:線索,對應的中序線索二叉樹存儲結構如圖所示：,注：此圖中序遍歷結果為: H, D, I, B, E, A, F, C, G,中序遍歷的第一個

45、結點?,在中序線索化鏈表中結點的后繼?,左子樹上處于“最左下”（沒有左子樹）的結點,若無右子樹，則為后繼線索所指結點,否則為對其右子樹進行中序遍歷時訪問的第一個結點,2、線索二叉樹的遍歷,按中序線索化二叉樹 遍歷中序線索二叉樹,在中序線索二叉樹中找結點后繼的方法： （1）若rt=1, 則rc域直接指向其后繼 （2）若rt=0, 則結點的后繼應是其右子樹的左鏈尾（lt=1)的結點,void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / p指向根結點 while (p != T) / 空樹或遍

46、歷結束時，p=T while (p-LTag=Link) p = p-lchild; / 第一個結點 while (p-RTag=Thread / p進至其右子樹根 / InOrderTraverse_Thr,3、線索二叉樹的生成,線索化過程就是在遍歷過程中修改空指針的過程： 將空的lchild改為結點的直接前驅； 將空的rchild改為結點的直接后繼。,非空指針呢？仍然指向孩子結點（稱為“正常情況”）,目的：在依某種順序遍歷二叉樹時修改空指針，添加前驅或后繼。,注解：為方便添加結點的前驅或后繼，需要設置兩個指針： p指針當前結點之指針； pre指針前驅結點之指針。,技巧：當結點p的左/右域為

47、空時，只改寫它的左域(裝入前驅pre), 而其右域（后繼）留給下一結點來填寫。 或者說，當前結點的指針p應當送到前驅結點的空右域中。,若p-lchildNULL,則p-Ltag=1;p-lchildpre; /p的前驅結點指針pre存入左空域 若pre-rchildNULL, 則pre-Rtag1;pre-rchild=p; /p存入其前驅結點pre的右空域,線索二叉樹的生成算法,在中序遍歷過程中修改結點的左、右指針域，以保存當前訪問結點的“前驅”和“后繼”信息。遍歷過程中，附設指針pre, 并始終保持指針pre指向當前訪問的、指針p所指結點的前驅。,void InOrderThreading

48、(BiThrTree ,void InThreading(BiThrTree p, BiThrTree ,6.3 樹和森林,一、樹和森林的定義 二、樹和森林的存儲結構 三、樹和森林的的遍歷,一、樹和森林的定義,1、樹的定義 2、森林的定義 3、對樹和森林的操作,1、樹的基本概念,注1：過去許多書籍中都定義樹為n1，曾經(jīng)有“空樹不是樹”的說法，但現(xiàn)在樹的定義已修改。 注2：樹的定義具有遞歸性，即樹中還有樹。,1. 有且僅有一個結點沒有前驅結點,該結點為樹的根結點。,2. 除了根結點外,每個結點有且僅有一個直接前驅結點。,3. 包括根結點在內(nèi)，每個結點可以有多個后繼結點。,根,子樹,任何一棵非空樹

49、是一個二元組 Tree = （root，F(xiàn)） 其中：root 被稱為根結點， F 被稱為子樹森林,2、森林,是 m（m0）棵互 不相交的樹的集合,A,root,F,3、樹的表示法,圖形表示法 嵌套集合表示法 廣義表表示法 目錄表示法 左孩子右兄弟表示法,1）圖形表示法,華中師范大學,葉子,根,子樹,2）廣義表表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作為由子樹森林組成的表的名字寫在表的左邊,麻煩問題：應當開設多少個鏈域?,A( ),樹根,B(E, F(K, L),C(G),D(H, I, J(M),例如:,3）

50、左孩子右兄弟表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ),Root(T) / 求樹的根結點,查找類：,Value(T, cur_e) / 求當前結點的元素值,Parent(T, cur_e) / 求當前結點的雙親結點,LeftChild(T, cur_e) / 求當前結點的最左孩子,RightSibling(T, cur_e) / 求當前結點的右兄弟,TreeEmpty(T) / 判定樹是否為空樹,TreeDepth(T) / 求樹的深度,TraverseTree( T, Visit() ) / 遍歷,4、樹的操

51、作,InitTree( int parent; / 雙親位置域 PTNode; 樹結構: typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根結點的位置和結點個數(shù) PTree;,思路：將每個結點的孩子排列起來，形成一個帶表頭（裝父結點）的線性表（n個結點要設立n個鏈表）； 再將n個表頭用數(shù)組存放起來，這樣就形成一個混合結構。,例如：,2、孩子鏈表表示法,C語言的類型描述:,孩子結點結構 typedef struct CTNode int child; struct CTNode *next; *ChildPtr; 雙親結點結構 typ

52、edef struct Elem data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox; 樹結構 typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 結點數(shù)和根結點的位置 CTree;,思路：用二叉鏈表來表示樹，但鏈表中的兩個指針域含義不同。 左指針指向該結點的第一個孩子； 右指針指向該結點的下一個兄弟結點。,3、用孩子兄弟表示法來存儲,指向左孩子,指向右兄弟,root,3、樹的二叉鏈表 (孩子-兄弟）表示法,root,C語言的類型描述,結點結構 typedef struct CSNode Elem data

53、; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree,1）森林到二叉樹的轉換-方法,如果森林用有序表T=(T1，T2，Tm)來表示，則將森林T轉換為對應的二叉樹BT的形式化描述如下： 如果m=0，則BT為空；否則依次作如下操作： 將T1的根作為BT的根； 將T1的子樹森林轉換為BT的左子樹； 將(T2，T3，Tm)轉換為BT的右子樹。,4、森林、樹和二叉樹的轉換,1）森林轉二叉樹,兄弟相連 長兄為父 孩子靠左 頭根為根,A,將各棵樹分別轉換成二叉樹 將每棵樹的根結點用線相連 以第一棵樹根結點為二叉樹的根，再以根結點為軸心，順時針旋

54、轉，構成二叉樹型結構,2）二叉樹到森林的轉換,將二叉樹BT轉換為森林T(T1，T2Tm)的形式化描述如下： 若BT不空，則依次執(zhí)行如下操作： 將BT的根轉換為T1的根； 將BT的左子樹轉換為T1的子樹森林； 將BT的右子樹轉換為（T2，Tm）,2）二叉樹轉換成森林 抹線：將二叉樹中根結點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹 還原：將孤立的二叉樹還原成樹,3）將樹轉換成二叉樹 加線：在兄弟之間加一連線 抹線：對每個結點，除了其左孩子外，去除其與其余孩子之間的關系 旋轉：以樹的根結點為軸心，將整樹順時針轉45,樹轉換成的二叉樹其右子樹一定為空,4）將二叉

55、樹轉換成樹 加線：若p結點是雙親結點的左孩子，則將p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都與p的雙親用線連起來 抹線：抹掉原二叉樹中雙親與右孩子之間的連線 調整：將結點按層次排列，形成樹結構,樹與二叉樹轉換,三、樹和森林的遍歷,1、樹的遍歷 2、森林的遍歷 3、樹的遍歷舉例,樹和森林的遍歷,先序遍歷 訪問根結點； 依次先序遍歷根結點的每棵子樹。,1、樹的遍歷,例如：,先序序列：,后序序列：,a b c d e,b d c e a,后序遍歷 依次后序遍歷根結點的每棵子樹； 訪問根結點。,樹沒有中序遍歷（因子樹不分左右）,按層次遍歷: 若樹不空，則自上而下自左至右訪問樹中每個結點。,

56、層次遍歷時頂點的訪問次序：,先根遍歷時頂點的訪問次序：,A B E F C D G H I J K,后根遍歷時頂點的訪問次序：,E F B C I J K H G D A,A B C D E F G H I J K,1）樹（森林）的遍歷-先序遍歷,先序遍歷森林T=(T1，T2Tm)的描述如下： 若T不空，則依次執(zhí)行如下操作： 訪問T1的根； 先序遍歷T1的子樹森林； 先序遍歷森林（T2，T3Tm）； void preorder(Tnode *t) /先序遍歷森林 if (t!=NULL) visite(t); /訪問結點 preorder(t-firstson); /先序遍歷t的子樹森林 pr

57、eorder(t-nextbrother); /先序遍歷t的兄弟森林 ,2）樹（森林）的遍歷-后序遍歷,后序遍歷森林T=(T1，T2Tm)的方法描述如下： 如果T不空，則依次執(zhí)行如下操作： 后序遍歷T1的子樹森林； 訪問T1的根； 后序遍歷森林（T2，T3Tm）； void postorder(Tnode *t) if (t!=NULL) postorder(t-firstson); /后序遍歷樹t的子樹森林 visite(t); /訪問樹t的根結點 postorder(t-nextbrother); /后序遍歷t的后續(xù)兄弟森林 ,討論：若采用先轉換后遍歷方式，結果是否一樣？,d e c b a,a b c d e,b d c e a,1. 樹的先序遍歷二法相同； 2. 樹的后序遍歷相當于對應二叉樹的中序遍歷； 3. 樹沒有中序遍歷，因為子樹無左右之分。,結論：