數(shù)據(jù)結(jié)構(gòu)chapter06_第1頁
數(shù)據(jù)結(jié)構(gòu)chapter06_第2頁
數(shù)據(jù)結(jié)構(gòu)chapter06_第3頁
數(shù)據(jù)結(jié)構(gòu)chapter06_第4頁
數(shù)據(jù)結(jié)構(gòu)chapter06_第5頁
已閱讀5頁,還剩154頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、第六章 樹與二叉樹6.1 樹的類型定義樹的類型定義6.2 6.2 二叉樹的類型定義二叉樹的類型定義6.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)6.4 二叉樹的遍歷二叉樹的遍歷6.5 線索二叉樹線索二叉樹6.6 樹和森林的表示方法樹和森林的表示方法6.7 樹和森林的遍歷樹和森林的遍歷6.8 哈夫曼樹與哈夫曼編碼哈夫曼樹與哈夫曼編碼6.1 樹的類型定義樹的類型定義數(shù)據(jù)對象數(shù)據(jù)對象 D:D是具有相同特性的數(shù)據(jù)元素的集合。是具有相同特性的數(shù)據(jù)元素的集合。 若若D為空集,則稱為空樹;為空集,則稱為空樹; 否則否則: (1) 在在D中存在唯一的稱為根的數(shù)據(jù)元素中存在唯一的稱為根的數(shù)據(jù)元素root, (2) 當(dāng)

2、當(dāng)n1時,其余結(jié)點可分為時,其余結(jié)點可分為m (m0)個互個互 不相交的有限集不相交的有限集T1, T2, , Tm, 其中每一其中每一 棵子集本身又是一棵符合本定義的樹,棵子集本身又是一棵符合本定義的樹, 稱為根稱為根root的子樹。的子樹。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系 R:查查 找找 類類 插插 入入 類類刪刪 除除 類類基本操作:基本操作: Root(T) 求樹的根結(jié)點求樹的根結(jié)點 Value(T, cur_e) 求當(dāng)前結(jié)點的元素值求當(dāng)前結(jié)點的元素值 Parent(T, cur_e) 求當(dāng)前結(jié)點的雙親結(jié)點求當(dāng)前結(jié)點的雙親結(jié)點LeftChild(T, cur_e) 求當(dāng)前結(jié)點的最左孩子求當(dāng)前結(jié)點的最

3、左孩子 RightSibling(T, cur_e) 求當(dāng)前結(jié)點的右兄弟求當(dāng)前結(jié)點的右兄弟TreeEmpty(T) 判定樹是否為空樹判定樹是否為空樹 TreeDepth(T) 求樹的深度求樹的深度TraverseTree( T) / 遍歷遍歷查找類查找類:InitTree(T) 初始化置空樹初始化置空樹 CreateTree(T) 按定義構(gòu)造樹按定義構(gòu)造樹Assign(T, cur_e, value) 給當(dāng)前結(jié)點賦值給當(dāng)前結(jié)點賦值InsertChild(T, p, i, c) 將以將以c為根的樹插入為結(jié)點為根的樹插入為結(jié)點p的第的第i棵子樹棵子樹插入插入類:類: ClearTree(T) 將樹

