《數(shù)據(jù)結(jié)構(gòu)樹》PPT課件

1、樹和二叉樹版權(quán)一切, 1997 (c) Dale Carnegie & Associates, Inc.樹的初步認(rèn)識(shí)樹的定義：樹(tree)是n0個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n0時(shí)稱為空樹。當(dāng)n1時(shí)只包含一個(gè)根節(jié)點(diǎn)當(dāng)n0時(shí)除根結(jié)點(diǎn)外；其他的結(jié)點(diǎn)Tt被分割成m0個(gè)不相交的有窮子集T1Tm，其中每個(gè)這樣的子集Ti(im)本身又是一棵樹，稱為根結(jié)點(diǎn)的子樹。由此可見(jiàn)，樹的定義是一個(gè)遞歸定義。 樹的邏輯表示ABCDE樹形表示 CDEBA文氏圖表示 CBADE凹入表示 A ( B , C ( D , E ) )嵌套括號(hào)表示 樹的根本術(shù)語(yǔ) 結(jié)點(diǎn)的度和樹的度結(jié)點(diǎn)的度和樹的度每個(gè)結(jié)點(diǎn)具有的子樹數(shù)或者說(shuō)后繼結(jié)點(diǎn)數(shù)

2、每個(gè)結(jié)點(diǎn)具有的子樹數(shù)或者說(shuō)后繼結(jié)點(diǎn)數(shù)被定義為該結(jié)點(diǎn)的度被定義為該結(jié)點(diǎn)的度(degree)。一切結(jié)點(diǎn)。一切結(jié)點(diǎn)的度的最大值被定義為該樹的度。的度的最大值被定義為該樹的度。分支結(jié)點(diǎn)和葉結(jié)點(diǎn)分支結(jié)點(diǎn)和葉結(jié)點(diǎn)度大于度大于0的結(jié)點(diǎn)稱作分支結(jié)點(diǎn)或非終端結(jié)的結(jié)點(diǎn)稱作分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)；度等于點(diǎn)；度等于0的結(jié)點(diǎn)稱作葉結(jié)點(diǎn)或終端結(jié)的結(jié)點(diǎn)稱作葉結(jié)點(diǎn)或終端結(jié)點(diǎn)。點(diǎn)。 樹的根本術(shù)語(yǔ)兒結(jié)點(diǎn)、父結(jié)點(diǎn)和兄弟結(jié)點(diǎn)兒結(jié)點(diǎn)、父結(jié)點(diǎn)和兄弟結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)的子樹的根，或者說(shuō)每個(gè)結(jié)點(diǎn)的后繼，每個(gè)結(jié)點(diǎn)的子樹的根，或者說(shuō)每個(gè)結(jié)點(diǎn)的后繼，被習(xí)慣地稱作該結(jié)點(diǎn)的兒結(jié)點(diǎn)被習(xí)慣地稱作該結(jié)點(diǎn)的兒結(jié)點(diǎn)(child)，相應(yīng)地，相應(yīng)地，該結(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)互稱兄弟(sibiling)。 結(jié)點(diǎn)的層數(shù)和樹的高度結(jié)點(diǎn)的層數(shù)和樹的高度樹既是一種遞歸構(gòu)造，也是一種層次構(gòu)造，樹中樹既是一種遞歸構(gòu)造，也是一種層次構(gòu)造，樹中的每個(gè)結(jié)點(diǎn)都處在一定的層次上。結(jié)點(diǎn)的層數(shù)的每個(gè)結(jié)點(diǎn)都處在一定的層次上。結(jié)點(diǎn)的層數(shù)(level)從樹根開(kāi)場(chǎng)定義，根結(jié)點(diǎn)為第一層，它從樹根開(kāi)場(chǎng)定義，根結(jié)點(diǎn)為第一層，它的孩子結(jié)點(diǎn)為第二層，以此類推。樹中結(jié)點(diǎn)的最的孩子結(jié)點(diǎn)為第二層，以此類推。樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的深度大層數(shù)稱為樹的深度(depth)或高度或高度(height)。 樹的根本術(shù)語(yǔ)有序樹和無(wú)序樹有序

