自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論 02142 第4章.ppt

1、1,第 4 章,樹,4.1 樹的基本概念 4.2 二叉樹 4.3 二叉樹的存儲結(jié)構(gòu) 4.4 二叉樹的遍歷 4.5 樹和森林 4.6 哈夫曼樹,2,樹型結(jié)構(gòu)是一類重要的非線性結(jié)構(gòu)。樹型結(jié)構(gòu)是結(jié)點(diǎn)之間有分支，并且具有層次關(guān)系的結(jié)構(gòu)，它非常類似于自然界中的樹。樹結(jié)構(gòu)在客觀世界中是大量存在的，例如家譜、行政組織機(jī)構(gòu)都可用樹形象地表示。樹在計算機(jī)領(lǐng)域中也有著廣泛的應(yīng)用，例如在編譯程序中，用樹來表示源程序的語法結(jié)構(gòu)；在數(shù)據(jù)庫系統(tǒng)中，可用樹來組織信息；在分析算法的行為時，可用樹來描述其執(zhí)行過程等等。,4.1 樹的定義和基本術(shù)語,樹是n(n=0)個結(jié)點(diǎn)的有限集T，滿足： (1)有且僅有一個特定的稱為根的結(jié)點(diǎn)；

2、 (2)其余的結(jié)點(diǎn)可分為m(m=0)個互不相交的子集 T1,T2,T3Tm，其中每個子集Ti又是一棵樹， 并稱其為子樹。,一、樹的定義,遞歸是樹的固有特性,3,二、樹的邏輯表示 一般表示法(直觀表示法)：,b、嵌套括號法： (根(子樹,子樹子樹) ( A ( B ( E, F ), C , D ( G ) ),c、凹入法表示：,另三種表示法,a、文氏圖法：,4,三、樹的基本術(shù)語,度,結(jié)點(diǎn)的度：該結(jié)點(diǎn)的子樹數(shù)（即分支數(shù)）。,樹的度：樹中結(jié)點(diǎn)的度最大值。,結(jié)點(diǎn)由一個數(shù)據(jù)元素及若干指向其它結(jié)點(diǎn)的分支所組成。,葉子（終端結(jié)點(diǎn)）度為零的結(jié)點(diǎn)。,孩子（子結(jié)點(diǎn)）結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子。,雙親（父結(jié)點(diǎn)

3、）一個結(jié)點(diǎn)稱為該結(jié)點(diǎn)所有子樹根的雙親。,非終端結(jié)點(diǎn)度不為零的結(jié)點(diǎn)。,祖先結(jié)點(diǎn)祖先指根到此結(jié)點(diǎn)的一條路徑上的所有結(jié)點(diǎn)。,子孫從某結(jié)點(diǎn)到葉結(jié)點(diǎn)的分支上的所有結(jié)點(diǎn)稱為該結(jié) 點(diǎn)的子孫。,兄弟同一雙親的孩子之間互稱兄弟。,5,結(jié)點(diǎn)的層次從根算起，根為第一層，其孩子在第二層, .， L層上任何結(jié)點(diǎn)的孩子都在L+1層上。,堂兄弟其雙親在同一層的結(jié)點(diǎn)。,樹的深度樹中結(jié)點(diǎn)的最大層次。,森林是m（0）棵樹的集合。,有序樹若樹中各結(jié)點(diǎn)的子樹從左到右是有次序的， 不能互換，稱為有序樹。,無序樹若樹中各結(jié)點(diǎn)的子樹是無次序的， 可以互換，則成為無序樹。,6,求根Root(T):求樹T的根結(jié)點(diǎn)； 求雙親Parent(T,X

4、):求結(jié)點(diǎn)X在樹T上的雙親；若X是樹T的根或X不在T上，則結(jié)果為一特殊標(biāo)志； 求孩子Child(T,X,i):求樹T上結(jié)點(diǎn)X的第i個孩子結(jié)點(diǎn)；若X不在T上或X沒有第i個孩子，則結(jié)果為一特殊標(biāo)志； 建樹Create(X,T1,Tk),k1:建立一棵以X為根，以T1,Tk為第1,k棵子樹的樹； 剪枝Delete(T,X,i):刪除樹T上結(jié)點(diǎn)X的第i棵子樹；若T無第i棵子樹，則為空操作； 遍歷Traverse Tree(T):遍歷樹，即訪問樹中每個結(jié)點(diǎn)，且每個結(jié)點(diǎn)僅被訪問一次。,四、樹的基本操作,7,二叉樹在樹結(jié)構(gòu)的應(yīng)用中起著非常重要的作用，因為二叉樹有許多良好的性質(zhì)和簡單的物理表示，而任何樹都可以

5、與二叉樹相互轉(zhuǎn)換，這樣就解決了樹的存儲結(jié)構(gòu)及其運(yùn)算中存在的復(fù)雜性。,4.2 二叉樹,1、定義： 二叉樹是n(n=0)個結(jié)點(diǎn)的有限集合，它或為空(n=0)，或是由一個根結(jié)點(diǎn)及兩棵互不相交的左、右 子樹組成，且每棵子樹都是二叉樹。,4.2.1 二叉樹的基本概念,這是一個遞歸定義。二叉樹可以是空集合，根可以有空的左子樹 或空的右子樹。,8,2、特點(diǎn)： 二叉樹可以是空的，稱空二叉樹； 每個結(jié)點(diǎn)最多只能有兩個孩子； 子樹有左、右之分且次序不能顛倒。,、二叉樹與樹的比較：,9,二叉樹結(jié)點(diǎn)的子樹要區(qū)分左子樹和右子樹，即使只有一棵子樹也要進(jìn)行區(qū)分，說明它是左子樹，還是右子樹。這是二叉樹與樹的最主要的差別。下圖

6、列出二叉樹的5種基本形態(tài)，圖(C) 和（d）是不同的兩棵二叉樹。,(a) 空二叉樹,A,(b) 根和空的 左右子樹,A,(c) 根和左子樹,A,(d) 根和右子樹,A,(e) 根和左右子樹,二叉樹的5種形式,4.2.1 二叉樹的定義,10,初始化Initiate(BT):建立一棵空二叉樹，BT=。 求雙親Parent(BT,X):求出二叉樹BT上結(jié)點(diǎn)X的雙親結(jié)點(diǎn)，若X是BT的根或X根本不是BT上的結(jié)點(diǎn)，運(yùn)算結(jié)果為NULL。 求左孩子Lchild(BT,X)和求右孩子Rchild(BT,X)：分別求出二叉樹BT上結(jié)點(diǎn)X的左、右孩子；若X為BT的葉子或X補(bǔ)在BT上，運(yùn)算結(jié)果為NULL。 建二叉樹C

7、reate(BT):建立一棵二叉樹BT。 先序遍歷PreOrder(BT):按先序?qū)Χ鏄銪T進(jìn)行遍歷，每個結(jié)點(diǎn)被訪問一次且僅被訪問一次，若BT為空，則運(yùn)算為空操作。,4、二叉樹的基本操作（見P77）,11,中序遍歷InOrder(BT):按中序?qū)Χ鏄銪T進(jìn)行遍歷，每個結(jié)點(diǎn)被訪問一次且僅被訪問一次，若BT為空，則運(yùn)算為空操作。 后序遍歷PreOrder(BT):按后序?qū)Χ鏄銪T進(jìn)行遍歷，每個結(jié)點(diǎn)被訪問一次且僅被訪問一次，若BT為空，則運(yùn)算為空操作。 層次遍歷LevelOrder(BT):按層從上往下，同一層中結(jié)點(diǎn)按從左往右的順序，對二叉樹進(jìn)行遍歷，每個結(jié)點(diǎn)被訪問一次且僅被訪問一次，若BT為

