華師本科生數(shù)據(jù)結(jié)構(gòu)課件 第6章 二叉樹和樹

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

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

3、點(diǎn)，也是整個(gè)課程中的一大難點(diǎn)。在本章的學(xué)習(xí)過程中主要應(yīng)該學(xué)會如何根據(jù)二叉樹和樹的結(jié)構(gòu)及其操作的遞歸定義編寫遞歸算法。 本章必須完成的算法設(shè)計(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 二叉樹,二、二叉樹的基本性質(zhì),一、二叉樹的定義和基本術(shù)語,三、二叉樹的存儲結(jié)構(gòu),一、二叉樹的定義和基本術(shù)語,1、二叉樹的定義 2、二叉樹的基本術(shù)語 3、二叉樹的應(yīng)用舉例 4、二叉樹的基本操作,1、 二叉樹定義,二叉樹T是n

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

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

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

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

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

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

10、編號為i 的結(jié)點(diǎn)具有以下性質(zhì): (1) 當(dāng)i=1, 則編號為i的結(jié)點(diǎn)為二叉樹的根結(jié)點(diǎn); 若i1, 則編號為i 的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為i/2. (2) 若2in, 則編號為i 的結(jié)點(diǎn)無左子樹; 若2in, 則編號為i 的結(jié)點(diǎn)的左子樹的根的編號為2i. (3) 若2i+1n, 則編號為i 的結(jié)點(diǎn)無右子樹; 若2i+1n, 則編號為i 的結(jié)點(diǎn)的右子樹的根的編號為2i+1.,兩種特殊形態(tài)的二叉樹,解釋：完全二叉樹的特點(diǎn)就是，只有最后一層葉子不滿，且全部集中在左邊。 這其實(shí)是順序二叉樹的含義。在圖論概念中的“完全二叉樹”是指n1=0的情況。,為何要研究這兩種特殊形式？ 因?yàn)樗鼈冊陧樞虼鎯Ψ绞较驴梢詮?fù)原

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

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

13、樹的鏈?zhǔn)酱鎯Y(jié)構(gòu),例：,2、二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu),二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)(二叉鏈表),2、二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu),空指針個(gè)數(shù)： 2*n0+1*n1+0*n2 =2n0+n1 =n0+n1+n0 =n0+n1+n2+1 =n+1,在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域,6.2 二叉樹的遍歷,二、遍歷算法,一、二叉樹的遍歷,四、線索二叉樹,三、遍歷應(yīng)用舉例,一. 二叉樹的遍歷,例如：,先序序列：,中序序列：,后序序列：,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,例：用二叉樹表示算術(shù)表達(dá)式,先序遍歷 + * * / A B C D

15、E 前綴表示 中序遍歷 A / B * C * D + E 中綴表示 后序遍歷 A B / C * D * E + 后綴表示 層序遍歷 + * E * D / C A B,例：用二叉樹表示算術(shù)表達(dá)式,三、遍歷算法,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; / 指向根結(jié)點(diǎn)的指針 TaskType task; / 任務(wù)性質(zhì) ElemType;,“遍歷左子樹”,“遍歷右子樹”,“訪問根結(jié)點(diǎn)”,4、中序遍歷算法的非遞歸描述,在寫算法之前首先需定義棧的元素類型。,void InOrder_iter