4、清空將樹清空 DestroyTree(T) 銷毀樹的結(jié)構(gòu)銷毀樹的結(jié)構(gòu)DeleteChild(T, p, i) 刪除結(jié)點刪除結(jié)點p的第的第i棵子樹棵子樹刪除類:刪除類:ABCDEFGHIJMKLA( )T1T3T2樹根B(E, F(K, L), C(G), D(H, I, J(M)樹定義示例樹定義示例: :() 有確定的根;() 樹根和子樹根之間為有向關(guān)系。有向樹:有向樹:有序樹:有序樹:子樹之間存在確定的次序關(guān)系。無序樹:無序樹:子樹之間不存在確定的次序關(guān)系。有向樹、有序樹和無序樹有向樹、有序樹和無序樹基基 本本 術(shù)術(shù) 語語結(jié)點結(jié)點: :結(jié)點的度結(jié)點的度: :樹的度樹的度: :葉子結(jié)點葉子結(jié)點

5、: :分支結(jié)點分支結(jié)點: :數(shù)據(jù)元素+ +若干指向子樹的分支分支的個數(shù)樹中所有結(jié)點的度的最大值度為零的結(jié)點度大于零的結(jié)點DHIJM(從根到結(jié)點的)路徑路徑:孩子孩子結(jié)點、雙親雙親結(jié)點、兄弟兄弟結(jié)點、堂兄弟祖先祖先結(jié)點、子孫子孫結(jié)點結(jié)點的層次結(jié)點的層次: :樹的深度:樹的深度: 由從根根到該結(jié)點所經(jīng)分支和結(jié)點構(gòu)成ABCDEFGHIJMKL假設(shè)根結(jié)點的層次為1,第l 層的結(jié)點的子樹根結(jié)點的層次為l+1樹中葉子結(jié)點所在的最大層次任何一棵非空樹是一個二元組 Tree = (root,F(xiàn))其中:其中:root 被稱為根結(jié)點, F 被稱為子樹森林森林:森林:是 m(m0)棵互不相交的樹的集合ArootBE

6、FKLCGDHIJMF對比對比樹型結(jié)構(gòu)樹型結(jié)構(gòu)和和線性結(jié)構(gòu)線性結(jié)構(gòu)的結(jié)構(gòu)特點的結(jié)構(gòu)特點樹型結(jié)構(gòu)樹型結(jié)構(gòu)和和線性結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)線性結(jié)構(gòu)樹型結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素第一個數(shù)據(jù)元素 ( (無前驅(qū)無前驅(qū)) ) 根結(jié)點根結(jié)點 ( (無前驅(qū)無前驅(qū)) )最后一個數(shù)據(jù)元素最后一個數(shù)據(jù)元素 (無后繼無后繼)多個葉子結(jié)點多個葉子結(jié)點 ( (無后繼無后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個前驅(qū)、一個前驅(qū)、 一個后繼一個后繼) )其它數(shù)據(jù)元素其它數(shù)據(jù)元素( (一個前驅(qū)、一個前驅(qū)、 多個后繼多個后繼) )6.2 6.2 二叉樹的類型定義二叉樹的類型定義 二叉樹或為空樹空樹;或是由一個根結(jié)根結(jié)點點加上兩棵兩棵

7、分別稱為左子樹左子樹和右子樹的、互不交的互不交的二叉樹二叉樹組成。ABCDEFGHK根結(jié)點左子樹右子樹EFN空樹空樹只含根結(jié)點只含根結(jié)點NNNLRR右子樹為空樹右子樹為空樹L左子樹為空樹左子樹為空樹左右子左右子樹均不樹均不為空樹為空樹二叉樹的五種基本形態(tài):二叉樹的五種基本形態(tài):查查 找找 類類插插 入入 類類刪刪 除除 類類二叉樹的主要基本操作二叉樹的主要基本操作: Root(T); Value(T, e); Parent(T, e); LeftChild(T, e); RightChild(T, e); LeftSibling(T, e); RightSibling(T, e); BiTre

8、eEmpty(T); BiTreeDepth(T); PreOrderTraverse(T); InOrderTraverse(T); PostOrderTraverse(T); LevelOrderTraverse(T); InitBiTree(T); Assign(T, e, value); CreateBiTree(T); InsertChild(T, p, LR, c);ClearBiTree(T); DestroyBiTree(T);DeleteChild(T, p, LR);二叉樹的重要特性二叉樹的重要特性 性質(zhì)性質(zhì) 1 : 在二叉樹的第 i 層上至多有2i-1 個結(jié)點。 (i1)

9、用歸納法用歸納法證明證明: 歸納基歸納基: 歸納假設(shè):歸納假設(shè): 歸納證明:歸納證明:i = 1 層時,只有一個根結(jié)點, 2i-1 = 20 = 1;假設(shè)對所有的 j,1 j i,命題成立;二叉樹上每個結(jié)點至多有兩棵子樹,則第 i 層的結(jié)點數(shù) = 2i-2 2 = 2i-1 。 性質(zhì)性質(zhì) 2 : 深度為 k 的二叉樹上至多含 2k-1 個結(jié)點(k1)證明:證明: 基于上一條性質(zhì),深度為 k 的二叉樹上的結(jié)點數(shù)至多為 20+21+ +2k-1 = 2k-1 性質(zhì)性質(zhì) 3 : 對任何一棵二叉樹,若它含有n0 個葉子結(jié)點、n2 個度為 2 的結(jié)點,則必存在關(guān)系式:n0 = n2+1證明:證明:設(shè)設(shè)

10、二叉樹上結(jié)點總數(shù) n = n0 + n1 + n2又又 二叉樹上分支總數(shù) b = n1 + 2n2而 b = n-1 = n0 + n1 + n2 - 1由此,由此, n0 = n2 + 1滿二叉樹滿二叉樹:指的是深度為k且含有2k-1個結(jié)點的二叉樹。完全二叉樹完全二叉樹:樹中所含的 n 個結(jié)點和滿二叉樹中編號編號為為 1 至至 n 的結(jié)點的結(jié)點一一對應(yīng)。123456789 10 11 12 13 14 15abcdefghij兩類兩類特殊特殊的二叉樹:的二叉樹:證明:證明:設(shè)設(shè) 完全二叉樹的深度為 k 則根據(jù)第二條性質(zhì)得 2k-1 n 2k 即 k-1 log2 n n,則該結(jié)點無左孩子,

11、否則,編號為 2i 的結(jié)點為其左孩子左孩子結(jié)點;(3) 若 2i+1n,則該結(jié)點無右孩子結(jié)點, 否則,編號為2i+1 的結(jié)點為其右孩子右孩子結(jié)點。二、二叉樹的鏈?zhǔn)蕉?、二叉樹的鏈?zhǔn)?存儲表示存儲表示一、一、 二叉樹的順序二叉樹的順序 存儲表示存儲表示6.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)#define MAX_TREE_SIZE 100 /*二叉樹的最大結(jié)點數(shù)*/typedef TElemType SqBiTreeMAX_TREE_SIZE; /* 0號單元存儲根結(jié)點*/SqBiTree bt;一、一、 二叉樹的順序存儲表示二叉樹的順序存儲表示例如例如: A B D C E F 0 1 2 3