4、樹和無(wú)序樹假設(shè)樹中各結(jié)點(diǎn)的子樹是按照一定的次序從左向右假設(shè)樹中各結(jié)點(diǎn)的子樹是按照一定的次序從左向右安排的，那么稱之為有序樹，否那么稱之為無(wú)序樹。安排的，那么稱之為有序樹，否那么稱之為無(wú)序樹。 森林森林 森林是森林是m(m0)棵互不相交的樹的集合?？没ゲ幌嘟坏臉涞募?。 二叉樹的定義二叉樹(binary tree)是指樹的度為2的有序樹。它是一種最簡(jiǎn)單、而且最重要的樹。遞歸定義為：二叉樹或者是一棵空樹，或者是一棵由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的左子樹和右子樹所組成的非空樹，左子樹和右子樹又同樣都是二叉樹。 二叉樹的五種根本形狀空a空b只需一個(gè)根結(jié)點(diǎn)c只需左子樹d只需右子樹e為左、右子樹均為非空的二叉

5、樹二叉樹的根本性質(zhì)1*恣意非空二叉樹中，假設(shè)葉結(jié)點(diǎn)的數(shù)目為n0，度為2的結(jié)點(diǎn)數(shù)目為n2，那么有關(guān)系：n0= n2+1證明：二叉樹的結(jié)點(diǎn)總數(shù)n為 n= n0+n1+n2 n = B + 1 = n1+2n2+1所以 n0+n1+n2 = n1+2n2+1 即 n0= n2+1二叉樹的根本性質(zhì)2 *一棵非空二叉樹的第i層最多有2i-1個(gè)結(jié)點(diǎn)(i1) 11=2022=2134=22i2 i-1二叉樹的根本性質(zhì)3 *高度為高度為k k的二叉樹最多有的二叉樹最多有2k-12k-1個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(k1)(k1)顯然，高度為顯然，高度為k k的二叉樹只需在每一層都到達(dá)最的二叉樹只需在每一層都到達(dá)最大結(jié)點(diǎn)數(shù)時(shí)，

