數(shù)據(jù)結(jié)構(gòu)與算法 課件 第五章樹(shù)與二叉樹(shù)

全國(guó)高等教育自學(xué)考試指定教材

計(jì)算機(jī)及應(yīng)用專業(yè)（本科段）數(shù)據(jù)結(jié)構(gòu)與算法第五章樹(shù)與二叉樹(shù)學(xué)習(xí)目標(biāo)理解樹(shù)及二叉樹(shù)的基本概念，掌握二叉樹(shù)的基本性質(zhì)掌握樹(shù)及二叉樹(shù)的存儲(chǔ)方式能夠?qū)崿F(xiàn)樹(shù)及二叉樹(shù)的基本操作及遍歷算法掌握堆的概念及基本操作的實(shí)現(xiàn)。理解優(yōu)先隊(duì)列的概念理解遞歸的概念，能夠?qū)崿F(xiàn)遞歸程序掌握樹(shù)、森林與二叉樹(shù)之間的相互轉(zhuǎn)換掌握哈夫曼樹(shù)及哈夫曼編碼的概念，能夠構(gòu)造哈夫曼樹(shù)并設(shè)計(jì)哈夫曼編碼本章主要內(nèi)容樹(shù)的基本概念12二叉樹(shù)的操作3二叉樹(shù)樹(shù)和森林5哈夫曼樹(shù)及哈夫曼編碼6堆及優(yōu)先隊(duì)列4第一節(jié)樹(shù)的基本概念樹(shù)是一種層次結(jié)構(gòu)，是一種非線性結(jié)構(gòu)日常生活中，經(jīng)常會(huì)遇到具有層次關(guān)系的示例家族中部分成員的輩份關(guān)系樹(shù)的定義定義5-1一棵樹(shù)（tree）T是由一個(gè)或一個(gè)以上的結(jié)點(diǎn)組成的有限集，其中有一個(gè)特定的結(jié)點(diǎn)R稱為樹(shù)T的根結(jié)點(diǎn)。在集合中除根結(jié)點(diǎn)R外，其余的結(jié)點(diǎn)可劃分為k(k≥0)個(gè)不相交的子集T1,T2,…,Tk，其中每個(gè)子集都是樹(shù)，并且其相應(yīng)的根結(jié)點(diǎn)R1,R2,…,Rk是R的孩子結(jié)點(diǎn)，R稱為Ri(1≤i≤k)的雙親結(jié)點(diǎn)，Ri(1≤i≤k)互稱為兄弟結(jié)點(diǎn)。子集Ti(1≤i≤k)稱為根R的子樹(shù)（subtree）樹(shù)的結(jié)點(diǎn)集合至少包含一個(gè)結(jié)點(diǎn)只含有一個(gè)結(jié)點(diǎn)的樹(shù)是只有根結(jié)點(diǎn)的樹(shù)，也就是單結(jié)點(diǎn)樹(shù)對(duì)于多結(jié)點(diǎn)的樹(shù)，必須有一個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)之間通過(guò)邊來(lái)連接，邊也稱為分支。含n個(gè)結(jié)點(diǎn)的樹(shù)有且僅有n-1條邊，這是樹(shù)的重要特性之一根結(jié)點(diǎn)的各子樹(shù)之間不會(huì)有重疊樹(shù)是一種層次結(jié)構(gòu)，也是遞歸形式的含有A,B,C,D,E,F,G,H,I,J共10個(gè)結(jié)點(diǎn)的樹(shù)TA為根結(jié)點(diǎn)，{B,E,F}，{C,G}和{D,H,I,J}構(gòu)成根結(jié)點(diǎn)A的三棵子樹(shù)，B,C,D分別是這三棵子樹(shù)的根樹(shù)中每個(gè)結(jié)點(diǎn)擁有的子樹(shù)的個(gè)數(shù)稱為結(jié)點(diǎn)的度結(jié)點(diǎn)的度即為其子結(jié)點(diǎn)的個(gè)數(shù)樹(shù)中結(jié)點(diǎn)的度的最大值稱為樹(shù)的度度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)，或終端結(jié)點(diǎn)度不為0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)如果樹(shù)中每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)之間規(guī)定了次序，則樹(shù)稱為有序樹(shù)具有同一雙親結(jié)點(diǎn)的結(jié)點(diǎn)是兄弟結(jié)點(diǎn)從任一結(jié)點(diǎn)到根結(jié)點(diǎn)之間所經(jīng)過(guò)的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的祖先結(jié)點(diǎn)以任一結(jié)點(diǎn)為根的子樹(shù)中的所有結(jié)點(diǎn)稱為該結(jié)點(diǎn)的后代將線性結(jié)構(gòu)中的前驅(qū)和后繼概念引申至樹(shù)中，將某結(jié)點(diǎn)的雙親結(jié)點(diǎn)看作是它的前驅(qū)，它的孩子結(jié)點(diǎn)看作是它的后繼除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)均只有一個(gè)前驅(qū)結(jié)點(diǎn)根的前驅(qū)結(jié)點(diǎn)個(gè)數(shù)為0，除葉結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有若干個(gè)后繼結(jié)點(diǎn)葉結(jié)點(diǎn)的后繼結(jié)點(diǎn)個(gè)數(shù)為0樹(shù)中每個(gè)元素的前驅(qū)的個(gè)數(shù)不會(huì)多于1個(gè)，后繼的個(gè)數(shù)可以是任意個(gè)樹(shù)是一種層次結(jié)構(gòu)，設(shè)根為0層，根的孩子結(jié)點(diǎn)為1層，依此類推一般地，若某個(gè)結(jié)點(diǎn)位于i（i≥0）層，則它的孩子結(jié)點(diǎn)位于i+1層樹(shù)中結(jié)點(diǎn)的最大層數(shù)定義為樹(shù)的深度最大層數(shù)加1為樹(shù)的高度樹(shù)中從某一結(jié)點(diǎn)出發(fā)，到達(dá)另一個(gè)結(jié)點(diǎn)之間所經(jīng)過(guò)的邊組成一條路徑路徑中所含的邊數(shù)為路徑長(zhǎng)度雖然樹(shù)的路徑定義中并沒(méi)有限制路徑的方向，但路徑通常是沿一個(gè)方向延伸的，即從某一結(jié)點(diǎn)向根的方向延伸，或是從某一結(jié)點(diǎn)向葉結(jié)點(diǎn)方向延伸通常，以組成路徑的結(jié)點(diǎn)序列來(lái)表示該條路徑m（m≥0）棵互不相交的樹(shù)構(gòu)成森林對(duì)樹(shù)中每個(gè)結(jié)點(diǎn)來(lái)說(shuō)，其子樹(shù)的集合即為森林第二節(jié)二叉樹(shù)定義5-2二叉樹(shù)（binarytree）是結(jié)點(diǎn)的一個(gè)有限集合，這個(gè)集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為這個(gè)根的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。左子樹(shù)和右子樹(shù)的根分別稱為此二叉樹(shù)根結(jié)點(diǎn)的左孩子結(jié)點(diǎn)和右孩子結(jié)點(diǎn)二叉樹(shù)的左子樹(shù)和右子樹(shù)都可以存在或者為空，不同的存在狀態(tài)可以組合出5種基本形態(tài)一棵高度為h的二叉樹(shù)若有2h-1個(gè)結(jié)點(diǎn)，則二叉樹(shù)稱為滿二叉樹(shù)從形式上來(lái)看，滿二叉樹(shù)中除葉結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)，即除最后一層外，每一層的結(jié)點(diǎn)都是“滿”的滿二叉樹(shù)中的n個(gè)結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，從編號(hào)為0的結(jié)點(diǎn)開(kāi)始，由連續(xù)編號(hào)的任意多個(gè)結(jié)點(diǎn)組成的二叉樹(shù)稱為完全二叉樹(shù)特殊二叉樹(shù)滿二叉樹(shù)和完全二叉樹(shù)完全二叉樹(shù)的特性