8、空，則運(yùn)算為空操作。,12,1、性質(zhì)1： 在二叉樹的第i(i=1)層上至多有2i-1個結(jié)點(diǎn)。,二叉樹具有下列重要性質(zhì)：,4.2.2 二叉樹的性質(zhì)（）,2、性質(zhì)2：深度為k(k=1)的二叉樹至多有2k1個結(jié)點(diǎn)。,3、性質(zhì)3：對任何一棵二叉樹，如果其終端結(jié)點(diǎn) 數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0n21。 即：葉結(jié)點(diǎn)數(shù)n0=度為2的結(jié)點(diǎn)數(shù)n2+1,13,滿二叉樹中結(jié)點(diǎn)順序編號：即從第一層結(jié)點(diǎn)開始自上 而下，從左到右進(jìn)行連續(xù)編號。,滿二叉樹深度為k(k=1)且有2k-1個結(jié)點(diǎn)的二叉樹。,4.2.2 二叉樹的性質(zhì),1,2,3,4,5,6,7,14,注：滿二叉樹是完全二叉樹的特例。,完全二叉樹深度為K的

9、二叉樹中，K-1層結(jié)點(diǎn)數(shù)是滿的(2k-2 )，K層結(jié)點(diǎn)是左連續(xù)的(即結(jié)點(diǎn)編號是連續(xù)的)。如下圖（a）,4.2.2 二叉樹的性質(zhì),15,符號【x】表示不大于x的最大整數(shù)。 假設(shè)此二叉樹的深度為k，則根據(jù)性質(zhì)2及完全二叉樹的定義得到：2k-11n=2k-1 或 2k-1=n2k 取對數(shù)得到：k1log2nk 因為k是整數(shù)。所以有：klog2n1。,4、性質(zhì)4：具有n個結(jié)點(diǎn)的完全二叉樹的深 度為log2n1。,16,4.2.2 二叉樹的性質(zhì),5、性質(zhì)5： 對有n個結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層編號 （從第1層到第log2n+1層，每層從左到右), 則對任一結(jié)點(diǎn)i（1in),有： （1）如果i1，則結(jié)點(diǎn)i

