數(shù)據(jù)結(jié)構(gòu)6.ppt

1、第六章 樹和二叉樹,6.1 樹的類型定義,6.2 二叉樹的類型定義,6.3 二叉樹的存儲結(jié)構(gòu),6.4 二叉樹的遍歷,6.5 線索二叉樹,6.6 樹和森林的表示方法,6.7 樹和森林的遍歷,6.8 哈夫曼樹與哈夫曼編碼,6.1 樹的類型定義,數(shù)據(jù)對象 D：,D是具有相同特性的數(shù)據(jù)元素的集合。,若D為空集，則稱為空樹； 否則: (1) 在D中存在唯一的稱為根的數(shù)據(jù)元素root, (2) 當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m (m0)個(gè)互 不相交的有限集T1, T2, , Tm, 其中每一 棵子集本身又是一棵符合本定義的樹， 稱為根root的子樹。,數(shù)據(jù)關(guān)系 R：,基本操作：,查 找 類,插 入 類,刪 除

2、類,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( Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); L

3、eftSibling(T, e); RightSibling(T, e); BiTreeEmpty(T); BiTreeDepth(T); PreOrderTraverse(T, Visit(); InOrderTraverse(T, Visit(); PostOrderTraverse(T, Visit(); LevelOrderTraverse(T, Visit();,InitBiTree(,ClearBiTree(,二叉樹的重要特性,性質(zhì) 1 ： 在二叉樹的第 i 層上至多有2i-1 個(gè)結(jié)點(diǎn)。 (i1),用歸納法證明： 歸納基： 歸納假設(shè)： 歸納證明：,i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)，

4、 2i-1 = 20 = 1；,假設(shè)對所有的 j，1 j i，命題成立;,二叉樹上每個(gè)結(jié)點(diǎn)至多有兩棵子樹， 則第 i 層的結(jié)點(diǎn)數(shù) = 2i-2 2 = 2i-1 。,性質(zhì) 2 ： 深度為 k 的二叉樹上至多含 2k-1 個(gè)結(jié)點(diǎn)（k1）,證明：,基于上一條性質(zhì)，深度為 k 的二叉樹上的結(jié)點(diǎn)數(shù)至多為 20+21+ +2k-1 = 2k-1,性質(zhì) 3 ： 對任何一棵二叉樹，若它含有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 = n1 + 2n2,而 b = n-1 = n0

5、+ n1 + n2 - 1,由此， n0 = n2 + 1,兩類特殊的二叉樹：,滿二叉樹：指的是深度為k且含有2k-1個(gè)結(jié)點(diǎn)的二叉樹。,完全二叉樹：樹中所含的 n 個(gè)結(jié)點(diǎn)和滿二叉樹中編號為 1 至 n 的結(jié)點(diǎn)一一對應(yīng)。,性質(zhì) 4 ： 具有 n 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2n +1,證明：,設(shè) 完全二叉樹的深度為 k,則根據(jù)第二條性質(zhì)得 2k-1 n 2k,即 k-1 log2 n k,因?yàn)?k 只能是整數(shù)，因此， k =log2n + 1,性質(zhì) 5 ：,若對含 n 個(gè)結(jié)點(diǎn)的完全二叉樹從上到下且從左至右進(jìn)行 1 至 n 的編號，則對完全二叉樹中任意一個(gè)編號為 i 的結(jié)點(diǎn)：(1) 若 i=

6、1，則該結(jié)點(diǎn)是二叉樹的根，無雙親, 否則，編號為 i/2 的結(jié)點(diǎn)為其雙親結(jié)點(diǎn); (2) 若 2in，則該結(jié)點(diǎn)無左孩子， 否則，編號為 2i 的結(jié)點(diǎn)為其左孩子結(jié)點(diǎn)；(3) 若 2i+1n，則該結(jié)點(diǎn)無右孩子結(jié)點(diǎn)， 否則，編號為2i+1 的結(jié)點(diǎn)為其右孩子結(jié)點(diǎn)。,6.3 二叉樹的存儲結(jié)構(gòu),二、二叉樹的鏈?zhǔn)?存儲表示,一、 二叉樹的順序 存儲表示,#define MAX_TREE_SIZE 100 / 二叉樹的最大結(jié)點(diǎn)數(shù) typedef TElemType SqBiTreeMAX_TREE_SIZE; / 0號單元存儲根結(jié)點(diǎn) SqBiTree bt;,一、 二叉樹的順序存儲表示,例如:,1,4,0,13

7、,2,6,二、二叉樹的鏈?zhǔn)酱鎯Ρ硎?1. 二叉鏈表,2三叉鏈表,3雙親鏈表,4線索鏈表,root,結(jié)點(diǎn)結(jié)構(gòu):,1. 二叉鏈表,typedef struct BiTNode / 結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指針 BiTNode, *BiTree;,結(jié)點(diǎn)結(jié)構(gòu):,C 語言的類型描述如下:,root,2三叉鏈表,結(jié)點(diǎn)結(jié)構(gòu):,typedef struct TriTNode / 結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指針 struc

8、t TriTNode *parent; /雙親指針 TriTNode, *TriTree;,結(jié)點(diǎn)結(jié)構(gòu):,C 語言的類型描述如下:,結(jié)點(diǎn)結(jié)構(gòu):,3雙親鏈表,LRTag,L R R R L,typedef struct BPTNode / 結(jié)點(diǎn)結(jié)構(gòu) TElemType data; int *parent; / 指向雙親的指針 char LRTag; / 左、右孩子標(biāo)志域 BPTNode typedef struct BPTree / 樹結(jié)構(gòu) BPTNode nodesMAX_TREE_SIZE; int num_node; / 結(jié)點(diǎn)數(shù)目 int root; / 根結(jié)點(diǎn)的位置 BPTree,6.4

9、二叉樹的遍歷,一、問題的提出,二、先左后右的遍歷算法,三、算法的遞歸描述,四、中序遍歷算法的非遞歸描述,四、遍歷算法的應(yīng)用舉例,順著某一條搜索路徑巡訪二叉樹 中的結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)均被訪問一 次，而且僅被訪問一次。,一、問題的提出,“訪問”的含義可以很廣，如：輸出結(jié) 點(diǎn)的信息等。,“遍歷”是任何類型均有的操作， 對線性結(jié)構(gòu)而言，只有一條搜索路 徑(因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼)， 故不需要另加討論。而二叉樹是非 線性結(jié)構(gòu)，,每個(gè)結(jié)點(diǎn)有兩個(gè)后繼， 則存在如何遍歷即按什么樣的搜索 路徑進(jìn)行遍歷的問題。,對“二叉樹”而言，可以有三條搜索路徑：,1先上后下的按層次遍歷； 2先左（子樹）后右（子樹）的遍歷

10、； 3先右（子樹）后左（子樹）的遍歷。,二、先左后右的遍歷算法,先（根）序的遍歷算法,中（根）序的遍歷算法,后（根）序的遍歷算法,根,左 子樹,右 子樹,根,根,根,根,根,若二叉樹為空樹，則空操作；否則， （1）訪問根結(jié)點(diǎn)； （2）先序遍歷左子樹； （3）先序遍歷右子樹。,先（根）序的遍歷算法：,若二叉樹為空樹，則空操作；否則， （1）中序遍歷左子樹； （2）訪問根結(jié)點(diǎn)； （3）中序遍歷右子樹。,中（根）序的遍歷算法：,若二叉樹為空樹，則空操作；否則， （1）后序遍歷左子樹； （2）后序遍歷右子樹； （3）訪問根結(jié)點(diǎn)。,后（根）序的遍歷算法：,例如：,先序序列：,中序序列：,后序序列：,A

11、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,三、算法的遞歸描述,void Preorder (BiTree T, void( *visit)(TElemType/ 遍歷右子樹 ,四、中序遍歷算法的非遞歸描述,有兩種分析(描述)方法:,一、“任務(wù)書”分析方法,二、“路徑”分析方法,在寫算法之前首先需定義棧的元素類型。 typedef enum Travel, Visit TaskType; / Travel = 1:遍歷， / Visit = 0:訪問 typedef struct BiTree ptr; / 指向根結(jié)點(diǎn)的指針 Task

12、Type task; / 任務(wù)性質(zhì) ElemType;,“遍歷二叉樹”包括三項(xiàng)子任務(wù):,“遍歷左子樹”,“遍歷右子樹”,“訪問根結(jié)點(diǎn)”,void InOrder_iter( 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) / 處理非

13、空樹的遍歷任務(wù) p=e.ptr; e.ptr=p-rchild; Push(S,e);/ 最不迫切任務(wù)進(jìn)棧 e.ptr=p; e.task=Visit; Push(S,e); e.ptr=p-lchild; e.task=Travel; Push(S,e); /if /while /InOrder_iter,void Inorder_I(BiTree T, void (*visit) (TelemType / ?？毡砻鞅闅v結(jié)束 / while / Inorder_I,t = GoFarLeft(t-rchild, S);,BiTNode *GoFarLeft(BiTree T, Stack *

14、S) if (!T ) return NULL; while (T-lchild ) Push(S, T); T = T-lchild; return T; ,四、遍歷算法的應(yīng)用舉例,2、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù),3、求二叉樹的深度(后序遍歷),4、復(fù)制二叉樹(后序遍歷),5、建立二叉樹的存儲結(jié)構(gòu),1、查詢二叉樹中某個(gè)結(jié)點(diǎn),1. 在二叉樹不空的前提下,和根結(jié)點(diǎn)的元素進(jìn)行比較,若相等,則找到返回 TRUE;,2. 否則在左子樹中進(jìn)行查找,若找到, 則返回 TRUE;,3. 否則繼續(xù)在右子樹中進(jìn)行查找,若找到,則返回 TRUE,否則返回 FALSE;,Status Preorder (BiTre

15、e T, ElemType x, BiTree return OK, /if else return FALSE;,else if (Preorder(T-lchild, x, p) return OK; else return(Preorder(T-rchild, x, p) ; /else,2、統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù),算法基本思想:,先序(或中序或后序)遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。 由此，需在遍歷算法中增添一個(gè)“計(jì)數(shù)”的參數(shù)，并將算法中“訪問結(jié)點(diǎn)” 的操作改為:若是葉子，則計(jì)數(shù)器增1。,void CountLeaf (BiTree T, int / if / Coun

16、tLeaf,int CountLeaf (BiTree T) /返回指針T所指二叉樹中所有葉子結(jié)點(diǎn)個(gè)數(shù) if (!T ) return 0; if (!T-lchild /else / CountLeaf,int Count (BiTree T) /返回指針T所指二叉樹中所有結(jié)點(diǎn)個(gè)數(shù) if (!T ) return 0; if (!T-lchild /else / CountLeaf,3、求二叉樹的深度(后序遍歷),算法基本思想:,從二叉樹深度的定義可知，二叉樹的深度應(yīng)為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結(jié)點(diǎn)”的操作為:求得左、右子樹深度的最大值，然

17、后加 1 。,首先分析二叉樹的深度和它的左、右子樹深度之間的關(guān)系。,int Depth (BiTree T ) / 返回二叉樹的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval; ,void Depth(BiTree T , int level, int / 調(diào)用之前 level 的初值為 1。 /

18、dval 的初值為 0.,4、復(fù)制二叉樹,其基本操作為:生成一個(gè)結(jié)點(diǎn)。,根元素,T,左子樹,右子樹,NEWT,左子樹,右子樹,左子樹,右子樹,(后序遍歷),BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) if (!(T = new BiTNode) exit(1); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; ,生成一個(gè)二叉樹的結(jié)點(diǎn) (其數(shù)據(jù)域?yàn)閕tem,左指針域?yàn)閘ptr,右指針域?yàn)閞ptr),BiTNode *CopyTr

19、ee(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, newlptr, newrptr); return newT; / CopyTree,例如:下列二叉樹的復(fù)制過程如下:,newT,5、建立二叉樹的存儲結(jié)構(gòu),不同的定義方法相應(yīng)有不同

20、的存儲結(jié)構(gòu)的建立算法,以字符串的形式 “根 左子樹 右子樹” 定義一棵二叉樹,例如:,以空白字符“ ”表示,A(B( ,C( , ),D( , ),空樹,只含一個(gè)根結(jié)點(diǎn)的二叉樹,A,以字符串“A ”表示,以下列字符串表示,Status CreateBiTree(BiTree / CreateBiTree,A B C D,A,B,C,D,上頁算法執(zhí)行過程舉例如下:,A,T,B,C,D,scanf(,按給定的表達(dá)式建相應(yīng)二叉樹, 由先綴表示式建樹 例如：已知表達(dá)式的先綴表示式 -+ a b c / d e, 由原表達(dá)式建樹 例如：已知表達(dá)式 (a+b)c d/e,對應(yīng)先綴表達(dá)式 -+ a b c

21、/ d e的二叉樹,a,b,c,d,e,-,+,/,特點(diǎn)： 操作數(shù)為葉子結(jié)點(diǎn)， 運(yùn)算符為分支結(jié)點(diǎn),scanf( ,由先綴表示式建樹的算法的基本操作：,a+b,(a+b)c d/e,a+bc,分析表達(dá)式和二叉樹的關(guān)系:,(a+b)c,基本操作:,scanf( ,void CrtExptree(BiTree / CrtExptree, ,switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) CrtSubtree( t, c); / 建二叉樹并入棧 Pop(S, c) break; defult : /

22、 switch, ,while(!Gettop(S, c) ,建葉子結(jié)點(diǎn)的算法為：,void CrtNode(BiTree ,建子樹的算法為：,void CrtSubtree (Bitree ,僅知二叉樹的先序序列“abcdefg” 不能唯一確定一棵二叉樹，,由二叉樹的先序和中序序列建樹,如果同時(shí)已知二叉樹的中序序列“cbdaegf”,則會如何？,二叉樹的先序序列,二叉樹的中序序列,左子樹,左子樹,右子樹,右子樹,根,根,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,void

23、 CrtBT(BiTree else / / CrtBT, ,if (!(T= new BiTNode) exit(OVERFLOW); T-data = preps; if (k=is) T-Lchild = NULL; else CrtBT(T-Lchild, pre, ino, ps+1, is, k-is ); if (k=is+n-1) T-Rchild = NULL; else CrtBT(T-Rchild, pre, ino, ps+1+(k-is), k+1, n-(k-is)-1 );,6.5線索二叉樹,何謂線索二叉樹？ 線索鏈表的遍歷算法 如何建立線索鏈表？,一、何謂線索二

24、叉樹？,遍歷二叉樹的結(jié)果是， 求得結(jié)點(diǎn)的一個(gè)線性序列。,A,B,C,D,E,F,G,H,K,例如:,先序序列: A B C D E F G H K,中序序列: B D C A H G K F E,后序序列: D C B H K G F E A,指向該線性序列中的“前驅(qū)”和 “后繼” 的指針，稱作“線索”,與其相應(yīng)的二叉樹，稱作 “線索二叉樹”,包含 “線索” 的存儲結(jié)構(gòu)，稱作 “線索鏈表”,A B C D E F G H K, D ,C , B,E ,對線索鏈表中結(jié)點(diǎn)的約定：,在二叉鏈表的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域， 并作如下規(guī)定：,若該結(jié)點(diǎn)的左子樹不空， 則Lchild域的指針指向其左子樹， 且左

25、標(biāo)志域的值為“指針 Link”； 否則，Lchild域的指針指向其“前驅(qū)”， 且左標(biāo)志的值為“線索 Thread” 。,若該結(jié)點(diǎn)的右子樹不空， 則rchild域的指針指向其右子樹， 且右標(biāo)志域的值為 “指針 Link”； 否則，rchild域的指針指向其“后繼”， 且右標(biāo)志的值為“線索 Thread”。,如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表”,typedef struct BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指針 PointerThr LTag, RTag; / 左右標(biāo)志 BiThrNode, *B

26、iThrTree;,線索鏈表的類型描述：,typedef enum Link, Thread PointerThr; / Link=0:指針，Thread=1:線索,二、線索鏈表的遍歷算法:,for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);,由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。,例如: 對中序線索化鏈表的遍歷算法, 中序遍歷的第一個(gè)結(jié)點(diǎn) ？, 在中序線索化鏈表中結(jié)點(diǎn)的后繼 ？,左子樹上處于“最左下”（沒有左子樹）的結(jié)點(diǎn),若無右子樹，則為后繼線索所指結(jié)點(diǎn),否則為對其右子樹進(jìn)行中序遍歷時(shí)訪問的第一個(gè)

27、結(jié)點(diǎn),void InOrderTraverse_Thr(BiThrTree T, void (*Visit)(TElemType e) p = T-lchild; / p指向根結(jié)點(diǎn) while (p != T) / 空樹或遍歷結(jié)束時(shí)，p=T while (p-LTag=Link) p = p-lchild; / 第一個(gè)結(jié)點(diǎn) Visit(p-data);/add this line on 2005 while (p-RTag=Thread / p進(jìn)至其右子樹根 / InOrderTraverse_Thr,在中序遍歷過程中修改結(jié)點(diǎn)的 左、右指針域，以保存當(dāng)前訪問結(jié) 點(diǎn)的“前驅(qū)”和“后繼”信息。遍歷

28、過 程中，附設(shè)指針pre, 并始終保持指 針pre指向當(dāng)前訪問的、指針p所指 結(jié)點(diǎn)的前驅(qū)。,三、如何建立線索鏈表？,void InThreading(BiThrTree p) if (p) / 對以p為根的非空二叉樹進(jìn)行線索化 InThreading(p-lchild); / 左子樹線索化 if (!p-lchild) / 建前驅(qū)線索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后繼線索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持 pre 指向 p 的前驅(qū) InThreading

29、(p-rchild); / 右子樹線索化 / if / InThreading,Status InOrderThreading(BiThrTree / InOrderThreading, ,if (!T) Thrt-lchild = Thrt; else Thrt-lchild = T; pre = Thrt; InThreading(T); pre-rchild = Thrt; / 處理最后一個(gè)結(jié)點(diǎn) pre-RTag = Thread; Thrt-rchild = pre; ,6.6 樹和森林 的表示方法,樹的三種存儲結(jié)構(gòu),一、雙親表示法,二、孩子鏈表表示法,三、樹的二叉鏈表(孩子-兄弟）

30、存儲表示法,根 r=0 結(jié)點(diǎn)數(shù) n=7,data parent,一、雙親表示法:,typedef struct PTNode Elem data; int parent; / 雙親位置域 PTNode;,#define MAX_TREE_SIZE 100,結(jié)點(diǎn)結(jié)構(gòu):,C語言的類型描述:,typedef struct PTNode nodes MAX_TREE_SIZE; int r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;,樹結(jié)構(gòu):,r=0 n=7,data firstchild,二、孩子鏈表表示法:,-1 0 0 0 2 2 4,typedef struct CTNode int c

31、hild; struct CTNode *nextchild; *ChildPtr;,孩子結(jié)點(diǎn)結(jié)構(gòu):,C語言的類型描述:,typedef struct Elem data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox;,雙親結(jié)點(diǎn)結(jié)構(gòu),typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; / 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 CTree;,樹結(jié)構(gòu):,root,三、樹的二叉鏈表 (孩子-兄弟）存儲表示法,root,typedef struct CSNode Elem data; struct CSNode *firstchild,

32、*nextsibling; CSNode, *CSTree;,C語言的類型描述:,結(jié)點(diǎn)結(jié)構(gòu):,森林和二叉樹的對應(yīng)關(guān)系,設(shè)森林 F = ( T1, T2, , Tn ); T1 = ( root，t11, t12, , t1m );,二叉樹 B =( LBT, Node(root), RBT );,由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:,若 F = ，則 B = ;,由 ROOT( T1 ) 對應(yīng)得到Node(root);,否則，,由 (t11, t12, , t1m ) 對應(yīng)得到 LBT;,由 (T2, T3, Tn ) 對應(yīng)得到 RBT。,由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為:,由LBT 對應(yīng)得到 (

33、t11, t12, ，t1m);,若 B = , 則 F = ;,否則，,由 Node(root) 對應(yīng)得到 ROOT( T1 );,由RBT 對應(yīng)得到 (T2, T3, , Tn)。,T1,T2,Tn,由此，樹和森林的各種操作均可與二叉樹的各種操作相對應(yīng)。,應(yīng)當(dāng)注意的是，和樹對應(yīng)的二叉樹，其左、右子樹的概念 已改變?yōu)椋?左是孩子，右是兄弟,6.7 樹和森林的遍歷,一、樹的遍歷,二、森林的遍歷,三、樹的遍歷的應(yīng)用,樹的遍歷可有2條搜索路徑:,按層次遍歷:,先根(次序)遍歷:,后根(次序)遍歷:,若樹不空，則先訪問根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹。,若樹不空，則先依次后根遍歷各棵子樹，然后訪問根

34、結(jié)點(diǎn)。,若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。,層次遍歷時(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。森林中第一棵樹的根結(jié)點(diǎn)；,2。森林中第一棵樹的子樹森林；,3。森林中其它樹構(gòu)成的森林。,可以分解成三部分：,森林,若森林不空，則 訪問森林中第一棵樹的根結(jié)點(diǎn); 先序遍歷森林中第一棵樹的子樹森林; 先序遍歷森林中(除第一棵樹之外)其 余樹構(gòu)成的森林。,先序遍歷,森林的遍歷,即：依次從左至右對森林中的每一棵樹進(jìn)行先根遍歷。,中

35、序遍歷,若森林不空，則 中序遍歷森林中第一棵樹的子樹森林; 訪問森林中第一棵樹的根結(jié)點(diǎn); 中序遍歷森林中(除第一棵樹之外)其 余樹構(gòu)成的森林。,即：依次從左至右對森林中的每一棵樹進(jìn)行后根遍歷。,樹的遍歷和二叉樹遍歷的對應(yīng)關(guān)系 ？,先根遍歷,后根遍歷,樹,二叉樹,森林,先序遍歷,先序遍歷,中序遍歷,中序遍歷,設(shè)樹的存儲結(jié)構(gòu)為孩子兄弟鏈表,typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;,一、求樹的深度,二、輸出樹中所有從根到葉子的路徑,三、建樹的存儲結(jié)構(gòu),Int D

36、epth(CSTree T) If (T=NULL) return 0; Else D1 = Depth(T-firstchild); D2 = Depth(T-nextsibling); Return Maxd1+1,d2,int TreeDepth( CTree T ) / T 是樹的孩子鏈表存儲結(jié)構(gòu)， / 返回該樹的深度 if ( T.n = 0) return 0; else return Depth( T, T.r ); / TreeDepth,一、求樹的深度的算法：,int Depth( CTree T, int root ) max = 0; p = T.nodesroot.fi

37、rstchild; while ( p ) h = Depth( T, p-child ); if ( h max ) max = h; p = p-nextchild; /while return max+1; ,二、輸出樹中所有從根到葉子的路徑的算法:,例如：對左圖所示的樹，其輸出結(jié)果應(yīng)為：,A B E A B F A C A D G H I A D G H J A D G H K,void AllPath( BiTree T, Stack / if(T) / AllPath,/ 輸出二叉樹上從根到所有葉子結(jié)點(diǎn)的路徑,void OutPath( Bitree T, Stack / whil

38、e / OutPath,/ 輸出森林中所有從根到葉的路徑,三、建樹的存儲結(jié)構(gòu)的算法:,和二叉樹類似，不同的定義相應(yīng)有不同的算法。,假設(shè)以二元組(F,C)的形式自上而下、自左而右依次輸入樹的各邊，建立樹的孩子-兄弟鏈表。,A,B,C,D,E,F,G,例如:,對下列所示樹的輸入序列應(yīng)為:,(#, A) (A, B) (A, C) (A, D) (C, E) (C, F) (E, G),A,B,C,D,(#, A),(A, B),(A, C),(A, D),(C, E),可見，算法中需要一個(gè)隊(duì)列保存已建好的結(jié)點(diǎn)的指針,void CreatTree( CSTree / 所建為根結(jié)點(diǎn) else / 非根結(jié)點(diǎn)的情況 / for / CreateTree, ,GetHead(Q,s); / 取隊(duì)列頭元素(指針值) while (s-data != fa ) / 查詢雙親結(jié)點(diǎn) DeQueue(Q,s); GetHead(Q,s); if (!(s-firstchild) s-firstchild = p; r = p; / 鏈接第一個(gè)孩子結(jié)點(diǎn) else r