二叉樹(shù)的性質(zhì)性質(zhì)1在二叉樹(shù)的i層上最多有2i個(gè)結(jié)點(diǎn)(i≥0)證明：使用數(shù)學(xué)歸納法證明

歸納基礎(chǔ)：

對(duì)于非空的二叉樹(shù)T，根在0層，本層只有20=1個(gè)結(jié)點(diǎn)，結(jié)論成立

歸納假設(shè)：

設(shè)二叉樹(shù)T中i-1層最多有2i-1個(gè)結(jié)點(diǎn)，考慮i層，由于i層的結(jié)點(diǎn)均為i-1層結(jié)點(diǎn)的孩子結(jié)點(diǎn)，而二叉樹(shù)中每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)，故i層最多有2

2i-1=2i個(gè)結(jié)點(diǎn)

根據(jù)歸納法原理，性質(zhì)1得證

性質(zhì)3對(duì)任何非空二叉樹(shù)T，設(shè)n0是葉結(jié)點(diǎn)的個(gè)數(shù)，n2是度為2的結(jié)點(diǎn)的個(gè)數(shù)，則有n0=n2+1證明：設(shè)二叉樹(shù)T中度為1的結(jié)點(diǎn)個(gè)數(shù)為n1，則T中結(jié)點(diǎn)總數(shù)n為 n=n0+n1+n2 n-1=2

