pascal數(shù)據(jù)結(jié)構(gòu)之非線性結(jié)構(gòu).doc

第一節(jié) 樹(shù)的概念教學(xué)課件下載一、樹(shù)的定義 樹(shù)是一種常見(jiàn)的非線性的數(shù)據(jù)結(jié)構(gòu)。 樹(shù)的定義：樹(shù)是n(n0)個(gè)結(jié)點(diǎn)的有限集，這個(gè)集合滿足以下條件： 有且僅有一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)（父親結(jié)點(diǎn)），該結(jié)點(diǎn)稱為樹(shù)的根； 除根外，其余的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)； 除根外，每一個(gè)結(jié)點(diǎn)都通過(guò)唯一的路徑連到根上。這條路徑由根開(kāi)始，而未端就在該結(jié)點(diǎn)上，且除根以外，路徑上的每一個(gè)結(jié)點(diǎn)都是前一個(gè)結(jié)點(diǎn)的后驅(qū)（兒子結(jié)點(diǎn)）；二、結(jié)點(diǎn)的分類 在樹(shù)中，一個(gè)結(jié)點(diǎn)包含一個(gè)元素以及所有指向其子樹(shù)的分支。 結(jié)點(diǎn)一般分成三類: 根結(jié)點(diǎn)：沒(méi)有前驅(qū)的結(jié)點(diǎn)。在樹(shù)中有且僅有一個(gè)根結(jié)點(diǎn)。如上圖（b）中的r； 分支結(jié)點(diǎn)：除根結(jié)點(diǎn)外，有后驅(qū)的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)。如上圖（b）中的a，b，c，x，t，d，i。分支結(jié)點(diǎn)亦是其子樹(shù)的根； 葉結(jié)點(diǎn)：沒(méi)有后驅(qū)的結(jié)點(diǎn)稱為樹(shù)葉。如上圖（b）中的w，h，e，f，s，m，o，n，j，u為葉結(jié)點(diǎn)。由樹(shù)的定義可知，樹(shù)葉本身也是其父結(jié)點(diǎn)的子樹(shù)。 根結(jié)點(diǎn)到每一個(gè)分支結(jié)點(diǎn)或葉結(jié)點(diǎn)的路徑是唯一的。例如上圖（b）中，從根r到結(jié)點(diǎn)i的唯一路徑為rcti。三、有關(guān)度的定義 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)的子樹(shù)數(shù)目稱為該結(jié)點(diǎn)的度。在上圖（b）中，結(jié)點(diǎn)i度為3，結(jié)點(diǎn)t的度為2，結(jié)點(diǎn)b的度為1。顯然，所有樹(shù)葉的度為0。 樹(shù)的度：所有結(jié)點(diǎn)中最大的度稱為該樹(shù)的度。圖（b）中的樹(shù)的度為3。四、樹(shù)的深度（高度） 樹(shù)是分層次的。結(jié)點(diǎn)所在的層次是從根算起的。根結(jié)點(diǎn)在第一層，根的后件在第二層，其余各層依次類推。即若某個(gè)結(jié)點(diǎn)在第k層，則該結(jié)點(diǎn)的后件均處在第k+1層。 圖（b）中的樹(shù)共有五層。在樹(shù)中，父結(jié)點(diǎn)在同一層的所有結(jié)點(diǎn)構(gòu)成兄弟關(guān)系。樹(shù)中最大的層次稱為樹(shù)的深度，亦稱高度。圖（b）中樹(shù)的深度為5。五、森林 所謂森林，是指若干棵互不相交的樹(shù)的集合。 如圖（b）去掉根結(jié)點(diǎn)r，其原來(lái)的三棵子樹(shù)Ta，Tb，Tc的集合Ta，Tb，Tc就為森林，這三棵子樹(shù)的具體形態(tài)如圖（c）。六、有序樹(shù)和無(wú)序樹(shù) 按照樹(shù)中同層結(jié)點(diǎn)是否保持有序性，可將樹(shù)分為有序樹(shù)和無(wú)序樹(shù)。如果樹(shù)中同層結(jié)點(diǎn)從左而右排列，其次序不容互換，這樣的樹(shù)稱為有序樹(shù)；如果同層結(jié)點(diǎn)的次序任意，這樣的樹(shù)稱為無(wú)序樹(shù)。第二節(jié) 樹(shù)的表示方法和存儲(chǔ)結(jié)構(gòu)一、樹(shù)的表示方法 樹(shù)的表示方法一般有兩種： 自然界的樹(shù)形表示法：用結(jié)點(diǎn)和邊表示樹(shù)，例如下圖采用的就是自然界的樹(shù)形表示法。樹(shù)形表示法一般用于分析問(wèn)題。 括號(hào)表示法：先將根結(jié)點(diǎn)放入一對(duì)圓括號(hào)中，然后把它的子樹(shù)按由左而右的順序放入括號(hào)中，而對(duì)子樹(shù)也采用同樣方法處理：同層子樹(shù)與它的根結(jié)點(diǎn)用圓括號(hào)括起來(lái)，同層子樹(shù)之間用逗號(hào)隔開(kāi)，最后用閉括號(hào)括起來(lái)。例如 下圖(b)可寫成如下形式 （r（a（w，x（d（h），e），b（f），c（s，t（i（m，o，n），j），u）二、樹(shù)的存儲(chǔ)結(jié)構(gòu) 樹(shù)的存儲(chǔ)結(jié)構(gòu)一般有兩種1.靜態(tài)的記錄數(shù)組 所有結(jié)點(diǎn)存儲(chǔ)在一個(gè)數(shù)組中，數(shù)組元素為記錄類型，包括數(shù)據(jù)域和長(zhǎng)度為n(n為樹(shù)的度)的數(shù)組，分別存儲(chǔ)該結(jié)點(diǎn)的每一個(gè)兒子的下標(biāo)。Const n=樹(shù)的度； max=結(jié)點(diǎn)數(shù)的上限；Type node=record data：； 數(shù)據(jù)域s ch：array1n of integer；指向各兒子的下標(biāo) end； treetype=array1.maxof node；Var tree：treetype；該圖用靜態(tài)數(shù)組方法保存如右表下標(biāo)數(shù)據(jù)域treei.data兒子的下標(biāo)序列treei.ch1r2342a5603b7004c89105w0006x111207f0008s0009t1314010u00011d150012e00013i16171814j00015h00016m00017o00018n000 2.動(dòng)態(tài)的多重鏈表 由于樹(shù)中結(jié)點(diǎn)可以有多個(gè)元素，所以可以用多重鏈表來(lái)描述比較方便。所謂多重鏈表，就是每個(gè)結(jié)點(diǎn)由數(shù)據(jù)域和n(n 為樹(shù)的度)個(gè)指針域共n+1個(gè)域組成，其表示方法如下：Const n=樹(shù)的度；Type treetype=node； node=record data：datatype；數(shù)據(jù)域 next：array1n of treetype；指向各兒子的指針域 end；Var root：treetype；上圖用多重鏈表表示如下：第三節(jié) 二叉樹(shù)的概念一、二叉樹(shù)的遞歸定義和基本形態(tài) 1.二叉樹(shù)是一種很重要的非線性數(shù)據(jù)結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)最多有兩個(gè)后繼，且其子樹(shù)有左右之分（次序不能任意顛倒）。 2.二叉樹(shù)是以結(jié)點(diǎn)為元素的有限集，它或者為空，或者滿足以下條件： 有一個(gè)特定的結(jié)點(diǎn)稱為根； 余下的結(jié)點(diǎn)分為互不相交的子集L和R，其中L是根的左子樹(shù)；R是根的右子樹(shù)；L和R又是二叉樹(shù)； 由上述定義可以看出，二叉樹(shù)和樹(shù)是兩個(gè)不同的概念: 樹(shù)的每一個(gè)結(jié)點(diǎn)可以有任意多個(gè)后繼，而二叉樹(shù)中每個(gè)結(jié)點(diǎn)的后繼不能超過(guò)2； 樹(shù)的子樹(shù)可以不分次序（除有序樹(shù)外）；而二叉樹(shù)的子樹(shù)有左右之分。我們稱二叉樹(shù)中結(jié)點(diǎn)的左后繼為左兒子，右后繼為右兒子。 3.二叉樹(shù)的五種基本形態(tài)二、二叉樹(shù)的兩個(gè)特殊形態(tài) 1.滿二叉樹(shù)：如果一棵二叉樹(shù)的任何結(jié)點(diǎn)，或者是樹(shù)葉，或者恰有兩棵非空子樹(shù)，則此二叉樹(shù)稱作滿二叉樹(shù)。（例如下圖(a)）可以驗(yàn)證具有n個(gè)葉結(jié)點(diǎn)的滿二叉樹(shù)共有2n-1個(gè)結(jié)點(diǎn)。 2.完全二叉樹(shù)：如果一棵二叉樹(shù)最多只有最下面兩層結(jié)點(diǎn)度數(shù)可以小于2，并且最下面一層的結(jié)點(diǎn)都集中在該層最左邊的若干位置上，則稱此二叉樹(shù)為完全二叉樹(shù)（例如下圖(b)）三、二叉樹(shù)的三個(gè)主要性質(zhì) 性質(zhì)1：在二叉樹(shù)的第i（1）層上，最多有2i-1個(gè)結(jié)點(diǎn)。 性質(zhì)2：在深度為k(k1)的二叉樹(shù)中最多有2k-1個(gè)結(jié)點(diǎn)。 性質(zhì)3：在任何二叉樹(shù)中，葉子結(jié)點(diǎn)數(shù)總比度為2的結(jié)點(diǎn)多1。四、普通有序樹(shù)轉(zhuǎn)換成二叉樹(shù)普通樹(shù)為有序樹(shù)T，將其轉(zhuǎn)化成二叉樹(shù)T的規(guī)則如下： T中的結(jié)點(diǎn)與T中的結(jié)點(diǎn)一一對(duì)應(yīng)，即T中每個(gè)結(jié)點(diǎn)的序號(hào) 和值在T中保持不變； T中某結(jié)點(diǎn)v的第一個(gè)兒子結(jié)點(diǎn)為v1，則在T中v1為對(duì)應(yīng)結(jié)點(diǎn)v的左兒子結(jié)點(diǎn)； T中結(jié)點(diǎn)v的兒子序列，在T中被依次鏈接成一條開(kāi)始于v1的右鏈； 由上述轉(zhuǎn)化規(guī)則可以看出，一棵有序樹(shù)轉(zhuǎn)化成二叉樹(shù)的根結(jié)點(diǎn)是沒(méi)有右子樹(shù)的，并且除保留每個(gè)結(jié)點(diǎn)的最左分支外，其余分支應(yīng)去掉，然后從最左的兒子開(kāi)始沿右兒子方向依次鏈接該結(jié)點(diǎn)的全部?jī)鹤?。五、森林轉(zhuǎn)換成二叉樹(shù) 如果m棵互不相交的普遍有序樹(shù)組成了森林F=T1，Tm。我們可以按下述規(guī)則將森林F轉(zhuǎn)換成一棵二叉樹(shù)b=R，LB，RB： 若F為空（m=0），則b為空樹(shù)； 若F非空（m0），則b的根R即為森林中第一棵樹(shù)的根R(T1)；b的左子樹(shù)LB是從T1的根結(jié)點(diǎn)的子樹(shù)森林F1=T11，T12，T1k轉(zhuǎn)換而成的二叉樹(shù)；其右子樹(shù)RB是從森林F2=T2，T3，Tm轉(zhuǎn)換成的二叉樹(shù)。第四節(jié) 二叉樹(shù)的遍歷一、樹(shù)的存儲(chǔ)結(jié)構(gòu)1.順序存儲(chǔ)結(jié)構(gòu) 將每個(gè)結(jié)點(diǎn)依次存放在一維數(shù)組中，用數(shù)組下標(biāo)指示結(jié)點(diǎn)編號(hào)，編號(hào)的方法是從根結(jié)點(diǎn)開(kāi)始編號(hào)1，然后由左而右進(jìn)行連續(xù)編號(hào)。每個(gè)結(jié)點(diǎn)的信息包括 一個(gè)數(shù)據(jù)域（data）； 三個(gè)指針域，其中有父結(jié)點(diǎn)編號(hào)（prt）、左兒子結(jié)點(diǎn)編號(hào)（lch）和右兒子結(jié)點(diǎn)編號(hào)（rch）。 滿二叉樹(shù)和完全二叉樹(shù)一般采用順序存儲(chǔ)結(jié)構(gòu)。Const m=樹(shù)中結(jié)點(diǎn)數(shù)上限；Type node=record結(jié)點(diǎn)類型 data：；數(shù)據(jù)值 prt，lch，rch：0m； 父結(jié)點(diǎn)、左兒子、右兒子編號(hào) end； treetype=array1m of node；二叉樹(shù)的順序表類型Var Tree：treetype；二叉樹(shù) 2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 對(duì)于一般的二叉樹(shù)，通常采用鏈?zhǔn)椒峙洌从枚劓湵肀硎疽话愕亩鏄?shù)。這種鏈?zhǔn)椒峙浼纯梢圆捎渺o態(tài)數(shù)據(jù)結(jié)構(gòu)（數(shù)組），又可以采用動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)（指針）。如果二叉樹(shù)的存儲(chǔ)需求量超過(guò)64Kb，則采用后者。由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)通常包括數(shù)據(jù)元素和兩個(gè)分支。因此二叉樹(shù)對(duì)應(yīng)的二重鏈表中每個(gè)結(jié)點(diǎn)應(yīng)有三個(gè)域： 值域： data 左指針域：lch 右指針域：rch 這種鏈表也稱為二叉鏈表。二叉鏈表頭指針bt指向二叉樹(shù)的根結(jié)點(diǎn)Type bitrpetr=node；結(jié)點(diǎn)指針類型 node=record結(jié)點(diǎn)類型 data：；值域 lch，rch：bitreptr；左指針域和右指針域 end；Var bt：bitreptr；頭指針二、二叉樹(shù)的遍歷 1.二叉樹(shù)遍歷的定義 按照一定的規(guī)律不重復(fù)地訪問(wèn)(或取出結(jié)點(diǎn)中的信息，或?qū)Y(jié)點(diǎn)作其它的處理)二叉樹(shù)中的每一個(gè)結(jié)點(diǎn)。 2.二叉樹(shù)遍歷的順序 如果用L、D、R分別表示遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)、遍歷右子樹(shù)，則對(duì)二叉樹(shù)的遍歷可以有下列六種（3!=6）組合：LDR、 LRD、 DLR、 DRL、RDL、 RLD。若再限定先左后右的次序，則只剩下三種組合：LDR（中序遍歷）、LRD（后序遍歷）、DLR（前序遍歷）。以下遍歷以該樹(shù)為例三、前序遍歷 規(guī)則如下： 若二叉樹(shù)為空，則退出。否則 訪問(wèn)處理根結(jié)點(diǎn)； 前序遍歷左子樹(shù)； 前序遍歷右子樹(shù)； 如上圖的前序遍歷結(jié)果為a b d e h i c f g順序結(jié)構(gòu):Procedue preorder(i:integer);begin if i0 then begin 訪問(wèn)處理treei.data; preorder(treei.lch);遞歸遍歷左子樹(shù) preorder(treei.rch);遞歸遍歷右子樹(shù) end;end;鏈?zhǔn)浇Y(jié)構(gòu):Procedue preorder(bt:bitreptr);begin if btnil then begin 訪問(wèn)處理bt.data; preorder(bt.lch);遞歸遍歷左子樹(shù) preorder(bt.rch);遞歸遍歷右子樹(shù) end; end;四、中序遍歷 規(guī)則如下： 若二叉樹(shù)為空，則退出；否則 中序遍歷左子樹(shù)； 訪問(wèn)處理根結(jié)點(diǎn)； 中序遍歷右子樹(shù)； 如上圖的中序遍歷結(jié)果為d b h e i a f c g順序結(jié)構(gòu):Procedue inorder(i:integer);begin if i0 then begin inorder(treei.lch);遞歸遍歷左子樹(shù) 訪問(wèn)處理treei.data; inorder(treei.rch);遞歸遍歷右子樹(shù) end;end;鏈?zhǔn)浇Y(jié)構(gòu):Procedue inorder(bt:bitreptr);begin if btnil then begin inorder(bt.lch);遞歸遍歷左子樹(shù) 訪問(wèn)處理bt.data; inorder(bt.rch);遞歸遍歷右子樹(shù) end; end;五、后序遍歷 規(guī)則如下： 若二叉樹(shù)為空，則退出；否則 后序遍歷左子樹(shù)； 后序遍歷右子樹(shù)； 訪問(wèn)處理根結(jié)點(diǎn)； 如上圖的后序遍歷結(jié)果為d h i e b f g c a順序結(jié)構(gòu):Procedue postorder(i:integer);beginif i0 then begin postorder(treei.lch);遞歸遍歷左子樹(shù) postorder(treei.rch);遞歸遍歷右子樹(shù) 訪問(wèn)處理treei.data; end;end;鏈?zhǔn)浇Y(jié)構(gòu):Procedue postorder(bt:bitreptr);begin if btnil then begin postorder(bt.lch);遞歸遍歷左子樹(shù) postorder(bt.rch);遞歸遍歷右子樹(shù) 訪問(wèn)處理bt.data; end; end;第五節(jié) 普通樹(shù)的遍歷一、先根次序遍歷樹(shù) 規(guī)則：若樹(shù)為空，則退出；否則先根訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后先根遍歷根的每棵子樹(shù)。上圖先根遍歷次序?yàn)閞 a w x d h e b f c s t i m o n j u當(dāng)普遍有序樹(shù)轉(zhuǎn)化為二叉樹(shù)時(shí)，可借用二叉樹(shù)的前序遍歷實(shí)現(xiàn)普遍有序樹(shù)的先根遍歷。二、后根次序遍歷樹(shù) 規(guī)則：若樹(shù)為空，則退出；否則先依次后根遍歷每棵子樹(shù)，然后訪問(wèn)根結(jié)點(diǎn)。 上圖后根遍歷次序?yàn)閣 h d e x a f b s m o n i j t u c r 當(dāng)普遍有序樹(shù)轉(zhuǎn)化為二叉樹(shù)時(shí)，可借用二叉樹(shù)的中序遍歷實(shí)現(xiàn)普遍有序樹(shù)的后根遍歷。三、森林的遍歷 1.先根遍歷森林 若森林非空，則可按下述規(guī)則遍歷之 訪問(wèn)森林中第一棵樹(shù)的根結(jié)點(diǎn)； 先根遍歷第一棵樹(shù)中根結(jié)點(diǎn)的子樹(shù)森林； 先根遍歷其余樹(shù)構(gòu)成的森林； 若對(duì)下圖的森林進(jìn)行先根遍歷，則得到森林的先根序列為A B D C E F G H J I。森林的先根遍歷即為其對(duì)應(yīng)的二叉樹(shù)的前序遍歷。 2.后根遍歷森林 若森林非空，則可按下述規(guī)則遍歷之 后根遍歷森林中第一棵樹(shù)的根結(jié)點(diǎn)的子樹(shù)森林； 訪問(wèn)第一棵樹(shù)的根結(jié)點(diǎn)； 后根遍歷其余樹(shù)構(gòu)成的森林； 若對(duì)上圖(a)中的森林進(jìn)行先根遍歷，則得到森林的后根序列為B C D A F E H J I G 。森林的后根遍歷即為其對(duì)應(yīng)的二叉樹(shù)的中序遍歷。例如，對(duì)上圖(c)中的二叉樹(shù)進(jìn)行中序遍歷，亦可得出對(duì)應(yīng)森林（上圖(a)的后根遍歷序列。第六節(jié) 根據(jù)兩種遍歷順序確定樹(shù)結(jié)構(gòu)一、由兩種順序確定樹(shù)結(jié)構(gòu) 遍歷二叉樹(shù)有三種規(guī)則： 前序遍歷：根左子樹(shù)右子樹(shù)； 中序遍歷：左子樹(shù)根右子樹(shù)； 后序遍歷：左子樹(shù)右子樹(shù)根； 由于前序遍歷的第一個(gè)字符和后序遍歷的最后一個(gè)字符為根，中序遍歷中位于根左方的子串和位于根右方的子串分別反映了左子樹(shù)和右子樹(shù)的結(jié)構(gòu)，因此二叉樹(shù)的形態(tài)可以由其中序與后序或者前序與中序唯一確定。但無(wú)法反映左子樹(shù)和右子樹(shù)結(jié)構(gòu)的前序遍歷與后序遍歷卻不能做到這一點(diǎn)，因此這兩個(gè)遍歷順序可對(duì)應(yīng)多種二叉樹(shù)的形態(tài)。二、由中序遍歷與后序遍歷確定前序遍歷 由二叉樹(shù)的遍歷規(guī)則可以看出，后序遍歷的最后一個(gè)字 符為根，中序遍歷中位于該字符左側(cè)的子串為左子樹(shù)中序遍歷的結(jié)果；中序遍歷中位于該字符右側(cè)的子串為右子樹(shù)中序遍歷的結(jié)果。 設(shè) 中序遍歷s1=s1sksn 后序遍歷s2=s1sn 顯然，后序遍歷中的sn為二叉樹(shù)的根。按照前序遍歷的規(guī)則輸出sn。在中序遍歷中與sn相同的字符為sk。若k1，說(shuō)明左子樹(shù)存在，位于sk左側(cè)的子串s1sk-1為左子樹(shù)中序遍歷的結(jié)果，后序遍歷中的前綴s1sk-1為左子樹(shù)后序遍歷的結(jié)果；若k1若左子樹(shù)存在，則遞歸遍歷左子樹(shù) then solve1(copy(s1，1，k-1)，copy(s2，1，k-1)； if k1若左子樹(shù)存在，則遞歸遍歷左子樹(shù) then solve2(copy(s1，1，k-1)，copy(s2，2，k-1)； if klength(s1) 若右子樹(shù)存在，則遞歸遍歷右子樹(shù) then solve2(copy(s1，k+1，length(s1)-k)，copy(s2，k+1，length(s2)-k)； end； write(s1k)；或者輸出子樹(shù)根s21end;第七節(jié) 二叉排序樹(shù)一、概念 所謂二叉排序樹(shù)是指具有下列性質(zhì)的非空二叉樹(shù) 若根結(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)的所有結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值； 若根結(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)的所有結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值； 根結(jié)的左右樹(shù)也分別為二叉排序樹(shù)； 顯然，對(duì)二叉排序樹(shù)進(jìn)行中序遍歷，可得出結(jié)點(diǎn)值遞增的排序序列。假設(shè)待排序的數(shù)存在數(shù)組a中procedure createtree;begin fillchar(b，sizeof(b)，0); b1.data:=a1; 二叉排序樹(shù)初始化 for i:=2 to n do begin bi .data:=ai; p:=1; while true do begin if aibpdata 若aibpdata，順左指針?lè)较驅(qū)ふ翼旤c(diǎn)i的插入位置 then if bpl0 then p:=bpl else begin bpl:=i;break;end else 若aibpdata 時(shí)順右指針?lè)较驅(qū)ふ翼旤c(diǎn)i的插入位置 if bpr0 then p:=bpr else begin bpr:=i; break; end; end;while end;forend;createtree第八節(jié) 最優(yōu)二叉樹(shù)(哈夫曼樹(shù))一、概念在具有n個(gè)帶權(quán)葉結(jié)點(diǎn)的二叉樹(shù)中，使所有葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和（即二叉樹(shù)的帶權(quán)路徑長(zhǎng)度）為最小的二叉樹(shù)，稱為最優(yōu)二叉樹(shù)（又稱最優(yōu)搜索樹(shù)或哈夫曼樹(shù)），即最優(yōu)二叉樹(shù)使（Wk第k個(gè)葉結(jié)點(diǎn)的權(quán)值；Pk第k個(gè)葉結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度）達(dá)到最小。二、最優(yōu)二叉樹(shù)的構(gòu)造方法假定給出n個(gè)結(jié)點(diǎn)ki(i=1n)，其權(quán)值分別為Wi(i=1n)。要構(gòu)造以此n個(gè)結(jié)點(diǎn)為葉結(jié)點(diǎn)的最優(yōu)二叉樹(shù)，其構(gòu)造方法如下： 首先，將給定的n個(gè)結(jié)點(diǎn)構(gòu)成n棵二叉樹(shù)的集合F=T1，T2，Tn。其中每棵二叉樹(shù)Ti中只有一個(gè)權(quán)值為wi的根結(jié)點(diǎn)ki，其左、右子樹(shù)均為空。然后做以下兩步 在F中選取根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹(shù)作為左右子樹(shù)，構(gòu)造一棵新的二叉樹(shù)，并且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)的權(quán)值之和； 在F中刪除這兩棵二叉樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F 重復(fù)、，直到在F中只含有一棵二叉樹(shù)為止。這棵二叉樹(shù)便是最優(yōu)二叉樹(shù)。三、最優(yōu)二叉樹(shù)的數(shù)據(jù)類型定義 在最優(yōu)二叉樹(shù)中非葉結(jié)點(diǎn)的度均為2，為滿二叉樹(shù)，因此采用順序存儲(chǔ)結(jié)構(gòu)為宜。如果帶權(quán)葉結(jié)點(diǎn)數(shù)為n個(gè)，則最優(yōu)二叉樹(shù)的結(jié)點(diǎn)數(shù)為2n-1個(gè)。 Const n=葉結(jié)點(diǎn)數(shù)的上限； m=2*n-1；最優(yōu)二叉樹(shù)的結(jié)點(diǎn)數(shù) Type node=record結(jié)點(diǎn)類型 data：；權(quán)值 prt，lch，rch,lth：0m；父指針、左、右指針和路徑長(zhǎng)度 end； wtype=array1n of ；n個(gè)葉結(jié)點(diǎn)權(quán)值的類型 treetype=array1m of node；最優(yōu)二叉樹(shù)的數(shù)組類型 Var tree：treetype； 其中tree 1n為葉結(jié)點(diǎn)，tree n+12n-1為中間結(jié)點(diǎn)，根為tree 2n-1四、構(gòu)造最優(yōu)二叉樹(shù)的算法procedure hufm(w：wtype；var tree：treetype；var bt：integer)； function min (h：integer)：integer；在前h個(gè)結(jié)點(diǎn)中選擇父指針為0且權(quán)值最小的結(jié)點(diǎn)min begin ml:=； for p:=1 to h do if (treepprt=0)and(m1treepdata) then begin i:=p；m1:=treepdata； end； min:=i； end；min begin fillchar (tree，sizeof(tree)，0)；構(gòu)造初始集合F for i:=1 to n do read(treeiData)； for k:=n+1 to m do 構(gòu)造最優(yōu)二叉樹(shù) begin 計(jì)算k為根的左兒子和右兒子 i:=min(k-1)