10、無雙親，是二叉樹的根； 如果i1，則i的雙親Parent(A)是結(jié)點(diǎn)i/2; （2）如果2*in，則其左孩子是結(jié)點(diǎn)2*i, 否則，結(jié)點(diǎn)i無左孩子且為葉子結(jié)點(diǎn)； （3）如果2*i1n，則其右孩子是結(jié)點(diǎn)2*i1， 否則，結(jié)點(diǎn)i無右孩子。,17,思考題:,一棵完全二叉樹,結(jié)點(diǎn)總數(shù)n=980,問:,性質(zhì)4,性質(zhì)2,完全二叉樹定義,性質(zhì)3,5,31,16,31,18,1. 樹最適合用來表示( ) A.有序數(shù)據(jù)元素 B.無序數(shù)據(jù)元素 C.元素之間具有分支層次關(guān)系的數(shù)據(jù) D.元素之間無聯(lián)系的數(shù)據(jù) 2. 根據(jù)定義，樹的葉子結(jié)點(diǎn)其度數(shù)（） A. 必大于0 B. 必等于0 C.必等于1 D.必等于2 3. 對一棵

11、有100個結(jié)點(diǎn)的完全二叉樹按層序編號，則編號為49的結(jié) 點(diǎn)，它的左孩子的編號為（ ） A. 99 B. 98 C. 97 D. 50 4. 樹形結(jié)構(gòu)中，若結(jié)點(diǎn)有個兄弟，是的雙親，則的度為 _。 5. 深度為15的滿二叉樹上，第11層有 個結(jié)點(diǎn)。 6. 三個結(jié)點(diǎn)可構(gòu)成 種不同形態(tài)的二叉樹。,想一想,C,A,B,4,210=1024,5,19,它是用一組連續(xù)的存儲單元存儲二叉樹的數(shù)據(jù)元素。因此，必須把二叉樹的所有結(jié)點(diǎn)安排成為一個恰當(dāng)?shù)男蛄校Y(jié)點(diǎn)在這個序列中的相互位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系，可用編號的方法。 二叉樹的順序存儲結(jié)構(gòu)即對二叉樹按完全二叉樹進(jìn)行編號，然后用一維數(shù)組存儲，其中編號為i的結(jié)

12、點(diǎn)存儲在數(shù)組中下標(biāo)為i的分量中。 該方法稱為“以編號為地址”策略,4.3.1 二叉樹的順序存儲結(jié)構(gòu),4.3 二叉樹的存儲結(jié)構(gòu),從樹根起，自上層至下層，每層自左至右的給所有結(jié)點(diǎn)編號缺點(diǎn)是有可能對存儲空間造成極大的浪費(fèi)，在最壞的情況下，一個深度為H且只有H個結(jié)點(diǎn)的右單支樹卻需要2h-1個結(jié)點(diǎn)存儲空間。而且，若經(jīng)常需要插入與刪除樹中結(jié)點(diǎn)時，順序存儲方式不是很好！,20,對于完全二叉樹來說，采用以編號作為數(shù)組的下邊的方法將結(jié)點(diǎn)存入一位數(shù)組中，也就是將編號為i的結(jié)點(diǎn)存入一維數(shù)組的以i為下標(biāo)的數(shù)組元素中。 對于非完全二叉樹，則用某種方法將其轉(zhuǎn)化為完全二叉樹，為此可增設(shè)若干個虛擬結(jié)點(diǎn)。,1 2 3 4 5