n2+1

n1+0

n0

將上兩式聯(lián)立求解，得到 n0=n2+1

例5-3一棵二叉樹(shù)共有20個(gè)結(jié)點(diǎn)，其中葉結(jié)點(diǎn)為5個(gè)，則度為l的結(jié)點(diǎn)個(gè)數(shù)是（）。A．11B．9C．6D．4答案為A二叉樹(shù)的存儲(chǔ)——順序存儲(chǔ)結(jié)構(gòu)對(duì)于完全二叉樹(shù)，各層自上至下，同層間自左至右，將結(jié)點(diǎn)依次存入數(shù)組從前至后的各個(gè)元素中。按照前面使用過(guò)的編號(hào)方法，一般來(lái)講，編號(hào)為i的結(jié)點(diǎn)存放在數(shù)組中下標(biāo)為i的位置使用這樣的存儲(chǔ)規(guī)則可以很方便地找到二叉樹(shù)中的相關(guān)結(jié)點(diǎn)，即若知道二叉樹(shù)某一結(jié)點(diǎn)保存在數(shù)組中下標(biāo)i的位置，則可以很方便地求出它的雙親結(jié)點(diǎn)（若存在）和左、右孩子結(jié)點(diǎn)（若存在）在數(shù)組中的位置對(duì)于一般的二叉樹(shù)，順序存儲(chǔ)的思想是，針對(duì)二叉樹(shù)中的每個(gè)位置，不論這個(gè)位置有沒(méi)有結(jié)點(diǎn)，都在數(shù)組中預(yù)留保存空間。采用這種存儲(chǔ)方式保存完全二叉樹(shù)時(shí)，既不浪費(fèi)空間，又便于有關(guān)操作的實(shí)現(xiàn)例5-4設(shè)高度為k（k≥1）的二叉樹(shù)T采用順序存儲(chǔ)結(jié)構(gòu)保存在數(shù)組B[2k-1]中，在沒(méi)有保存T中元素的數(shù)組位置中，保存一個(gè)區(qū)別于T中元素的特殊標(biāo)記。B中保存的特殊標(biāo)記個(gè)數(shù)最多為（）。A．k-1B．2k-1C．2k-k-1D．2k-1答案為C鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義一個(gè)結(jié)點(diǎn)結(jié)構(gòu)：它含有兩個(gè)指針域，一個(gè)指針用來(lái)指向該結(jié)點(diǎn)左孩子所在的結(jié)點(diǎn)，稱為左孩子指針，簡(jiǎn)稱為左指針；另一個(gè)指針用來(lái)指向該結(jié)點(diǎn)右孩子所在的結(jié)點(diǎn)，稱為右孩子指針，簡(jiǎn)稱為右指針。此外，還定義一個(gè)用來(lái)保存結(jié)點(diǎn)中數(shù)據(jù)的數(shù)據(jù)域二叉鏈表表示二叉樹(shù)結(jié)點(diǎn)類的定義及二叉樹(shù)的定義二叉鏈表中結(jié)點(diǎn)類的定義及二叉樹(shù)的定義typedefintELEMType;typedefstructBNode //二叉樹(shù)結(jié)點(diǎn){ ELEMTypedata; //數(shù)據(jù)域 structBNode*left,*right;