17、( BiTree BT ) / 利用棧實(shí)現(xiàn)中序遍歷二叉樹，T為指向二叉樹的根結(jié)點(diǎn)的頭指針 InitStack(S); e.ptr=BT; e.task=Travel; if (T) Push(S, e); / 布置初始任務(wù) while(!StackEmpty(S) Pop(S,e); / 每次處理一項(xiàng)任務(wù) if (e.task=Visit) visit(e.ptr); / 處理訪問任務(wù) else if ( !e.ptr ) / 處理非空樹的遍歷任務(wù) p=e.ptr; e.ptr=p-rchild; Push(S,e); / 最不迫切任務(wù)進(jìn)棧 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); ,四、遍歷算法的應(yīng)用舉例,2、求二叉樹的深度(后序遍歷),1、建立二叉樹的存儲結(jié)構(gòu),4、計(jì)算表達(dá)式的值,3、復(fù)制二叉樹(后序遍歷),1、建立二叉樹的存儲結(jié)構(gòu),不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法,(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、求二叉樹的深度(后序遍歷),算法基本思想:首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系。,從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中訪問結(jié)點(diǎn)的操作為:求得左、右子樹深度的最大值，然后加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 /調(diào)用之前 level 的初值為 1, dval 的初值為 0.,void BiTreeDepth(BiTree T, int h, int /BiTreeDepth 主函數(shù)調(diào)用： 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,例如，下列二叉樹的復(fù)制過程如下：,newT,3、復(fù)制二叉樹(后序遍歷),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; ,生成一個(gè)二叉樹的結(jié)點(diǎn)(其數(shù)據(jù)域?yàn)閕tem,左指針域?yàn)閘ptr,右指針域?yàn)閞ptr),BiTNode *CopyTree(BiTNode *T) if (!T) return NULL; if (T-lchild ) newlptr = CopyTree(T-lchild); /復(fù)制左子樹 else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild); /復(fù)制右子樹 else newrptr = NULL; newT = GetTreeNode(T-data, new

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

38、*b-cd/ef （前綴表達(dá)式） 按中序遍歷,其中序序列為： a+b*c-d-e/f （中綴表達(dá)式） 按后序遍歷,其后序序列為： abcd-*+ef/- （后綴表達(dá)式）,double value(BiTree T, float opnd) / 對以T為根指針的二叉樹表示的算術(shù)表達(dá)式求值， / 操作數(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(不合法的運(yùn)算符); /switch return v; /value,習(xí)題討論：,1. 求二叉樹深度，或從x結(jié)點(diǎn)開始的子樹深度。 算法思路：只查各結(jié)點(diǎn)后繼鏈表指針，若左(右)孩子的左(右)指針非空，則層次數(shù)加1；否則函數(shù)返回。 技巧：遞歸時(shí)應(yīng)當(dāng)從葉子開始向上計(jì)數(shù)，層深者保留。否則不易確定層數(shù)。 2. 按層次輸出二叉樹

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

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

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

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

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

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

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

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

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

49、是一個(gè)二元組 Tree = （root，F(xiàn)） 其中：root 被稱為根結(jié)點(diǎn)， F 被稱為子樹森林,2、森林,是 m（m0）棵互 不相交的樹的集合,A,root,F,3、樹的表示法,圖形表示法 嵌套集合表示法 廣義表表示法 目錄表示法 左孩子右兄弟表示法,1）圖形表示法,華中師范大學(xué),葉子,根,子樹,2）廣義表表示法,( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作為由子樹森林組成的表的名字寫在表的左邊,麻煩問題：應(yīng)當(dāng)開設(shè)多少個(gè)鏈域?,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) / 求樹的根結(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() ) / 遍歷,4、樹的操

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

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

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

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

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

56、層次遍歷時(shí)頂點(diǎn)的訪問次序：,先根遍歷時(shí)頂點(diǎn)的訪問次序：,A B E F C D G H I J K,后根遍歷時(shí)頂點(diǎn)的訪問次序：,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); /訪問結(jié)點(diǎn) 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的根結(jié)點(diǎn) postorder(t-nextbrother); /后序遍歷t的后續(xù)兄弟森林 ,討論：若采用先轉(zhuǎn)換后遍歷方式，結(jié)果是否一樣？,d e c b a,a b c d e,b d c e a,1. 樹的先序遍歷二法相同； 2. 樹的后序遍歷相當(dāng)于對應(yīng)二叉樹的中序遍歷； 3. 樹沒有中序遍歷，因?yàn)樽訕錈o左右之分。,結(jié)論：