13、6 7 8 9 10 11 12,1,2,3,4,5,6,7,8,9,10,11,12,0,Btree：,21,1 2 3 4 5 6 7 8 9 10 11 12,此方法用于完全二叉樹，則： 節(jié)省內(nèi)存 結(jié)點(diǎn)位置確定方便,22,A,B,C,D,E,F,G, 表示該處沒有元素存在,用于一般二叉樹：（浪費(fèi)空間）,用于單分支二叉樹則存儲空間浪費(fèi)極大。,1 2 3 4 5 6 7 8 9 10 11,1,2,3,4,5,6,7,8,9,10,11,23,結(jié)點(diǎn)形式：,左孩指針指向其左孩結(jié)點(diǎn)；,右孩指針指向其右孩結(jié)點(diǎn)；,二叉鏈表類型定義 typedef struct btnode Datatype dat

14、a; struct btnode *lchild,*rchild; *Bintree;二叉鏈表類型,4.3.2 二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu),二叉鏈表表示法：,24,例：,三叉鏈表表示法：,結(jié)點(diǎn)形式：,指向雙親,4.3 二叉樹的存儲結(jié)構(gòu),注：在含n個結(jié)點(diǎn)的二叉鏈表中有2n個指針域，其中 n-1個用來指向結(jié)點(diǎn)的左右孩子，其余n+1個空鏈域.,25,一、遍歷含義 在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點(diǎn)，或者對樹中全部結(jié)點(diǎn)逐一進(jìn)行某種處理。這就引入了遍歷二叉樹的問題。 遍歷二叉樹是指按一定規(guī)律對二叉樹中的每個結(jié)點(diǎn)訪問且僅訪問一次即訪遍樹中每一結(jié)點(diǎn)（只一次），打印或處理結(jié)點(diǎn)。 遍歷對線性結(jié)

15、構(gòu)是容易解決的，而二叉樹是非線性的，因而需要尋找一種規(guī)律（或次序），能把二叉樹上的各結(jié)點(diǎn)都訪問一次且只訪問一次。 二、遍歷規(guī)則,b,c,(根結(jié)點(diǎn)D),(右子樹R),(左子樹L),由二叉樹的遞歸定義知，二叉樹的三個基本組成單元是：根結(jié)點(diǎn)、左子樹和右子樹。,a,4.4 二叉樹的遍歷,26,令：L 遍歷左子樹 D 訪問根結(jié)點(diǎn) R 遍歷右子樹,組合,LDR、LRD、DLR、 RDL、RLD、DRL,先左 后右,DLR先（根）序遍歷， LDR中（根）序遍歷， LRD后（根）序遍歷。,1、先序遍歷DLR 首先訪問根結(jié)點(diǎn)，其次遍歷根的左子樹，最后遍歷根右子樹，對每棵子樹同樣按這三步（先根、后左、再右）進(jìn)行。

16、,2、中序遍歷LDR 首先遍歷根的左子樹，其次訪問根結(jié)點(diǎn)，最后遍歷根右子樹，對每棵子樹同樣按這三步（先左、后根、再右）進(jìn)行。,3、后序遍歷LRD 首先遍歷根的左子樹，其次遍歷根的右子樹，最后訪問根結(jié)點(diǎn)，對每棵子樹同樣按這三步（先左、后右、最后根）進(jìn)行。,4.4 二叉樹的遍歷,27,三、遍歷算法 1、先序遍歷（遞歸算法）： 步驟：若二叉樹為空，則退出； 否則: （1）訪問根結(jié)點(diǎn)； （2）先序遍歷根的左子樹； （3）先序遍歷根的右子樹。 算法：,void preorder ( bitreptr r ) /*先序遍歷以r為根的二叉樹*/ if (r=NULL) return; printf ( r-

17、data ) ; /*訪問根結(jié)點(diǎn)*/ preorder ( r-lchild ) ； preorder ( r-rchild ) ; /*先序遍歷以r的右孩子為根的右子樹*/ ；,4.4 二叉樹的遍歷,28,preorder(A),參數(shù)為根A 輸出A preorder(A-lchild) preorder(A-rchild),參數(shù)為根 return,遞歸調(diào)用函數(shù)preorder,參數(shù)為根B 輸出B preorder(B-lchild) Preorder(B-rchild),參數(shù)為根D 輸出D preorder(D-lchild) preorder(D-rchild),函數(shù)preorder,函數(shù)