//指向左孩子、右孩子的指針}BinTNode;typedefBinTNode*BTree; //二叉樹(shù)二叉鏈表中到底有多少空指針域呢設(shè)二叉樹(shù)中有n個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)都含有兩個(gè)指針域，則二叉鏈表中共有2

n個(gè)指針域已知含n個(gè)結(jié)點(diǎn)的樹(shù)中僅含有n-1個(gè)分支，即只有n-1個(gè)指針域不為空，則其余的n+1個(gè)指針域均為空可以看出，二叉鏈表中有超過(guò)一半的指針域都是空的，這些都是結(jié)構(gòu)性開(kāi)銷第三節(jié)二叉樹(shù)的操作二叉樹(shù)的生成按照二叉樹(shù)的順序存儲(chǔ)方式，將二叉樹(shù)各結(jié)點(diǎn)值保存在一維數(shù)組中，然后建立二叉鏈表如要建立如下的二叉鏈表輸入的數(shù)組是inta[]={0,1,2,3,4,NA,5,NA,NA,NA,NA,NA,NA,6};函數(shù)CreateBinaryTree遞歸處理二叉鏈表的生成調(diào)用它的主程序中先創(chuàng)建一個(gè)根結(jié)點(diǎn)，其中保存數(shù)組首元素的值，該結(jié)點(diǎn)作為參數(shù)傳遞給函數(shù)CreateBinaryTree。這個(gè)結(jié)點(diǎn)的位置是下標(biāo)0，將這個(gè)位置值也作為參數(shù)傳給函數(shù)CreateBinaryTree主程序中BTreeroot;root=(BTree)malloc(sizeof(BinTNode));root->data=a[0];root->left=NULL;root->right=NULL;調(diào)用函數(shù)CreateBinaryTree。參數(shù)0是起始位置CreateBinaryTree(0,n,a,root);生成二叉鏈表如果下標(biāo)i處的結(jié)點(diǎn)有左孩子，則其應(yīng)該保存在下標(biāo)2

i+1處如果有右孩子，則應(yīng)該保存在下標(biāo)2

i+2處故在函數(shù)內(nèi)，判斷數(shù)組中位置2

i+1及位置2

i+2處是否保存了元素值如果確實(shí)有值，則分配空間創(chuàng)建結(jié)點(diǎn)且保存數(shù)組中相應(yīng)位置的元素值，并讓下標(biāo)i處結(jié)點(diǎn)的相應(yīng)指針指向新創(chuàng)建的結(jié)點(diǎn)然后再以2

i+1或2

i+2為參數(shù)值，遞歸調(diào)用函數(shù)，去處理2

i+1或2

i+2位置處結(jié)點(diǎn)的左孩子和右孩子如果數(shù)組中數(shù)據(jù)的存儲(chǔ)是正確的，則能正確建立二叉鏈表。如果位置2

i+1或位置2