6、整個(gè)二叉樹的結(jié)點(diǎn)數(shù)才干到達(dá)最大。大結(jié)點(diǎn)數(shù)時(shí)，整個(gè)二叉樹的結(jié)點(diǎn)數(shù)才干到達(dá)最大。即當(dāng)每層的結(jié)點(diǎn)數(shù)目都到達(dá)該層的最大結(jié)點(diǎn)數(shù)即當(dāng)每層的結(jié)點(diǎn)數(shù)目都到達(dá)該層的最大結(jié)點(diǎn)數(shù)2i-12i-1時(shí)性質(zhì)時(shí)性質(zhì)2 2，對(duì)應(yīng)的二叉樹的結(jié)點(diǎn)數(shù)目獲得最，對(duì)應(yīng)的二叉樹的結(jié)點(diǎn)數(shù)目獲得最大值大值( (等比數(shù)列求和等比數(shù)列求和) ) 12222211011kkkiiqqasnn1)1(1滿二叉樹和完全二叉樹假設(shè)一棵二叉樹高度為k且有2k-1個(gè)結(jié)點(diǎn)，那么稱該二叉樹為滿二叉樹。滿二叉樹的特點(diǎn)就是每層的結(jié)點(diǎn)數(shù)目都到達(dá)該層的最大結(jié)點(diǎn)數(shù)。183276541514131211109滿二叉樹和完全二叉樹一個(gè)深度為K具有N個(gè)節(jié)點(diǎn)的二叉樹，假設(shè)其節(jié)點(diǎn)

7、的編號(hào)與深度為K的滿二叉樹編號(hào)為1n的節(jié)點(diǎn)完全對(duì)應(yīng)，那么稱之為完全二叉樹183276541514131211109完全二叉樹的根本性質(zhì)4*具有具有n0n0個(gè)結(jié)點(diǎn)的完全二叉樹的高度個(gè)結(jié)點(diǎn)的完全二叉樹的高度k=k=log2n+1 log2n+1 。根據(jù)完全二叉樹定義以及二叉樹的性質(zhì)根據(jù)完全二叉樹定義以及二叉樹的性質(zhì)3 3，有：，有： 2k-1 2k-11 n2k1 n2k1 1或或 2k-1n 2k 2k-1n 2k由上式可推出由上式可推出 k k1log2n k1log2n log2n完全二叉樹的根本性質(zhì)5*父子序號(hào)規(guī)律父子序號(hào)規(guī)律 假設(shè)對(duì)具有假設(shè)對(duì)具有n個(gè)結(jié)點(diǎn)的完全二叉樹按層次從上到下，每層從

8、個(gè)結(jié)點(diǎn)的完全二叉樹按層次從上到下，每層從左至右的規(guī)那么對(duì)結(jié)點(diǎn)編號(hào)，那么序號(hào)為左至右的規(guī)那么對(duì)結(jié)點(diǎn)編號(hào)，那么序號(hào)為i的結(jié)點(diǎn)具有以的結(jié)點(diǎn)具有以下性質(zhì)下性質(zhì).假設(shè)假設(shè)i1，那么序號(hào)為，那么序號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的序號(hào)為i/2 ；當(dāng)當(dāng)i=1時(shí)，那么對(duì)應(yīng)結(jié)點(diǎn)為二叉樹的根結(jié)點(diǎn)，沒(méi)有雙親結(jié)時(shí)，那么對(duì)應(yīng)結(jié)點(diǎn)為二叉樹的根結(jié)點(diǎn)，沒(méi)有雙親結(jié)點(diǎn)。點(diǎn)。假設(shè)假設(shè)2in，那么序號(hào)為，那么序號(hào)為i的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為的結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的序號(hào)為2i；假設(shè)假設(shè)2in，那么序號(hào)為，那么序號(hào)為i的結(jié)點(diǎn)無(wú)左孩子。的結(jié)點(diǎn)無(wú)左孩子。 假設(shè)假設(shè)2i1n，那么序號(hào)為，那么序號(hào)為i的結(jié)點(diǎn)的右孩子結(jié)點(diǎn)的序號(hào)的結(jié)點(diǎn)的

9、右孩子結(jié)點(diǎn)的序號(hào)為為2i+1；假設(shè)；假設(shè)2i+1n，那么序號(hào)為，那么序號(hào)為i的結(jié)點(diǎn)無(wú)右孩子。的結(jié)點(diǎn)無(wú)右孩子。 A B C D E二叉樹的存儲(chǔ)構(gòu)造一維數(shù)組表示法：一維數(shù)組表示法：用一組延續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素。用一組延續(xù)的存儲(chǔ)單元存儲(chǔ)二叉樹的數(shù)據(jù)元素。為了反映各結(jié)點(diǎn)在二叉樹中的位置及相互關(guān)為了反映各結(jié)點(diǎn)在二叉樹中的位置及相互關(guān)系，必需適當(dāng)安排各結(jié)點(diǎn)的存儲(chǔ)次序。系，必需適當(dāng)安排各結(jié)點(diǎn)的存儲(chǔ)次序。 ABCDE二叉樹的鏈?zhǔn)酱鎯?chǔ)構(gòu)造二叉鏈表：二叉鏈表：struct BTreeNode T data; BTreeNode *lchild, *rchild;；ABCDElchilddatarchi

10、ldABCDE二叉樹的鏈?zhǔn)酱鎯?chǔ)構(gòu)造三叉鏈表：三叉鏈表： struct BTreeNode T data; BTreeNode *parent, *lchild, *rchild;； A A lchildlchilddatadataparentparentrchildrchildA A A A A A A A 二叉樹結(jié)點(diǎn)類的定義template class BTree;template class BSTree;template class BTreeNode friend class BTree ; friend class BSTree ; T data; BTreeNode *lchild