18、preorder,參數(shù)為根 return,函數(shù)preorder,參數(shù)為根 return,函數(shù)preorder,參數(shù)為根C 輸出C preorder(C-lchild) preorder(C-rchild),函數(shù)preorder,參數(shù)為根E 輸出E preorder(E-lchild) preorder(E-rchild),參數(shù)為根 return,函數(shù)preorder,參數(shù)為根 return,函數(shù)preorder,參數(shù)為根 return,29,2、中序遍歷運(yùn)算（遞歸算法） 步驟：若二叉樹為空，則退出； 否則: （1）中序遍歷根的左子樹； （2）訪問根結(jié)點(diǎn)； （3）中序遍歷根的右子樹。 算法：,v

19、oid inorder (bitreptr r) /*中序遍歷以r為根的二叉樹*/ if (r=NULL) return; inorder ( r-lchild ) ； /*中序遍歷以r的左孩子為根的左子樹*/ printf ( r-data ) ; /*訪問根結(jié)點(diǎn)*/ inorder (r-rchild ) ; /*.*/ ,30,3、后序遍歷運(yùn)算（遞歸算法） 步驟：若二叉樹為空，則退出； 否則: （1）后序遍歷根的左子樹； （2）后序遍歷根的右子樹。 （3）訪問根結(jié)點(diǎn)； 算法：,void postorder (bitreptr r) /*后序遍歷以r為根的二叉樹*/ if (r=NULL)

20、 return; postorder ( r-lchild ) ； /*后序遍歷以r的左孩子為根的左子樹*/ postorder ( r-rchild ) ； printf ( r-data ) ; /*訪問根結(jié)點(diǎn)*/ ,31,對于如下圖的二叉樹，其先序、中序、后序遍歷的序列為：,A、B、D、F、G、C、E、H 。 B、F、D、G、A、C、E、H 。 F、G、D、B、H、E、C、A 。,先序遍歷： 中序遍歷： 后序遍歷：,32,以中序遍歷為例來說明中序遍歷二叉樹的遞歸過程,A,B,D,C,E,第一次經(jīng)過,第二次經(jīng)過,第三次經(jīng)過,33,二叉樹的層次遍歷：從二叉樹的根結(jié)點(diǎn)的這一層開始，逐層向下遍歷