i+2處沒(méi)有保存元素值，則遞歸結(jié)束二叉樹(shù)的遍歷對(duì)非空的二叉樹(shù)的遍歷可以相應(yīng)地分解為三項(xiàng)“子任務(wù)”訪問(wèn)根結(jié)點(diǎn)遍歷左子樹(shù)（即依相應(yīng)的規(guī)律訪問(wèn)左子樹(shù)中的全部結(jié)點(diǎn)）遍歷右子樹(shù)（即依相應(yīng)的規(guī)律訪問(wèn)右子樹(shù)中的全部結(jié)點(diǎn)）常規(guī)的3種遍歷算法分別是先序遍歷、中序遍歷和后序遍歷。這3種遍歷也分別稱為先根遍歷、中根遍歷和后根遍歷先序遍歷算法若二叉樹(shù)為空，則返回；否則依次執(zhí)行以下操作（1）訪問(wèn)根結(jié)點(diǎn)（2）先序遍歷左子樹(shù)（3）先序遍歷右子樹(shù)中序遍歷算法若二叉樹(shù)為空，則返回；否則依次執(zhí)行以下操作（1）中序遍歷左子樹(shù)（2）訪問(wèn)根結(jié)點(diǎn)（3）中序遍歷右子樹(shù)后序遍歷算法若二叉樹(shù)為空，則返回；否則依次執(zhí)行以下操作（1）后序遍歷左子樹(shù)（2）后序遍歷右子樹(shù)（3）訪問(wèn)根結(jié)點(diǎn)先序遍歷過(guò)程中序遍歷過(guò)程后序遍歷過(guò)程例5-6寫(xiě)出其先序、中序及后序遍歷序列先序遍歷序列為A,B,D,G,H,J,K,E中序遍歷序列為G,D,J,H,K,B,E,A后序遍歷序列為G,J,K,H,D,E,B,A先序遍歷算法先序遍歷算法中序遍歷算法中序遍歷算法后序遍歷算法后序遍歷算法給出二叉樹(shù)的先序遍歷序列和中序遍歷序列，能唯一確定該二叉樹(shù)給出二叉樹(shù)的后序遍歷序列和中序遍歷序列，能唯一確定該二叉樹(shù)例5-7設(shè)二叉樹(shù)T的先序遍歷序列是A,B,D,G,H,J,K,E，中序遍歷序列是G,D,J,H,K,B,E,A，畫(huà)出二叉樹(shù)T由先序遍歷序列可知，T的根是A在中序遍歷序列中查找A的位置，位于A前面的是其左子樹(shù)的中序遍歷序列，位于A后面的是其右子樹(shù)的中序遍歷序列從而將原問(wèn)題的求解（對(duì)整棵樹(shù)的還原）分解為兩個(gè)更小問(wèn)題的求解（對(duì)兩棵子樹(shù)的還原）例5-8統(tǒng)計(jì)以二叉鏈表表示的二叉樹(shù)T中葉結(jié)點(diǎn)的個(gè)數(shù)T中葉結(jié)點(diǎn)的個(gè)數(shù)等于根左子樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)加上根右子樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)。所以如果遞歸調(diào)用已經(jīng)得到了兩棵子樹(shù)中葉結(jié)點(diǎn)的個(gè)數(shù)，那么將結(jié)果相加即求解例5-9編寫(xiě)程序，返回二叉樹(shù)T的高度仍是使用遞歸的思想去編寫(xiě)程序。如果左子樹(shù)的高度和右子樹(shù)的高度都已經(jīng)知道，則二叉樹(shù)T的高度就可求得，樹(shù)的高度是兩棵子樹(shù)中較高者的高度再加1層序遍歷所謂按層遍歷，即是從根結(jié)點(diǎn)開(kāi)始逐層向下遍歷，直到最后一層對(duì)于同一層的結(jié)點(diǎn)，由左到右遍歷各結(jié)點(diǎn)同一層中的結(jié)點(diǎn)相繼被訪問(wèn)，同時(shí)，它們之間的相對(duì)次序也決定著它們孩子結(jié)點(diǎn)的相對(duì)次序。即同一層中的結(jié)點(diǎn)u和結(jié)點(diǎn)v，若先遍歷u再遍歷v，則u的孩子結(jié)點(diǎn)的遍歷也早于v的孩子結(jié)點(diǎn)的遍歷按層進(jìn)行遍歷先訪問(wèn)最上面一層即0層中的元素，輸出1然后依次訪問(wèn)1的子結(jié)點(diǎn)2和3再繼續(xù)訪問(wèn)2的子結(jié)點(diǎn)和3的子結(jié)點(diǎn)依此類推，得到的層序遍歷結(jié)果是：1,2,3,4,5,6,7層序遍歷算法二叉樹(shù)層序遍歷的算法遍歷的非遞歸實(shí)現(xiàn)仍然將一棵二叉樹(shù)分為三部分：根、左子樹(shù)和右子樹(shù)。從根開(kāi)始遍歷二叉樹(shù)時(shí)，根的左子樹(shù)和右子樹(shù)的遍歷不能同時(shí)進(jìn)行，只能先遍歷一棵子樹(shù)，同時(shí)保存二叉樹(shù)中尚不能遍歷部分的信息，留待一棵子樹(shù)處理完畢后再處理分析二叉樹(shù)的遍歷過(guò)程可知，使用棧來(lái)保存相關(guān)信息先序遍歷算法在進(jìn)入左子樹(shù)進(jìn)行處理之前，需要在棧中保存右子樹(shù)的相關(guān)信息，以便當(dāng)左子樹(shù)處理完畢，能夠根據(jù)保存的線索找到右子樹(shù)的根。所以，棧中保存右子樹(shù)的根即可程序中序遍歷算法中序遍歷時(shí)，先進(jìn)行左子樹(shù)的遍歷，然后遍歷根，再遍歷右子樹(shù)。所以棧中保存根的信息，遍歷完左子樹(shù)后，從棧中找到根，訪問(wèn)根，同時(shí)也能容易地找到右子樹(shù)程序后序遍歷算法類似于中序遍歷過(guò)程，在進(jìn)入左子樹(shù)遍歷之前，需要先保存根的信息。當(dāng)左子樹(shù)遍歷結(jié)束，從棧中找到根，但此時(shí)因?yàn)橛易訕?shù)尚未遍歷，所以根并不能從棧中彈出，仍需要保存在棧中，只有當(dāng)右子樹(shù)也遍歷結(jié)束后，才能訪問(wèn)根棧中保存的結(jié)點(diǎn)需要入棧兩次出棧兩次。為了能有所區(qū)別，二叉樹(shù)結(jié)點(diǎn)入棧時(shí)，附帶一個(gè)標(biāo)記位flag。第一次出棧時(shí)，并不訪問(wèn)結(jié)點(diǎn)。第二次出棧時(shí)才訪問(wèn)它將二叉樹(shù)結(jié)點(diǎn)和標(biāo)記組合在一起，定義新的棧的類型，專用于非遞歸實(shí)現(xiàn)二叉樹(shù)的后序遍歷過(guò)程typedefstruct SNode //進(jìn)棧帶標(biāo)記結(jié)點(diǎn){ BinTNodebtreeNode; //二叉樹(shù)結(jié)點(diǎn)