11、,*rchild; public: BTreeNode():lchild(NULL),rchild(NULL); BTreeNode(T d, BTreeNode *l=NULL, BTreeNode *r=NULL) :data(d),lchild(l),rchild(r); T getdata()return data; BTreeNode *getleft()return lchild; BTreeNode *getright()return rchild;二叉樹類的定義template class BTree T *a; int n; BTreeNode *build0(int i);

12、 protected: BTreeNode *root; public: BTree(BTreeNode *p=NULL) copybt(root,p); BTree(T a,int n);/由T類型的數(shù)組a的n個(gè)元素構(gòu)造二叉樹 int num(); static int num(BTreeNode *p); int dep(); static int dep(BTreeNode *p); bool equal(BTree& bt); static bool equal(BTreeNode *p, BTreeNode *q); void copybt(BTree& bt); s

13、tatic void copybt(BTreeNode *&p, BTreeNode *q); void preorder(void visit(BTreeNode *p); static void preorder(BTreeNode *p,void visit(BTreeNode *p); ; 建立二叉鏈表lchilddata rchildDHIABCFG建立二叉鏈表 構(gòu)造函數(shù)template BTree: BTree(T a,int n) this-a=a; this-n=n; root=build0(1);BTreeNode * build0(int i)功能：以數(shù)組a中的第i

14、個(gè)元素下標(biāo)為i-1為根結(jié)點(diǎn)，遞歸地創(chuàng)建二叉鏈表，并前往指向該鏈表的指針。處置過(guò)程：(1) 假設(shè)序號(hào)為i的數(shù)組元素存在，即i小于等于數(shù)組的長(zhǎng)度且數(shù)組的第i個(gè)元素非空，那么創(chuàng)建一個(gè)結(jié)點(diǎn)作為根結(jié)點(diǎn)，在其數(shù)據(jù)域中存放數(shù)組的第i個(gè)元素。(2) 以2*i為參數(shù)，調(diào)用build0創(chuàng)建左子樹，并掛在該結(jié)點(diǎn)的左支上。(3) 以2*i+1為參數(shù)，調(diào)用build0創(chuàng)建右子樹，并掛在該結(jié)點(diǎn)的右支上。建立二叉鏈表 遞歸函數(shù)的程序代碼template BTreeNode * BTree:build0(int i) BTreeNode *p; int l,r; if (i = n) & (ai-1!= ) p=ne

15、w BTreeNode; p-data=ai-1; l=2*i; r=2*i+1; p-lchild=build0(l); p-rchild=build0(r); return(p); else return(NULL);template BTreeNode * BTree:build0(int i) BTreeNode *p; int l,r; if (i = n) & (ai-1!= ) p=new BTreeNode; p-data=ai-1; l=2*i; r=2*i+1; p-lchild=build0(l); p-rchild=build0(r); return(p); e

16、lse return(NULL);計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù) int num(BTreeNode *p)功能:前往p所指向的二叉樹的結(jié)點(diǎn)個(gè)數(shù)，處置過(guò)程：1)假設(shè)p為NULL那么前往0；否那么2)經(jīng)過(guò)遞歸調(diào)用求出左、右子樹的結(jié)點(diǎn)個(gè)數(shù)，并前往兩者之和加1template int BTree:num(BTreeNode *p) if(p=NULL) return(0); else return(num(p-lchild)+num(p-rchild)+1);實(shí)例函數(shù)，求當(dāng)前對(duì)象中的結(jié)點(diǎn)個(gè)數(shù)：template int BTree:num() return(num(root); 計(jì)算二叉樹結(jié)點(diǎn)個(gè)數(shù) templat

17、e int BTree:num(BTreeNode *p) if(p=NULL) return(0); else return(num(p-lchild)+num(p-rchild)+1);DHIABCFG互動(dòng)環(huán)節(jié):計(jì)算二叉樹的高度 int dep(BTreeNode *p) 功能:前往p所指向的二叉樹的高度，處置過(guò)程：(1)假設(shè)p為NULL那么前往0，否那么；(2)求出左、右子樹的高度l1、l2并前往max(l1+ l2)+1?；?dòng)環(huán)節(jié):計(jì)算二叉樹的高度 template int BTree:dep(BTreeNode *p) int max; if(p=NULL) return(0); e