21、，在每一層上按從左到右的順序?qū)Y(jié)點(diǎn)逐個訪問。,四、二叉樹的層次遍歷,右圖按照層次遍歷，所得到的的結(jié)點(diǎn)序列為：ABCDEFGH,設(shè)立一個隊列Q，用于存放結(jié)點(diǎn)，以保證二叉樹結(jié)點(diǎn)按照層次順序從左往右進(jìn)入隊列。若二叉樹bt非空： 將根結(jié)點(diǎn)插入隊列； 從隊列中刪除一個結(jié)點(diǎn)，訪問該結(jié)點(diǎn)，并將該結(jié)點(diǎn)的孩子（若有的話）插入隊列。 若此時隊列非空，再從隊列中刪除一個結(jié)點(diǎn)，訪問該結(jié)點(diǎn)，并將它的孩子結(jié)點(diǎn)插入隊列。依次重復(fù)進(jìn)行，直到隊列為空。,Void levelorder(BinTree bt) LkQue Q; InitQueue( while (!EmptyQueue(Q),p=Gethead( ,34,注：“

22、遍歷”是二叉樹各種操作的基礎(chǔ)，可以在遍歷過程中對結(jié)點(diǎn)進(jìn)行各種操作，如：對于一棵已知二叉樹 求二叉樹中結(jié)點(diǎn)的個數(shù)； 求二叉樹中葉子結(jié)點(diǎn)的個數(shù)； 求二叉樹中度為1的結(jié)點(diǎn)個數(shù)； 求二叉樹中度為2的結(jié)點(diǎn)個數(shù)； 求二叉樹中非終端結(jié)點(diǎn)個數(shù)； 交換結(jié)點(diǎn)左右孩子； 判定結(jié)點(diǎn)所在層次；,6.3 遍歷二叉樹,五、遍歷二叉樹的應(yīng)用,35,例1：編寫求二叉樹中葉結(jié)點(diǎn)個數(shù)的算法(設(shè)二叉樹的二叉鏈表的根指針為bt)。,int leafcount (bitreptr bt ) /*求二叉樹bt中葉結(jié)點(diǎn)的數(shù)目*/ if ( bt = NULL ) return (0) ; else if ( bt-lchild = NULL

23、 ,36,例2：編寫輸出二叉樹中所有度為1的結(jié)點(diǎn)的數(shù)據(jù)域的值，并統(tǒng)計其數(shù)目的算法(設(shè)二叉樹的二叉鏈表的根指針為t)。,int onesoncount(bitreptr t) /*輸出二叉樹t中度為1的結(jié)點(diǎn)值，并求其個數(shù)*/ if (t=NULL) return(0); else if (t-lchild=NULL ,37,例3：編寫輸出二叉樹中所有度為2的結(jié)點(diǎn)的數(shù)據(jù)域的值，并統(tǒng)計其數(shù)目的算法(設(shè)二叉樹的二叉鏈表的根指針為BT)。,int twoson(bitreptr BT) /*輸出二叉樹BT中所有度為2的結(jié)點(diǎn)的數(shù)據(jù)域值，并統(tǒng)計其數(shù)目*/ if (BT=NULL) return(0); el

24、se if (BT-lchild=NULL | BT-rchild=NULL) return(twoson(BT-lchild)+ twoson (BT-rchild); else if (BT-lchild!=NULL ,38,例4：編寫一算法，打印出一棵二叉樹中所有非終端結(jié)點(diǎn)的值，并統(tǒng)計非終端結(jié)點(diǎn)的個數(shù)。(二叉樹以二叉鏈表存儲，根指針為bt),int notleafcount (bitreptr bt ) /*求二叉樹bt中非葉結(jié)點(diǎn)的數(shù)目*/ if ( bt = NULL ) return (0) ; else if ( bt-lchild = NULL /* 返回總的非終端結(jié)點(diǎn)數(shù)*/ ,

25、39,例5： 編寫一算法，打印出一棵二叉樹中所有結(jié)點(diǎn)的值，并統(tǒng)計結(jié)點(diǎn)的個數(shù)。(二叉樹以二叉鏈表存儲，根指針為bt),int f5 (bitreptr bt ) /* 打印出二叉樹t中所有結(jié)點(diǎn)的值，并統(tǒng)計結(jié)點(diǎn)的個數(shù) */ if ( bt = NULL ) return (0) ; else printf(bt-data); /* 輸出結(jié)點(diǎn)值*/ n = f5( bt-lchild); /* 求左子樹的結(jié)點(diǎn)數(shù)目*/ m = f5( bt-rchild); /* 求右子樹的結(jié)點(diǎn)數(shù)目*/ return (m+n+1) ; /* 返回總的結(jié)點(diǎn)數(shù)*/ ,40,例6：設(shè)二叉樹存儲結(jié)構(gòu)采用二叉鏈表表示，每個結(jié)

26、點(diǎn)的數(shù)據(jù)域中存放一個整數(shù)。試編寫一個算法，求此二叉樹上數(shù)據(jù)域的值為的結(jié)點(diǎn)個數(shù)。,int f6 (bitreptr bt ) /*求二叉樹bt結(jié)點(diǎn)數(shù)據(jù)域值為的結(jié)點(diǎn)的數(shù)目*/ if ( bt = NULL ) return (0) ; else if (bt-data=) return(f6(bt-lchild)+f6(bt-rchild)+1); else return(f6(bt-lchild)+f6(bt-rchild); ,41,一、雙親表示法 以一組連續(xù)空間存儲樹的結(jié)點(diǎn)，即一個一維數(shù)組構(gòu)成，數(shù)組每個分量包含兩個域：數(shù)據(jù)域和雙親域。數(shù)據(jù)域用于存儲樹上一個結(jié)點(diǎn)的數(shù)據(jù)元素值，雙親域用于存儲本結(jié)

27、點(diǎn)的雙親結(jié)點(diǎn)在數(shù)組中的序號（下標(biāo)值）。,4.5 樹和森林,例：,雙親表示,每個數(shù)組元素含兩個成員，即：（結(jié)點(diǎn)值和其雙親在表中的位置）,注：找父結(jié)點(diǎn)容易，找結(jié)點(diǎn) 的孩子麻煩，需遍歷整張表。,4.5.1 樹的存儲結(jié)構(gòu)（三種）,42,根結(jié)點(diǎn)沒有雙親，雙親域的值為-1。雙親鏈表的類型定義如下：,#define size 10 typedef struct datatype data; int parent; Node; Node slistsize;,43,二、孩子鏈表表示法,樹中每個結(jié)點(diǎn)的孩子串成一單鏈表孩子鏈表,n個結(jié)點(diǎn)n個孩子鏈表,n個頭指針用順序表存儲表頭數(shù)組：數(shù)組元素存儲結(jié)點(diǎn)本身的信息和該結(jié)

28、點(diǎn)的孩子鏈表的頭指針。,孩子鏈表的結(jié)點(diǎn)為:,存放孩子結(jié)點(diǎn)在表頭數(shù)組中的序號,指向下一個孩子結(jié)點(diǎn),44,孩子鏈表表示法的類型定義：,# define MAXND 20 typedef struct bnode int child; struct bnode *next; node,*childlink; Typedef struct DataType data; childlink hp; headnode; Headnode ；linkMAXND；,45,注:在孩子鏈表表示中，找孩子方便，但 求結(jié)點(diǎn)的雙親困難，因此可在順序表中再增加一個域，用于指明每個結(jié)點(diǎn)的雙親在表中位置，即將雙親表示法和孩子

29、鏈表表示法結(jié)合起來。,46,雙親孩子表示法,樹中每個結(jié)點(diǎn)的孩子串成一單鏈表孩子鏈表,n個結(jié)點(diǎn)n個孩子鏈表,同時用一維數(shù)組順序存儲樹中的各結(jié)點(diǎn)，數(shù)組元素除了包括結(jié)點(diǎn)本身的信息和該結(jié)點(diǎn)的孩子鏈表的頭指針之外，還增設(shè)一個域，用來存儲結(jié)點(diǎn)雙親結(jié)點(diǎn)在數(shù)組中的序號。,47,parent hp,# define MAXND 20 typedef struct bnode int child; struct bnode *next; node,*childlink; Typedef struct DataType data; int parent; childlink hp; headnode; Headno

30、de ；linkMAXND；,48,三、孩子兄弟鏈表表示法（二叉鏈表表示）,結(jié)點(diǎn)形式：,指向結(jié)點(diǎn)的第一個孩子結(jié)點(diǎn),指向該結(jié)點(diǎn)的下一個兄弟結(jié)點(diǎn),例：,49,孩子兄弟鏈表表示法類型定義：,Typedef struct tnode DataType data; struct tnode *son,*brother; *Tree;,50,4.5.2 樹、森林與二叉樹的轉(zhuǎn)換,例：,方法：, 各兄弟之間加連線； 對任一結(jié)點(diǎn)，除最左孩子外，抹掉該結(jié)點(diǎn)與其余孩子的各枝； 以根為軸心，將連線順時針轉(zhuǎn)450。,51,例：,完全一樣,一棵樹唯一對應(yīng)一棵二叉樹,52,二叉樹,2、森林,森林F轉(zhuǎn)換成二叉樹的方法如下：,

31、（1）將每棵樹轉(zhuǎn)換成相應(yīng)的二叉樹； （2）將（1）中得到的各棵二叉樹的根結(jié)點(diǎn)看做是兄弟連接起來。,A,B,C,D,樹T1,E,F,樹T2,G,H,J,I,樹T3,A,B,C,D,E,F,G,H,J,I,G,H,J,I,A,B,C,D,E,F,森林F對應(yīng)的二叉樹,53,例：,方法：, 從根結(jié)點(diǎn)起； 該結(jié)點(diǎn)左孩和左孩右枝上的結(jié)點(diǎn)依次 作為該結(jié)點(diǎn)孩子； 重復(fù) 。,根無右孩的二叉樹可以轉(zhuǎn)變成一般樹。,54,4.5.3 樹和森林的遍歷,先序遍歷：先訪問根結(jié)點(diǎn)，然后依次先序 遍歷根的每棵子樹；,后序遍歷：先依次后序遍歷每棵子樹，最 后訪問根結(jié)點(diǎn)。,先序遍歷次序：？ 后序遍歷次序：？ 層次遍歷次序：？,注：

32、,層次遍歷：,ABCDE,BDCEA,ABCED,一、樹的遍歷,55,二、森林的遍歷,先序遍歷森林：訪問森林中每棵樹的根結(jié)點(diǎn)；先序遍歷森林中第一棵樹的根結(jié)點(diǎn)的子樹組成的森林；先序遍歷除去第一棵樹之外其余的樹組成的森林。 對下圖中森林進(jìn)行先序遍歷的序列為：ABCDEFGHJI 中序遍歷森林：中序訪問森林中第一棵樹的根結(jié)點(diǎn)的子樹組成的森林；訪問第一棵樹的根結(jié)點(diǎn)；中序遍歷除去第一棵樹之外其余的樹組成的森林； 對下圖中森林進(jìn)行先序遍歷的序列為：BCDAFEJHIG,A,B,C,D,E,F,G,H,J,I,56,問題：n個學(xué)生成績 a1，a2，,an （百分制），現(xiàn) 要轉(zhuǎn)換成五分制。 即 a1，a2，,

33、an 分五類： 一類： 60 不及格 二類： 60， 70 ） 及格 三類： 70， 80 ） 中等 四類： 80， 90 ） 良好 五類： 90 優(yōu)秀 每類出現(xiàn)的概率： 分?jǐn)?shù) 059 6069 7079 8089 90以上 概率 5% 15% 40% 30% 10%,4.6 判定樹和哈夫曼樹,4.6.1 分類與判定樹,57,若按順序判，得下列判斷過程：,對n個數(shù)分類花費(fèi)時間較多。因為大多數(shù)元素屬于中和良，這樣大多數(shù)數(shù)據(jù)都得通過3至4次判斷，這樣總的判斷次數(shù)就多。,改進(jìn),判定樹用于描述分類過程的二叉樹，其中：每個非終端結(jié)點(diǎn)包含一個條件，對應(yīng)一次比較；每個終端結(jié)點(diǎn)包含一個種類標(biāo)記，對應(yīng)于一種分類

34、結(jié)果。,58,5,10,15,30,40,總的判斷次數(shù)最少。因為屬于中、良的數(shù)最多，而檢驗它們的判斷少，因此總的判斷次數(shù)少。,哈夫曼樹,a,59,4.6.2 哈夫曼樹與哈夫曼算法,一、路徑長度,葉結(jié)點(diǎn)帶權(quán)的二叉樹：,結(jié)點(diǎn)ni的帶權(quán)路徑長度： 為結(jié)點(diǎn)ni到樹根的路徑長度(ni的祖先的個數(shù)li)結(jié)點(diǎn)ni所帶的權(quán)（pi）,a的路徑長度=？,27=14,60,葉結(jié)點(diǎn)帶權(quán)的二叉樹路徑長度WPL：,d的路徑長度=？ WPL=？,n WPL=(pklk)， k=1,其中：n葉子數(shù) pk第k個葉子的權(quán) lk從根到第k個葉子的路徑長度（分支數(shù)）,8,36,61,例：二叉樹有4個葉子，權(quán)分別為7，5，2，4,WP

35、L=36,WPL=?,WPL=?,(35),(46),結(jié)論： 帶權(quán)路徑長最小的二叉樹,權(quán)大的葉子離根近 權(quán)小的葉子離根遠(yuǎn),哈夫曼樹（最優(yōu)二叉樹）,二、哈夫曼樹,其特征是,62,F=T1，T2，,Tn T1，T2，,Tn 權(quán)從小到大排列, 取F中T1和T2(權(quán)最小的二棵)生成一棵二叉樹T， T為根， T1、T2分別為T的左、右子樹， T的權(quán)=T1的權(quán)+T2的權(quán)； T插入到F的余下森林中（按序）；,方法：,三、哈夫曼算法,構(gòu)造,給定n個權(quán)值 p1，p2，, pn n個葉子帶的權(quán),森林F=T1，T2，,Tn Ti只有一個帶權(quán)pi 的根結(jié)點(diǎn)，左、右子樹為空,排序,重復(fù)、，直至F=T為一棵二叉樹。,此二叉樹T即為哈夫曼樹,63,森林F= ,p= 7，5，2，4 ,例：,森林F= ,不減序列,第一步：,插入F,第二步：,插入F,第三步：,插入F,哈夫曼樹,初始森林共有n棵二叉樹，每棵樹中都僅有一個孤立