12、 4 5 6 7 8 9 10 11 12 13ABCDEF14013261. 1. 二叉鏈表二叉鏈表2三叉鏈表三叉鏈表3 3雙親鏈表雙親鏈表4線索鏈表線索鏈表二、二叉樹的鏈?zhǔn)酱鎯Ρ硎径?、二叉樹的鏈?zhǔn)酱鎯Ρ硎続DEBCF rootlchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):1. 1. 二叉鏈表二叉鏈表typedef struct BiTNode /* 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)*/ TElemType data; struct BiTNode *lchild, *rchild; /*左右孩子指針*/ BiTNode, *BiTree;lchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):C 語

13、言的類型描述如下語言的類型描述如下: :rootADEBCF parent lchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):2三叉鏈表三叉鏈表 typedef struct TriTNode /*結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)*/ TElemType data; struct TriTNode *lchild, *rchild; /*左右孩子指針*/ struct TriTNode *parent; /*雙親指針*/ TriTNode, *TriTree;parent lchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):C 語言的類型描述如下語言的類型描述如下: :結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu): data pa

14、rentABDCEF0B41D42C03E14A-15F36LRTagLRRRRL根根3 3雙親鏈表雙親鏈表 typedef struct BPTNode /* 結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu)*/ TElemType data; int *parent; /*指向雙親的指針*/ char LRTag; /*左、右孩子標(biāo)志域*/ BPTNode typedef struct BPTree /*樹結(jié)構(gòu)樹結(jié)構(gòu)*/ BPTNode nodesMAX_TREE_SIZE; int num_node; /*結(jié)點數(shù)目*/ int root; /*根結(jié)點的位置*/ BPTree6.4 二叉樹的遍二叉樹的遍歷歷一、問題的提出

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

16、徑:二叉樹的三條遍歷路徑:1先上后下先上后下的按層次遍歷;2先左先左(子樹)后右后右(子樹)的遍歷;3先右先右(子樹)后左后左(子樹)的遍歷。先先(根)序的遍歷算法中中(根)序的遍歷算法后后(根)序的遍歷算法根根左子樹右子樹根根根根根根根根根根二、先左后右的遍歷算法二、先左后右的遍歷算法 若二叉樹為空樹,則空操作;否則,(1)訪問根結(jié)點;(2)先序遍歷左子樹;(3)先序遍歷右子樹。先(根)序的遍歷算法: 若二叉樹為空樹,則空操作;否則,(1)中序遍歷左子樹;(2)訪問根結(jié)點;(3)中序遍歷右子樹。中(根)序的遍歷算法:中(根)序的遍歷算法: 若二叉樹為空樹,則空操作;否則,(1)后序遍歷左子樹

17、;(2)后序遍歷右子樹;(3)訪問根結(jié)點。后(根)序的遍歷算法:后(根)序的遍歷算法:ABCDEFGHK例如:例如:先序序列:先序序列:中序序列:中序序列:后序序列:后序序列:A B C D E F G H KB D C A E H G K FD C B H K G F E Avoid Preorder (BiTree T) /*先序遍歷二叉樹 */ if (T) visit(T-data); /*訪問結(jié)點*/ Preorder(T-lchild); /*遍歷左子樹*/ Preorder(T-rchild); /*遍歷右子樹*/ else return ;三、算法的遞歸描述三、算法的遞歸描述有

18、兩種分析(描述)方法:一、“任務(wù)書”分析方法二、“路徑”分析方法四、中序遍歷算法的非遞歸描述四、中序遍歷算法的非遞歸描述一、“任務(wù)書”分析方法在寫算法之前首先需定義棧的元素類型。typedeftypedef enum Visit,Travel TaskType; /*Visit = 0:訪問 Travel = 1:遍歷*/ typedef structtypedef struct BiTree ptr; /*指向根結(jié)點的指針*/ TaskType task; /*任務(wù)性質(zhì)*/ ElemType;“遍歷二叉樹遍歷二叉樹”包括三項子任務(wù):“遍歷左子樹”“遍歷右子樹”“訪問根結(jié)點”voidvoid

19、InOrder_iter( BiTree BT ) /*利用棧實現(xiàn)中序遍歷二叉樹,T為二叉樹的根結(jié)點的頭指針*/ Stack S; InitStack(S); ElemType e; e.ptr=BT; e.task=Travel; ifif(T) push(S, e); /*布置初始任務(wù)*/ whilewhile(! !StackEmpty(S) pop(S,e); /*每次處理一項任務(wù)*/ if if (e.task=Visit) visit(e.ptr); /* 處理訪問任務(wù)*/ elseelse ifif(e.ptr!=NULL) /*處理非空樹的遍歷任務(wù)*/ p=e.ptr; e.p

20、tr=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); /*end if(e.ptr!=NULL)*/ /*end while*/ /*InOrder_iter*/二、“路徑”分析方法void Inorder_I(BiTree T) Stack *S; InitStack(S); t = GoFarLeft(T, S); /*找到最左下的結(jié)點*/ while(t) visit(t-data); if (t-rchild) els