18、lse max=dep(p-lchild); if (dep(p-rchild)max) max=dep(p-rchild); return(max+1); 實(shí)例函數(shù)求當(dāng)前對(duì)象中的高度：template int BTree:dep() return(dep(root);判別兩個(gè)二叉樹相等 bool equal(BTreeNode *p, BTreeNode *q)功能:為判別p、q所指向的兩棵二叉樹能否相等，假設(shè)相等那么前往true否那么前往false處置過(guò)程：(1) 假設(shè)p、q均為空，那么前往true；否那么，(2)假設(shè)p、q中有一個(gè)為空，那么前往false；否那么(3)假設(shè)結(jié)點(diǎn)數(shù)據(jù)和左右子

19、樹均相等，那么前往true,否那么前往false。template bool BTree:equal(BTreeNode *p,BTreeNode *q) bool b; if(p=NULL & q=NULL) b=true; else if(p=NULL | q=NULL) b=false; else b=(p-data=q-data)& equal(p-lchild,q-lchild)& equal(p-rchild,q-rchild); return(b);判別兩個(gè)二叉樹相等 equal函數(shù)的另一種方式是實(shí)例函數(shù)：bool equal(BTree& bt)

20、功能：將指定的二叉樹與當(dāng)前的二叉樹進(jìn)展比較，假設(shè)相等那么前往true否那么前往false，template bool BTree:equal(BTree& bt) return(equal(root,bt.root);復(fù)制二叉樹：拷貝函數(shù)復(fù)制二叉樹：拷貝函數(shù)void copybt(BTree& bt)功能:將參數(shù)中指定的二叉樹拷貝到當(dāng)前對(duì)象中。處置過(guò)程：(1)釋放已分配的存儲(chǔ)空間。釋放存儲(chǔ)空間的任務(wù)由dest函數(shù)完成。(2)調(diào)用相應(yīng)的遞歸函數(shù)來(lái)完成二叉樹的拷貝。void BTree:copybt(BTree& bt) dest(root); copybt(root,bt

21、.root);template void BTree:dest(BTreeNode *p) if (p!=NULL ) dest(p-lchild); dest(p-rchild); delete p; 復(fù)制二叉樹：遞歸函數(shù)復(fù)制二叉樹：遞歸函數(shù)void copybt(BTreeNode *&p,BTreeNode *q)功能:復(fù)制q所指向的二叉樹，并由p指向新復(fù)制的二叉樹。(1)假設(shè)q均為空那么設(shè)置p為空。否那么，(2)創(chuàng)建一個(gè)新的結(jié)點(diǎn)，復(fù)制結(jié)點(diǎn)q中的數(shù)據(jù)。(3)經(jīng)過(guò)遞歸調(diào)用復(fù)制左、右子樹，并掛在該結(jié)點(diǎn)的左、右兒子鏈上。template void BTree:copybt(BTreeN

22、ode *&p,BTreeNode *q) if(q=NULL) p=NULL; else p=new BTreeNode; p-data=q-data; copybt(p-lchild,q-lchild); copybt(p-rchild,q-rchild); 要留意的是參數(shù)p是結(jié)點(diǎn)指針類型，其值會(huì)有所改動(dòng)，因此必修加上援用符號(hào)&。二叉樹的遍歷 二叉樹的遍歷是指按照一定次序訪問(wèn)樹中一切結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次的過(guò)程。按根節(jié)點(diǎn)被訪問(wèn)的先后可分為先序、中序、后序先序：根節(jié)點(diǎn)、左子樹、右子樹中序：左子樹、根節(jié)點(diǎn)、右子樹后序：左子樹、右子樹、根節(jié)點(diǎn)顯然，遍歷左、右子樹的問(wèn)題依然

23、是遍歷二叉樹的問(wèn)題，所以二叉樹的這三種遍歷方式可以用遞歸算法實(shí)現(xiàn)。 二叉樹的遍歷 先序：根節(jié)點(diǎn)、左子樹、右子樹 A B D H I C F G中序：左子樹、根節(jié)點(diǎn)、右子樹 H D I B A F C G后序：左子樹、右子樹、根節(jié)點(diǎn) H I D B F G C A中序遍歷的遞歸函數(shù)與實(shí)例函數(shù) void inorder(BTreeNode *p,void visit(BTreeNode *p)功能:對(duì)p所指的二叉樹進(jìn)展中序遍歷，對(duì)每個(gè)結(jié)點(diǎn)執(zhí)行visit函數(shù)的操作，處置過(guò)程：假設(shè)p非空，那么(1)中序遍歷p所指結(jié)點(diǎn)的左子樹。(2)對(duì)根結(jié)點(diǎn)執(zhí)行visit函數(shù)的操作。(3) 中序遍歷p所指結(jié)點(diǎn)的右子樹。

24、另一種方式的inorder函數(shù)不設(shè)置結(jié)點(diǎn)指針參數(shù)，是對(duì)當(dāng)前二叉樹進(jìn)展中序遍歷，稱為實(shí)例函數(shù)。void BTree:inorder(void visit(BTreeNode *p)中序遍歷的遞歸函數(shù)與實(shí)例函數(shù)template void BTree:inorder(void visit(BTreeNode *p) inorder(root,visit); coutendl; template void BTree:inorder(BTreeNode *p, void visit(BTreeNode *p) if (p!=NULL ) inorder(p-lchild,visit); visit(p

25、); inorder(p-rchild,visit); 先序、后序遍歷的遞歸函數(shù)也與之類似中序遍歷遞歸函數(shù)的執(zhí)行過(guò)程 執(zhí)行過(guò)程：執(zhí)行過(guò)程：表達(dá)式的逆波蘭表示 a+b*c-d先序遍歷 先序序列中序遍歷 中序序列后序遍歷 后序序列逆波蘭表示ab+cd-*中序遍歷的非遞歸函數(shù)void inorder1(void visit(BTreeNode *p)其功能為對(duì)當(dāng)前二叉樹進(jìn)展非遞歸的中序遍歷，執(zhí)行visit函數(shù)的操作，其處置過(guò)程為：(1) 棧初始化，根結(jié)點(diǎn)進(jìn)棧。(2) 假設(shè)棧非空，那么棧頂結(jié)點(diǎn)的左兒子相繼進(jìn)棧，直至NULL退棧；訪問(wèn)棧頂結(jié)點(diǎn)執(zhí)行visit函數(shù)的操作并使棧頂結(jié)點(diǎn)的右兒子成為棧頂結(jié)點(diǎn)。(3

26、) 反復(fù)執(zhí)行步驟(2)直至棧為空。中序遍歷的非遞歸函數(shù)template void BTree:inorder1(void visit(BTreeNode *p) BTreeNode *stack10,*p; int top; s=; top=0;stacktop=root; while(top=0) while(stacktop!=NULL) p= stacktop-lchild; stack+top=p; top-; if (top=0) p=stacktop; visit(p); stacktop=p-rchild ; coutendl;互動(dòng)環(huán)節(jié)：二叉樹顯示為二叉樹類增設(shè)一個(gè)打印二叉樹的成

27、員函數(shù)，按二叉樹的凹入表示法打印二叉樹，其輸出的方式相當(dāng)于把二叉樹逆時(shí)針旋轉(zhuǎn)90度。設(shè)計(jì)思想：該算法的設(shè)計(jì)思想與中序遍歷二叉樹相類似。由于把二叉樹逆時(shí)針旋轉(zhuǎn)90度后顯示在上方的右子樹，然后是根節(jié)點(diǎn)，最后是左子樹，所以該算法是一種特殊的中序遍歷算法。為了使不同層次中的結(jié)點(diǎn)顯示在不同的位置上，在遞歸函數(shù)中設(shè)置一個(gè)表示遞歸調(diào)用深度的參數(shù)。遞歸打印函數(shù)的程序代碼如下：互動(dòng)環(huán)節(jié)：二叉樹顯示template void BTree:prnt(BTreeNode *p, int l) if (p!=NULL ) prnt(p-rchild,l+1); for (int i=0;i6*(l-1);i+)cout

28、 ; cout.datalchild,l+1); void prnt()prnt(root,1); 互動(dòng)環(huán)節(jié)：重置函數(shù)及其測(cè)試template void BTree:setroot(BTreeNode *p) dest(root); copybt(root,p);void main( )char *str2=abcd f; BTreebt2(str2,6); bt2.prnt(); BTreeNode *p1=new BTreeNode(x,NULL,NULL); BTreeNode *p2=new BTreeNode(y,NULL,NULL); BTreeNode *p3=new BTree

29、Node(z,p1,p2); bt2.setroot(p3); bt2.prnt(); c fa b d y z x排序二叉樹的定義排序二叉樹或?yàn)榭諛浠驗(yàn)闈M足具有以下特點(diǎn)的二叉樹：1一切結(jié)點(diǎn)的數(shù)據(jù)值均不一樣；2假設(shè)左子樹為非空，那么左子樹中一切結(jié)點(diǎn) 的值均小于根結(jié)點(diǎn)的值；3假設(shè)右子樹為非空，那么右子樹中一切結(jié)點(diǎn) 的值均大于根結(jié)點(diǎn)的值；4左子樹和右子樹均是排序二叉樹。排序二叉樹的動(dòng)態(tài)生成過(guò)程32,16,43,14,25,57,18,52,61排序二叉樹類的定義 template class BSTree : public BTree public: BSTree(BTreeNode *p=NUL

30、L)root=p; T minv(); T maxv(); BTreeNode *sear(T el); /查找實(shí)例函數(shù) BTreeNode *sear1(T el); /非遞歸查找函數(shù) static BTreeNode *sear(T el, BTreeNode *bst);/遞歸查找函 數(shù) void inst(T el); /插入實(shí)例函數(shù) void inst1(T el); /非遞歸插入函數(shù) static void inst(BTreeNode *p, BTreeNode *&bst); /遞歸插 入函數(shù) ;求排序二叉樹的最值 T minv()功能:前往當(dāng)前排序二叉樹中結(jié)點(diǎn)關(guān)鍵碼的

31、最小值。處置過(guò)程：使p=root，假設(shè)p為空，那么顯示相應(yīng)的信息，否那么(1) 假設(shè)p所指結(jié)點(diǎn)有左兒子，那么令p指向該結(jié)點(diǎn)；(2) 反復(fù)(1)，直至p所指結(jié)點(diǎn)的左兒子鏈為空；(3) 前往p所指結(jié)點(diǎn)的關(guān)鍵碼。程序代碼為：template T BSTree:minv() BTreeNode *p=root; if (p=NULL) coutemptylchild!=NULL) p=p-lchild; return p-data; 樹與森林森林是m(m0)棵互不相交的樹的集合。樹當(dāng)節(jié)點(diǎn)個(gè)數(shù) n0 時(shí)由根節(jié)點(diǎn)與M棵子樹構(gòu)成的森林所構(gòu)成。樹的存儲(chǔ)構(gòu)造：兒子雙親表示法把樹中每個(gè)結(jié)點(diǎn)的兒子節(jié)點(diǎn)陳列起來(lái)，用單

32、鏈表來(lái)存儲(chǔ)；而每個(gè)單鏈表的頭指針又組成一個(gè)線性表，同時(shí)在線性表的元素中又添加父節(jié)點(diǎn)的序號(hào)，構(gòu)成兒子雙親表示法 73625410112132425263772樹的存儲(chǔ)構(gòu)造：兒子兄弟表示法根據(jù)：從最先的祖先開(kāi)場(chǎng)，只需能確定家屬中每個(gè)人的兒子與兄弟，即可找到家屬中的每個(gè)人。 First-childdataNext-sibling樹、森林轉(zhuǎn)換成二叉樹樹轉(zhuǎn)換成二叉樹轉(zhuǎn)換方法：用兒子兄弟表示法表示一棵樹，并將兒子鏈看作為左子樹，將兄弟鏈看作為右子樹。 樹、森林轉(zhuǎn)換成二叉樹森林轉(zhuǎn)換成二叉樹，轉(zhuǎn)換方法：將第一棵樹轉(zhuǎn)換成二叉樹，將第二棵樹轉(zhuǎn)換成二叉樹，作為第一棵二叉樹的右子樹； 將第三棵樹轉(zhuǎn)換成二叉樹，作為第二

33、棵二叉樹的右子樹；以此類推樹的運(yùn)用：哈 夫 曼 樹哈夫曼樹的定義 節(jié)點(diǎn)的途徑長(zhǎng)度：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè) 結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路 徑，途徑上的分支數(shù)目稱做途徑長(zhǎng)度樹的途徑長(zhǎng)度：從樹根到每一結(jié)點(diǎn)的途徑長(zhǎng)度之和樹的帶權(quán)途徑長(zhǎng)度：被定義為從各葉結(jié)點(diǎn)到樹根之間的途徑長(zhǎng)度與結(jié)點(diǎn)上權(quán)的乘積和。 niiilwWPL1樹的運(yùn)用：哈 夫 曼 樹(a)WPL = 9262523246 (b)WPL = 6132935354 (c)WPL = 9162533345 哈夫曼樹的定義 具有具有n個(gè)帶權(quán)葉節(jié)點(diǎn)的二叉樹中個(gè)帶權(quán)葉節(jié)點(diǎn)的二叉樹中WPL最小最小的二叉樹稱為哈夫曼樹的二叉樹稱為哈夫曼樹意義：用于編碼

34、設(shè)計(jì)意義：用于編碼設(shè)計(jì) 編碼長(zhǎng)度途徑長(zhǎng)度編碼長(zhǎng)度途徑長(zhǎng)度 運(yùn)用頻率權(quán)值運(yùn)用頻率權(quán)值 報(bào)文總長(zhǎng)報(bào)文總長(zhǎng)WPL 報(bào)文總長(zhǎng)最短報(bào)文總長(zhǎng)最短WPL最小最小各類編碼哈夫曼樹的構(gòu)造設(shè)給定葉結(jié)點(diǎn)的個(gè)數(shù)n及權(quán)值集合 w1 , w2 , wn 為使二叉樹的帶權(quán)途徑長(zhǎng)度到達(dá)最小，權(quán)值越大的葉結(jié)點(diǎn)應(yīng)越接近根結(jié)點(diǎn)，而權(quán)值越小的葉結(jié)點(diǎn)那么離根結(jié)點(diǎn)越遠(yuǎn)。構(gòu)造方法如下： wplR141022936114812539628718831067951125107121811111339121513410132601112哈夫曼樹的建樹及編碼26115157341238621 12 23 34 45 56 67 7編碼方式：左分支

35、為0 ，右分支為1，反復(fù)下去，直到葉子結(jié)點(diǎn)，可以得到：樹的運(yùn)用：哈夫曼編碼生成程序 在程序中要運(yùn)用到兩種構(gòu)造類型，一種是哈夫曼樹的結(jié)點(diǎn)類型，另一種是哈夫曼編碼的構(gòu)造類型。struct HaffNode int weight; int parent; int lchild; int rchild;struct HaffCode int bitmaxlen; int start; int weight; 樹的運(yùn)用：哈夫曼編碼生成程序 void Haffman(int w,int n,HaffNode ht,HaffCode hc)int i,j,m1,m2,x1,x2; /m1、m2分別表示最小、次小的權(quán)值,x1、x2分別表示當(dāng)前分支結(jié)點(diǎn)的左右兒子 /步驟1 構(gòu)造哈夫曼樹for(i=0;i2*n-1;i+) /哈夫曼樹初始化 if(in)hti.weight=wi;else hti.weight=0; hti.parent=0; hti.lchild=-1; hti.rchild=-1; 在構(gòu)造某一個(gè)分支結(jié)點(diǎn)時(shí)運(yùn)用了一個(gè)循環(huán)for(j=0;jn+i;j+)表示從根結(jié)點(diǎn)到當(dāng)前已生成的分支結(jié)點(diǎn)