intflag; //標(biāo)記}StackTNode; typedefstruct{ //用于后序遍歷的棧 StackTNodeelement[maxSize]; inttop; //棧頂位置}SeqBTreeStackforPostT;程序二叉樹(shù)的應(yīng)用可以使用二叉樹(shù)來(lái)表示一個(gè)表達(dá)式，這樣的二叉樹(shù)稱為表達(dá)式樹(shù)2*y*(a+3*y)-b畫(huà)出表達(dá)式樹(shù)先根據(jù)運(yùn)算符的優(yōu)先級(jí)對(duì)表達(dá)式加括號(hào)去掉最外層括號(hào)。中間的運(yùn)算符為根，前后兩部分分別對(duì)應(yīng)于左子樹(shù)和右子樹(shù)對(duì)左子樹(shù)遞歸執(zhí)行步驟②對(duì)右子樹(shù)遞歸執(zhí)行步驟②當(dāng)遇到空串時(shí)，遞歸結(jié)束例5-12已知算術(shù)表達(dá)式的中綴形式為A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為（）A．-A+B*C/DEB．-A+B*CD/EC．-+*ABC/DED．-+A*BC/DE答案：D

第四節(jié)堆及優(yōu)先隊(duì)列前一種關(guān)系表明，任何一個(gè)分支結(jié)點(diǎn)的值都不大于它子結(jié)點(diǎn)的值，所以樹(shù)根結(jié)點(diǎn)的值是全部結(jié)點(diǎn)中的最小值。這樣的堆稱為最小堆或小根堆后一種關(guān)系表明，任何一個(gè)分支結(jié)點(diǎn)的值都不小于它子結(jié)點(diǎn)的值，故樹(shù)根結(jié)點(diǎn)的值是全部結(jié)點(diǎn)中的最大值。這樣的堆稱為最大堆或大根堆樹(shù)根結(jié)點(diǎn)稱為堆頂堆的定義中還隱含了遞歸的含義，當(dāng)用完全二叉樹(shù)的形式表示堆時(shí)，樹(shù)中的任意一棵子樹(shù)都可以構(gòu)成堆，并且保持與原來(lái)同樣的性質(zhì)最大堆中任何結(jié)點(diǎn)的子樹(shù)仍是最大堆最小堆中任何結(jié)點(diǎn)的子樹(shù)仍是最小堆最小堆和最大堆堆的類型定義#defineHeapSize30 //堆的容量typedefintELEMType; //元素類型typedefstructHeap{ ELEMTypeheap[HeapSize]; //存放元素的數(shù)組 intn; //堆中當(dāng)前元素個(gè)數(shù)};堆的基本操作intcreatHeap(maxHeap*H,ELEMTypearr[],intn); //創(chuàng)建堆intinsertHeap(maxHeap*H,ELEMTypex); //在堆中插入元素xintdeleteHeap(maxHeap*H,ELEMType*x); //刪除堆頂元素intisHeapEmpty(maxHeap*H); //如果堆為空，則返回1，否則返回0intisHeapFull(maxHeap*H); //如果堆為滿，則返回1，否則返回0最大堆的類型定義#defineHeapSize30 //堆的容量typedefintELEMType; //元素類型typedefstructmaxHeap{ ELEMTypeheap[HeapSize]; //存放元素的數(shù)組 intn; //堆中當(dāng)前元素個(gè)數(shù)};判空、判滿創(chuàng)建最大堆向最大堆中插入新元素刪除堆頂元素例5-1370,13,65,24,56,48,92,86，將其建成最大堆例5-14在最大堆中插入新元素40例5-15刪除最大堆的堆頂優(yōu)先隊(duì)列一些應(yīng)用中，各元素本身還被賦予一個(gè)優(yōu)先值，可以用一個(gè)非負(fù)整數(shù)表示優(yōu)先值。優(yōu)先值也稱為優(yōu)先權(quán)。具有優(yōu)先值的各元素保存在一個(gè)結(jié)構(gòu)中，這個(gè)結(jié)構(gòu)稱為優(yōu)先隊(duì)列。輸出時(shí)，選擇最優(yōu)先的元素輸出?！白顑?yōu)先”取決于優(yōu)先值的定義，可以是優(yōu)先值最小，也可以是優(yōu)先值最大。第五節(jié)樹(shù)和森林樹(shù)的存儲(chǔ)結(jié)構(gòu)父結(jié)點(diǎn)表示法孩子結(jié)點(diǎn)表示法孩子-兄弟表示法父結(jié)點(diǎn)表示法樹(shù)中每個(gè)結(jié)點(diǎn)至少含兩個(gè)域，一個(gè)域用來(lái)保存結(jié)點(diǎn)本身的值，另一個(gè)域用來(lái)保存結(jié)點(diǎn)之父結(jié)點(diǎn)的相關(guān)信息孩子結(jié)點(diǎn)表示法父結(jié)點(diǎn)-孩子結(jié)點(diǎn)表示法孩子-兄弟表示法為樹(shù)中的每個(gè)結(jié)點(diǎn)定義一個(gè)存儲(chǔ)結(jié)點(diǎn)，其中有左、右兩個(gè)指針域，左指針域指向這個(gè)結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)，右指針域指向這個(gè)結(jié)點(diǎn)的下一個(gè)兄弟結(jié)點(diǎn)樹(shù)、森林與二叉樹(shù)的轉(zhuǎn)換樹(shù)和二叉樹(shù)都可以用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)同一個(gè)二叉鏈表，若按樹(shù)的存儲(chǔ)含義來(lái)解釋，可以還原為樹(shù)。若按二叉樹(shù)的存儲(chǔ)含義來(lái)解釋，可以還原為二叉樹(shù)正是因?yàn)檫@一點(diǎn)，可以在樹(shù)與二叉樹(shù)之間建立一種對(duì)應(yīng)關(guān)系轉(zhuǎn)換規(guī)則規(guī)則1：將森林轉(zhuǎn)換成二叉樹(shù)設(shè)F={T1,T2,…,Tm}是森林，則可按如下規(guī)則將森林F轉(zhuǎn)換為一棵二叉樹(shù)B=(root,LB,RB)（1）若F為空（m=0），則B為空樹(shù)（2）若F非空（m>0），則森林中T1的根作為二叉樹(shù)B的根root；T1中各子樹(shù)組成的森林F1={T11,T12,…,T1s}轉(zhuǎn)換成的二叉樹(shù)作為B的左子樹(shù)BL；森林F’={T2,T3,…,Tm}轉(zhuǎn)換成的二叉樹(shù)作為B的右子樹(shù)BR森林轉(zhuǎn)換為二叉樹(shù)轉(zhuǎn)換規(guī)則規(guī)則2：將二叉樹(shù)還原為森林設(shè)B=(root,BL,BR)是一棵二叉樹(shù)，則可按如下規(guī)則轉(zhuǎn)換成森林F={T1,T2,…,Tm}（1）若B為空，則F為空（2）若B非空，則B的根root作為F中第一棵樹(shù)T1的根；B的左子樹(shù)BL還原得到的森林作為T(mén)1的各子樹(shù)；B的右子樹(shù)BR還原得到的森林作為F中的T2,T3,…,Tm樹(shù)和森林的遍歷樹(shù)的兩種遍歷策略先序（根）遍歷先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，再依次先序遍歷根結(jié)點(diǎn)的各棵子樹(shù)后序（根）遍歷若樹(shù)的根結(jié)點(diǎn)有子樹(shù)，則首先后序遍歷各棵子樹(shù)，然后再訪問(wèn)根結(jié)點(diǎn)；否則（根結(jié)點(diǎn)無(wú)子樹(shù)），只訪問(wèn)根結(jié)點(diǎn)森林的兩種遍歷策略先序遍歷森林森林的先序遍歷過(guò)程，是按照樹(shù)的排列次序，先序遍歷各棵樹(shù)后序遍歷森林森林的后序遍歷過(guò)程，是按照樹(shù)的排列次序，后序遍歷各棵樹(shù)可以看出，森林的遍歷序列中，各棵樹(shù)中的結(jié)點(diǎn)不會(huì)混雜在一起森林與對(duì)應(yīng)的二叉樹(shù)的遍歷序列的關(guān)系二叉樹(shù)的先序遍歷序列和中序遍歷序列，與森林的先序遍歷序列和后序遍歷序列分別相同第六節(jié)哈夫曼樹(shù)及哈夫曼編碼編碼ASCII編碼、Unicode碼、電報(bào)碼定長(zhǎng)編碼算法簡(jiǎn)單，效率高在編碼長(zhǎng)度確定之后，譯文的長(zhǎng)度完成取決于原文的長(zhǎng)度變長(zhǎng)編碼變長(zhǎng)編碼前綴特性：一個(gè)編碼方案中，任何一個(gè)字符的編碼都不是該方案中任何其他字符編碼的前綴，這樣的編碼稱為具有前綴特性正是因?yàn)榫幋a方案具有前綴特性，才能夠保證譯碼過(guò)程的正確性和唯一性。可以使用二叉樹(shù)來(lái)表示一個(gè)編碼方案在二叉樹(shù)的分支上標(biāo)注0或1，從根到某結(jié)點(diǎn)的路徑上，各分支標(biāo)注的0或1組成一個(gè)編碼哈夫曼樹(shù)二叉樹(shù)中，葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度定義為葉結(jié)點(diǎn)的權(quán)值乘上其到根結(jié)點(diǎn)的路徑長(zhǎng)度二叉樹(shù)的帶權(quán)路徑長(zhǎng)度，就是樹(shù)中所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和二叉樹(shù)的外部帶權(quán)路徑長(zhǎng)度記為WPL其中n為葉結(jié)點(diǎn)個(gè)數(shù)，wk為第k個(gè)葉結(jié)點(diǎn)的權(quán)值，lk為第k個(gè)葉結(jié)點(diǎn)的路徑長(zhǎng)度各字符出現(xiàn)的頻度分別是6、12、25、30，構(gòu)造4棵二叉樹(shù)，分別計(jì)算其WPL值4棵二叉樹(shù)的帶權(quán)路徑長(zhǎng)度WPL分別為134、195、139和146我們的任務(wù)是構(gòu)造具有最小WPL且滿足前綴特性的編碼樹(shù)設(shè)有n個(gè)權(quán)值{w1,w2,…,wn}，構(gòu)造具有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，每個(gè)葉結(jié)點(diǎn)帶有一個(gè)權(quán)值wi。在所有這樣的二叉樹(shù)中，帶權(quán)路