21、e if ( !StackEmpty(S ) t = pop(S); /*退棧*/ else t = NULL; /*??毡砻鞅闅v結(jié)束*/ /*end while*/*Inorder_I*/ t = GoFarLeft(t-rchild, S);BiTNode *GoFarLeft(BiTree T, Stack *S) if (T=NULL ) return NULL; while (T-lchild ) push(S, T); T = T-lchild; return T;3、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)、統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)4、求二叉樹的深度、求二叉樹的深度(后序遍歷后序遍歷)5、查

22、詢二叉樹中某個結(jié)點、查詢二叉樹中某個結(jié)點1 1、建立二叉樹的存儲結(jié)構(gòu)、建立二叉樹的存儲結(jié)構(gòu)2、復(fù)制二叉樹、復(fù)制二叉樹(后序遍歷后序遍歷)四四、遍歷算法的應(yīng)用舉例遍歷算法的應(yīng)用舉例1 1、建立二叉樹的存儲、建立二叉樹的存儲結(jié)構(gòu)結(jié)構(gòu)不同的定義方法相應(yīng)有不同的不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法存儲結(jié)構(gòu)的建立算法例如例如: :以空白字符“ ”表示ABCDA(B( ,C( , ),D( , )空樹空樹只含一個根結(jié)點只含一個根結(jié)點的二叉樹的二叉樹A以字符串“A ”表示以下列字符串表示通過給定字符串建立二叉樹通過給定字符串建立二叉樹 字符串按字符串按“根根 左子樹左子樹 右子樹右子樹”給出給出ty

23、pedef enumERR,OK Status;BiTree CreateBiTree() char ch; BiTree T; ch=getchar(); if (ch= ) return NULL; else T = malloc(sizeof(BiTNode); if (T)=NULL ) exit(-1); T-data = ch; /*生成根結(jié)點*/ T-lchild=CreateBiTree(); /*構(gòu)造左子樹*/ T-rchild=CreateBiTree(); /*構(gòu)造右子樹*/ return T; /* end CreateBiTree*/A B C D A BCD算法執(zhí)行

24、過程舉例如下:ATBCDch=getchar();if (ch= ) T = NULL;else T = malloc(sizeof(BiTNode) if (!(*T) exit(-1); T-data = ch; T-lchild=CreateBiTree(); T-rchild=CreateBiTree(); 僅知二叉樹的先序序列“abcdefg” 不能唯一確定一棵二叉樹, 如果同時已知二叉樹的中序序列“cbdaegf”,則會如何? 二叉樹的先序序列二叉樹的中序序列左子樹左子樹左子樹左子樹 右子樹右子樹右子樹右子樹根根根根由先序和中序序列建立二叉樹由先序和中序序列建立二叉樹a b c d

25、 e f gc b d a e g f例如例如: :aab bccddeeffggabcdefg先序序列中序序列void CrtBT(BiTree *T, char pre, char ino, int ps, int is, int n ) /*已知preps.ps+n-1為二叉樹的先序序列, insis.is+n-1為二叉樹的中序序列,本算 法由此兩個序列構(gòu)造二叉鏈表*/ if (n=0) *T=NULL; else k=Search(ino, preps);/*在中序序列中查詢*/ if (k= -1) *T=NULL; else /* end CrtBT */ *T= malloc(s

26、izeof(BiTNode);if (*T)=NULL) exit(-1);(*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 );其基本操作為其基本操作為: :生成一個結(jié)點。生成一個結(jié)點。根元素根元素T左子樹左子樹右子樹右子樹根元素根元素NEW

27、T左子樹左子樹右子樹右子樹左子樹左子樹右子樹右子樹(后序遍歷后序遍歷)2、復(fù)制二叉樹、復(fù)制二叉樹BiTNode *GetTreeNode(TElemType item, BiTNode *lptr , BiTNode *rptr ) BiTree T= malloc(sizeof(BiTNode); if (T=NULL) exit(-1); T- data = item; T- lchild = lptr; T- rchild = rptr; return T; 生成一個二叉樹的結(jié)點生成一個二叉樹的結(jié)點(其數(shù)據(jù)域為其數(shù)據(jù)域為item,左指針域為左指針域為lptr,右指針域為右指針域為rptr

28、)BiTNode *CopyTree(BiTree T) BiTree newlptr,newT; if (T=NULL ) return NULL; /*復(fù)制左子樹和右子樹*/ if (T-lchild ) newlptr = CopyTree(T-lchild); else newlptr = NULL; if (T-rchild ) newrptr = CopyTree(T-rchild); else newrptr = NULL; newT = GetTreeNode(T-data, newlptr, newrptr); return newT; /*end CopyTree*/ABC

29、DEFGHK D C H K G A例如例如: :下列二叉樹下列二叉樹的復(fù)制過程如下的復(fù)制過程如下: :newT F B E 3、二叉樹中的查找在二叉樹中的查找和統(tǒng)計的基本思想就是利用二叉樹的遍歷算法,查找或統(tǒng)計相應(yīng)的數(shù)據(jù)(1)在二叉樹中查找指定元素)在二叉樹中查找指定元素在二叉樹不空的前提下,和根結(jié)點的元素進(jìn)行比較,若相等,返回根結(jié)點的指針;否則在左子樹中進(jìn)行查找,若找到,則返回左子樹的指針;否則繼續(xù)在右子樹中進(jìn)行查找,若找到,則返回右子樹指針,否則返回NULL;算法基本思想算法基本思想BiTNode *Preorder (BiTree T, ElemType x) /*若二叉樹中存在和若二

30、叉樹中存在和 x 相同的元素,則返回指向該結(jié)點相同的元素,則返回指向該結(jié)點, 否則返回否則返回 NULL */ if (T) if (T-data=x) return T, else return NULL;else if (Preorder(T-lchild, x) return T-lchild; else if(Preorder(T-rchild, x) return T-rchild;/* end if(T-data=x) */算法基本思想算法基本思想: : 先序(或中序或后序)遍歷二叉樹,在遍歷過程中查找葉子結(jié)點,并計數(shù)。由此,需在遍歷算法中增添一個需在遍歷算法中增添一個“計數(shù)計數(shù)”

31、的參數(shù),的參數(shù),并將算法中“訪問結(jié)點” 的操作改為:若是葉子,則計數(shù)器增若是葉子,則計數(shù)器增1 1。(2)統(tǒng)計二叉樹中葉子結(jié)點的個數(shù))統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)void CountLeaf (BiTree T, int *count) if ( T ) if (!T-lchild)& (!T-rchild) (*count)+; /*對葉子結(jié)點計數(shù)*/ CountLeaf( T-lchild, count); CountLeaf( T-rchild, count); /*end CountLeaf*/統(tǒng)計葉子結(jié)點方法1int CountLeaf (BiTree T) if (!T )

32、return 0; if (!T-lchild & !T-rchild) return 1; else int m = CountLeaf( T-lchild); int n = CountLeaf( T-rchild); return (m+n); /*end CountLeaf*/統(tǒng)計葉子結(jié)點方法2(3)統(tǒng)計二叉樹中所有結(jié)點的個數(shù))統(tǒng)計二叉樹中所有結(jié)點的個數(shù) 算法與統(tǒng)計葉子結(jié)點方法2類似,只是返回值是葉子結(jié)點個數(shù)+1,即多加了一個根結(jié)點。/*統(tǒng)計二叉樹所有結(jié)點數(shù)目統(tǒng)計二叉樹所有結(jié)點數(shù)目*/int Count (BiTree T) if (!T ) return 0; if (!T-

33、lchild & !T-rchild) return 1; else m = Count ( T-lchild); n = Count ( T-rchild); return (m+n+1); /*左右子樹葉子結(jié)點數(shù)左右子樹葉子結(jié)點數(shù)+1*/ /* end CountLeaf*/算法基本思想算法基本思想: : 從二叉樹深度的定義可知,二叉樹的二叉樹的深度應(yīng)為其左、右子樹深度的最大值加深度應(yīng)為其左、右子樹深度的最大值加1 1。由此,需先分別求得左、右子樹的深度,需先分別求得左、右子樹的深度,算法中“訪問結(jié)點”的操作為:求得左、求得左、右子樹深度的最大值,然后加右子樹深度的最大值,然后加

34、1 1 。 首先分析二叉樹的深度二叉樹的深度和它的左左、右子右子樹深度樹深度之間的關(guān)系。4、求二叉樹的深度、求二叉樹的深度(后序遍歷后序遍歷)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;6.5線索二叉樹線索二叉樹 何謂線索二叉樹?何

35、謂線索二叉樹? 線索鏈表的遍歷算法線索鏈表的遍歷算法 如何建立線索鏈表?如何建立線索鏈表?遍歷二叉樹的結(jié)果是, 求得結(jié)點的一個線性序列。ABCDEFGHK例如:先序先序序列: 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é)點的

36、約定:中結(jié)點的約定: 在二叉鏈表的結(jié)點中增加兩個標(biāo)志域增加兩個標(biāo)志域,并作如下規(guī)定:若該結(jié)點的左子樹不空,若該結(jié)點的左子樹不空,則Lchild域的指針指向其左子樹, 且左標(biāo)志域的值為“指針 Link”; 否則,Lchild域的指針指向其“前驅(qū)”, 且左標(biāo)志的值為“線索 Thread” 。若該結(jié)點的右子樹不空,若該結(jié)點的右子樹不空,則rchild域的指針指向其右子樹, 且右標(biāo)志域的值為 “指針 Link”;否則,rchild域的指針指向其“后繼”, 且右標(biāo)志的值為“線索 Thread”。 如此定義的二叉樹的存儲結(jié)構(gòu)稱作如此定義的二叉樹的存儲結(jié)構(gòu)稱作“線索鏈表線索鏈表”typedef struct

37、 BiThrNod TElemType data; struct BiThrNode *lchild, *rchild; / 左右指針 PointerThr LTag, RTag; / 左右標(biāo)志 BiThrNode, *BiThrTree;線索鏈表的類型描述: typedef enum Link, Thread PointerThr; /*Link=0:指針,Thread=1:線索*/ for ( p = firstNode(T); p; p = Succ(p) ) Visit (p);由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息,從而簡化了遍歷的算法。二、線索鏈表的遍歷算法二、

38、線索鏈表的遍歷算法:例如例如: 對中序線索化鏈表的遍歷算法對中序線索化鏈表的遍歷算法 中序遍歷的第一個結(jié)點中序遍歷的第一個結(jié)點 ? 在中序線索化鏈表中結(jié)點的后繼在中序線索化鏈表中結(jié)點的后繼 ?左子樹上處于“最左下最左下”(沒有左子樹)的結(jié)點若若無右子樹,則為則為后繼線索后繼線索所指結(jié)點否則為否則為對其右子樹右子樹進(jìn)行中序遍歷遍歷時訪問的第一個結(jié)點第一個結(jié)點 為了方便操作,可以在中序線索二叉樹中加入一個頭結(jié)點,使其lchild指向二叉樹的根結(jié)點,而rchild指向最右下的結(jié)點。這時最左下結(jié)點的lchild成為線索指針,指向頭結(jié)點前驅(qū),而最右下結(jié)點的rchild也成為線索指針,指向頭結(jié)點后繼。 由

39、于頭結(jié)點的左子樹指針指向根結(jié)點,右子樹指針指針指向最右下結(jié)點,同時最左下結(jié)點的左子樹指針指向頭結(jié)點,最右下結(jié)點的右子樹指針指向頭結(jié)點,這樣加入頭結(jié)點的線索二叉樹就形成了一個雙向鏈表,因此可以從任意結(jié)點開始,遍歷線索二叉樹中序線索二叉樹中的頭結(jié)點 B C D E Thrt G H K F A 為空樹時的帶頭結(jié)點線索二叉樹lchild LTag data RTag rchild thrtlchild=thrt LTag=Linkrchild=thrt RLag=Threadthrt!=NULLvoid InOrderTraverse_Thr(BiThrTree Thrt) p = Thrt-lch

40、ild; /*p指向根結(jié)點,Thrt是頭結(jié)點的指針*/ while (p != Thrt) /*空樹或遍歷結(jié)束時,p=Thrt*/ while (p-LTag=Link) p = p-lchild; /*第一個結(jié)點*/ Visit (p- data); while (p-RTag=Thread & p-rchild!=Thrt) p = p-rchild; Visit(p-data); /*訪問后繼結(jié)點*/ p = p-rchild; /*p進(jìn)至其右子樹根*/ /* InOrderTraverse_Thr*/ 在中序遍歷過程中修改結(jié)點的在中序遍歷過程中修改結(jié)點的左、右指針域,以保存當(dāng)前

41、訪問結(jié)左、右指針域,以保存當(dāng)前訪問結(jié)點的點的“前驅(qū)前驅(qū)”和和“后繼后繼”信息。遍歷過信息。遍歷過程中,附設(shè)指針程中,附設(shè)指針pre, 并始終保持指并始終保持指針針pre指向當(dāng)前訪問的、指針指向當(dāng)前訪問的、指針p所指所指結(jié)點的前驅(qū)。結(jié)點的前驅(qū)。三、如何建立線索鏈表?三、如何建立線索鏈表?Status InOrderThreading(BiThrTree *Thrt, BiThrTree T) /*構(gòu)建帶頭結(jié)點的中序線索鏈表,*Thrt用于向調(diào)用者回傳創(chuàng)建的頭結(jié)點指針*/ *Thrt = malloc(sizeof(BiThrNode); if (!(*Thrt) ) exit (-1); (*T

42、hrt)-LTag = Link; (*Thrt)-RTag =Thread; (*Thrt)-rchild = *Thrt; /*初始化頭結(jié)點*/ return OK; /*end InOrderThreading */ if (!T) (*Thrt)-lchild =(*Thrt); else (*Thrt)-lchild = T; pre = (*Thrt); InThreading(T); pre-rchild = *Thrt;/*處理最后一個結(jié)點*/ pre-RTag = Thread; (*Thrt)-rchild = pre; void InThreading(BiThrTree

43、 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(p-rchild); /*右子樹線索化*/ /*end if(p)*/ /*InThreading*/6.6 6.6 樹和森林的表示方法樹和森林的

44、表示方法樹的三種存儲結(jié)構(gòu)樹的三種存儲結(jié)構(gòu)一、一、雙親表示法雙親表示法二、二、孩子鏈表表示法孩子鏈表表示法三、三、樹的二叉鏈表樹的二叉鏈表( (孩子孩子- -兄弟)兄弟) 存儲表示法存儲表示法ABCDEFGr=0n=60 A -11 B 02 C 03 D 04 E 2 5 F 26 G 5data parent一、雙親表示法一、雙親表示法: typedef struct PTNode Elem data; int parent; /*雙親位置域*/ PTNode; data parent#define MAX_TREE_SIZE 100結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu):C語言的類型描述語言的類型描述: :ty

45、pedef struct PTNode nodes MAX_TREE_SIZE; int r, n; /*根結(jié)點的位置和結(jié)點個數(shù)*/ PTree;樹結(jié)構(gòu)樹結(jié)構(gòu):r=0n=6 data firstchildABCDEFG0 A -11 B 02 C 03 D 04 E 25 F 26 G 464 5 1 2 3-1 0 0 0 2 2 4二、孩子鏈表表示法二、孩子鏈表表示法:typedef struct CTNode int child; /*孩子結(jié)點編號*/ struct CTNode *nextchild; *ChildPtr;孩子結(jié)點結(jié)構(gòu)孩子結(jié)點結(jié)構(gòu): child nextchildC語言

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

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

48、到 LBT;由 (T2, T3, Tn ) 對應(yīng)得到 RBT。由森林轉(zhuǎn)換成二叉樹由森林轉(zhuǎn)換成二叉樹的轉(zhuǎn)換規(guī)則為:由LBT 對應(yīng)得到 ( t11, t12, ,t1m);若 B = , 則 F = ;否則,由 Node(root) 對應(yīng)得到 ROOT( T1 );由RBT 對應(yīng)得到 (T2, T3, , Tn)。由二叉樹轉(zhuǎn)換為森林由二叉樹轉(zhuǎn)換為森林的轉(zhuǎn)換規(guī)則為:T1T11,T12,T1mT2,TnLBTRBTroot 由此,樹和森林的各種操作均可與二叉樹的各種操作相對應(yīng)。 應(yīng)當(dāng)注意的是,應(yīng)當(dāng)注意的是,和樹對應(yīng)的二叉樹,其左、右子樹的概念已改變?yōu)椋?左是孩子,右是兄弟左是孩子,右是兄弟6.76.7

49、樹和森林的遍歷樹和森林的遍歷一、樹的遍歷一、樹的遍歷二、森林的遍歷二、森林的遍歷三、樹的遍歷的應(yīng)用三、樹的遍歷的應(yīng)用按層次遍歷按層次遍歷:先根先根(次序次序)遍歷遍歷:后根后根(次序次序)遍歷遍歷: 若樹不空,則先訪問根結(jié)點,然后若樹不空,則先訪問根結(jié)點,然后依次先根遍歷各棵子樹。依次先根遍歷各棵子樹。 若樹不空,則先依次后根遍歷各棵若樹不空,則先依次后根遍歷各棵子樹,然后訪問根結(jié)點。子樹,然后訪問根結(jié)點。 若樹不空,則自上而下自左至右若樹不空,則自上而下自左至右訪問樹中每個結(jié)點。訪問樹中每個結(jié)點。一、樹的遍歷一、樹的遍歷 層次遍歷時頂點層次遍歷時頂點的訪問次序:的訪問次序: A B C DE

50、 F G H I J K 先根遍歷時頂點先根遍歷時頂點的訪問次序:的訪問次序:A B E F C D G H I J K 后根遍歷時頂點后根遍歷時頂點的訪問次序:的訪問次序:E F B C I J K H G D AA B C D E F G H I J K B C DE F G H I J K1。森林中第一棵樹的根結(jié)點;2。森林中第一棵樹的子樹森林;3。森林中其它樹構(gòu)成的森林。森林森林可以分解成三部分:二、森林的遍歷二、森林的遍歷 若森林不空,則訪問訪問森林中第一棵樹的根結(jié)點;先序遍歷先序遍歷森林中第一棵樹的子樹森林;先序遍歷先序遍歷森林中(除第一棵樹之外)其 余樹構(gòu)成的森林。先序遍歷先序遍

51、歷即:依次從左至右依次從左至右對森林中的每一棵樹樹進(jìn)行先根遍歷先根遍歷。 中序遍歷中序遍歷 若森林不空,則中序遍歷中序遍歷森林中第一棵樹的子樹森林;訪問訪問森林中第一棵樹的根結(jié)點;中序遍歷中序遍歷森林中(除第一棵樹之外)其 余樹構(gòu)成的森林。即:依次從左至右依次從左至右對森林中的每一棵樹樹進(jìn)行后根遍歷后根遍歷。 樹的遍歷和二叉樹遍歷樹的遍歷和二叉樹遍歷的對應(yīng)關(guān)系的對應(yīng)關(guān)系 ?先根遍歷先根遍歷后根遍歷后根遍歷樹樹二叉樹二叉樹森林森林先序遍歷先序遍歷先序遍歷先序遍歷中序遍歷中序遍歷中序遍歷中序遍歷三、樹遍歷算法的應(yīng)用 求樹的深度求樹的深度 輸出樹中所有從根到葉子的路徑輸出樹中所有從根到葉子的路徑 建

52、樹的存儲結(jié)構(gòu)建樹的存儲結(jié)構(gòu)typedef struct CSNode Elem data; struct CSNode *firstchild, *nextsibling; CSNode, *CSTree;1、求樹的深度算法(1)設(shè)樹的存儲結(jié)構(gòu)為孩子兄弟鏈表設(shè)樹的存儲結(jié)構(gòu)為孩子兄弟鏈表int Depth(CSTree T)if (T=NULL) return 0;elseD1 = Depth(T-firstchild);D2 = Depth(T-nextsibling);return maxd1+1,d21、求樹的深度的算法(、求樹的深度的算法(2)設(shè)樹的存儲結(jié)構(gòu)為孩子鏈表設(shè)樹的存儲結(jié)構(gòu)為孩子

53、鏈表typedef struct CTNode /*孩子結(jié)點孩子結(jié)點*/ int child; struct CTNode nextchild; *ChildPtr;typedef struct /*孩子鏈表樹的結(jié)構(gòu)孩子鏈表樹的結(jié)構(gòu)*/ CTBox nodesMAX_TREE_SIZE; int n, r; /*結(jié)點數(shù)和根結(jié)點的位置*/ CTree; typedef struct /*雙親結(jié)點雙親結(jié)點*/ Elem data; ChildPtr firstchild; /*孩子鏈的頭指針*/ CTBox;int TreeDepth( CTree T ) /*T 是樹的孩子鏈表存儲結(jié)構(gòu), 返回該

54、樹的深度*/ if ( T.n = 0) return 0; else return Depth( T, T.r ); /*TreeDepth*/int Depth( CTree T, int root ) max = 0; p = T.nodesroot.firstchild; while ( p ) h = Depth( T, p-child ); if ( h max ) max = h; p = p-nextchild; /*end while*/ return max+1; A B C DE F G H I J K例如:對左圖所示的樹,其輸出結(jié)果應(yīng)為:A B EA B FA CA D

55、 G H IA D G H JA D G H K2、輸出樹中所有從根到葉子的路徑的算法輸出樹中所有從根到葉子的路徑的算法:void AllPath( BiTree T, Stack *S ) if (T) push( S, T-data ); if (!T-Lchild & !T-Rchild ) PrintStack(S); else AllPath( T-Lchild, S ); AllPath( T-Rchild, S ); pop(S); /* end if(T)*/ /*end AllPath*/* 輸出二叉樹上從根到所有葉子結(jié)點的路徑輸出二叉樹上從根到所有葉子結(jié)點的路徑*/

56、void OutPath( Bitree T, Stack *S ) while ( T !=NULL) push(S, T-data ); if ( !T-firstchild ) Printstack(S); else OutPath( T-firstchild, S ); pop(S); T = T-nextsibling; /*end while*/ /*OutPath*/*輸出森林中所有從根到葉的路徑*/ 和二叉樹類似,不同的定義相應(yīng)有不同的算法。 假設(shè)以二元組(F,C)的形式自上而下自上而下、自左而右自左而右依次輸入樹的各邊,建立樹的孩子孩子-兄弟鏈表兄弟鏈表。3、建樹的存儲結(jié)構(gòu)的

57、算法、建樹的存儲結(jié)構(gòu)的算法:ABCDEFG例如例如:對下列所示樹的輸入序列應(yīng)為:(#, A)(A, B)(A, C)(A, D)(C, E)(C, F)(E, G)ABCD(#, A)(A, B)(A, C)(A, D)(C, E)可見,算法中需要一個隊列隊列保存已建好的結(jié)點的指針指針void CreatTree( CSTree *T ) *T = NULL; for( scanf(&fa, &ch); ch!= ; scanf(&fa, &ch);) p = GetTreeNode(ch); /*創(chuàng)建結(jié)點*/EnQueue(Q, p); /*指針入隊列*/if

58、 (fa = ) *T = p; /* 所建為根結(jié)點*/ else /*非根結(jié)點的情況*/ /*end for*/ /*end CreateTree */ 按給定的表達(dá)式建相應(yīng)二叉樹按給定的表達(dá)式建相應(yīng)二叉樹 由先綴表示式建樹由先綴表示式建樹例如:已知表達(dá)式的先綴表示式 - -+ + a b c / d e 由原表達(dá)式建樹由原表達(dá)式建樹例如:已知表達(dá)式 (a+b)c d/e d/e對應(yīng)先綴表達(dá)式 - -+ + a b c / d e的二叉樹的二叉樹abcde- -+/特點特點: 操作數(shù)為葉子葉子結(jié)點, 運(yùn)算符為分支分支結(jié)點scanf(&ch);if ( In(ch, 字母集 ) 建葉子

59、結(jié)點;else 建根結(jié)點; 遞歸建左子樹; 遞歸建右子樹;由先綴表示式建樹的算法的基本操作:由先綴表示式建樹的算法的基本操作:a+b(a+b)c d/e d/ea+bc 分析表達(dá)式和二叉樹的關(guān)系分析表達(dá)式和二叉樹的關(guān)系:abbac+abc(a+b)c/deabc+- -基本操作基本操作:scanf(&ch);if (In(ch, 字母集 ) 建葉子結(jié)點; 暫存; else if (In(ch, 運(yùn)算符集) 和前一個運(yùn)算符比較優(yōu)先數(shù); 若當(dāng)前的優(yōu)先數(shù)“高”,則暫存; 否則建子樹;void CrtExptree(BiTree *T, char exp ) InitStack(S); Pus

60、h(S, #); InitStack(PTR); char *p = exp; char ch = *p; while (!(GetTop(S)=# & ch=#) if (!IN(ch, OP) CrtNode( T, ch ); /*建葉子結(jié)點并入棧*/ else if ( ch!= # ) p+; ch = *p; /*end while*/ pop(PTR, *T); /*end CrtExptree*/ switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) CrtSubtree( t, c); / 建二叉樹并入棧建二叉樹并入棧 Pop(S, c) break; defult : / s

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論