最優(yōu)二叉樹(哈夫曼樹)

1、實(shí)驗(yàn)4.2最優(yōu)二叉樹（哈夫曼樹）、實(shí)驗(yàn)的目的要求1、了解樹和哈夫曼樹的特性，以及它們?cè)趯?shí)際問題中的應(yīng)用。2、掌握樹和哈夫曼樹的實(shí)現(xiàn)方法以及它們的基本操作，學(xué)會(huì)運(yùn)用樹和二叉樹來解決問 題。、實(shí)驗(yàn)的主要內(nèi)容1、請(qǐng)?jiān)O(shè)計(jì)一個(gè)算法，對(duì)于給定的n個(gè)結(jié)點(diǎn)的權(quán)值，建立一棵哈夫曼樹。 具體要求如下: 算法輸入：n個(gè)結(jié)點(diǎn)的權(quán)值。 算法輸出：哈夫曼樹，打印出哈夫曼樹的所有的結(jié)點(diǎn)序號(hào)、雙親結(jié)點(diǎn)、左孩子、右孩 子和權(quán)值。 測(cè)試數(shù)據(jù)：設(shè)結(jié)點(diǎn)數(shù)n=7,權(quán)值分別為7、5、2、3、8、10、20 ；設(shè)結(jié)點(diǎn)數(shù)n=8,權(quán)值分別為 7、19、2、6、32、3、21、10。三、解題思路圖5-L哈夫曼啊示世圖1、 哈夫曼樹的存儲(chǔ)結(jié)構(gòu)：用

2、哈夫曼算法求得的哈夫曼樹中共有 2n-l個(gè)結(jié)點(diǎn)，其中n個(gè)葉結(jié)點(diǎn)是初始森林中的n個(gè)孤立結(jié)點(diǎn)，其余 n-1個(gè)結(jié)點(diǎn)是構(gòu)造過程中生成的度為2的結(jié)點(diǎn)。因此，有2n-l個(gè)結(jié)點(diǎn)的哈天曼樹可用大小為2n-l的向量來存儲(chǔ)。每個(gè)結(jié)點(diǎn)包括4個(gè)域：權(quán)值域、左/右孩子域和雙親域，雙親域不但可用來存放雙親在向量中的下標(biāo)，而且可區(qū)分該結(jié)點(diǎn)是否為根結(jié)點(diǎn)。因?yàn)樵诋?dāng)前森林中合并兩棵二叉樹時(shí)，必須在森林的所有結(jié)點(diǎn)中先取兩個(gè)權(quán)值最小的根結(jié)點(diǎn)，所以有必要為每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)標(biāo)記以區(qū)分根和非根結(jié)點(diǎn)。2、解題步驟如下： 將哈天曼樹向量tree中的2n-l個(gè)結(jié)點(diǎn)初始化：即將各結(jié)點(diǎn)中的三個(gè)指針和權(quán)值均置 為0。 讀入n個(gè)權(quán)值放入向量tree的前

3、n個(gè)分量中，它們是初始森林中的n個(gè)孤立的根結(jié)點(diǎn)上的權(quán)值。 對(duì)森林中的樹進(jìn)行n I次合并，共產(chǎn)生 n I個(gè)新結(jié)點(diǎn)，依次放入向量tree的第t個(gè)分量中（n+l wtw m）（第t個(gè)分量的下標(biāo)值為t 一 I）。每次合并的方法如下：在當(dāng)前森林的所有結(jié)點(diǎn)treej(O j i 一 l, i=t-l)中，選取具有最小權(quán)值和次小權(quán)值的兩個(gè)根結(jié)點(diǎn)，分別用pl和p2記住這兩個(gè)根結(jié)點(diǎn)在向量tree中的下標(biāo)。將根為treepl和treep2的兩棵樹合并，使其成為新結(jié)點(diǎn)treei的左右孩子，得到一 棵以新結(jié)點(diǎn)treei為根的二叉樹。同時(shí)修改treepl和treep2的雙親域，使其指向新結(jié)點(diǎn)treei，這意味著它們?cè)诋?dāng)

4、前森林中已不再是根，將treepl和treep2的權(quán)值相加后，作為新結(jié)點(diǎn)treei的權(quán)值。05-2哈夭曼樹的三叉鏈表存儲(chǔ)形式示盍圖四、原程序清單c+程序#in clude#in clude#in cludeusing n amespace std;#defi ne MAXVAL 10000000 typedef int datatype;typedef structdouble weight;int num;datatype lchild,rchild,pare nt; htree;htree tree100;int n, m,flag=1;void create()int i,j,p1,p2

5、;double small1,small2,w;coutncinn;/定義一個(gè)足夠大的數(shù)，方便之后的操作定義哈夫曼樹結(jié)構(gòu)體類型結(jié)點(diǎn)的權(quán)值/結(jié)點(diǎn)的左、右孩子指針和父指針/定義全局變量，方便操作n表示預(yù)處理的結(jié)點(diǎn)數(shù)，m表示處理的結(jié)點(diǎn)總數(shù)/健立哈夫曼樹的函數(shù)/i,j用于循環(huán)語句，p1、p2用于記錄操作結(jié)果 /操作的中間變量請(qǐng)輸入預(yù)處理的結(jié)點(diǎn)數(shù)：;m=2* n-1; if(n=0) printf(n*n);printf(這是一棵空樹n);printf( *n); return;printf(n*n);printf(”請(qǐng)依次輸入個(gè)結(jié)點(diǎn)的權(quán)值(各權(quán)值以空格隔開)n);prin tf(*n)for(i=1;

6、i w; treei.weight=w; treei. num=i; treei.pare nt=O; treei.lchild=O; treei.rchild=O;for(i=n+1;i=m;i+)p仁0;p2=0;small1=MAXV AL;small2=MAXV AL;for(j=1;j=i-1;j+) if(treej.pare nt=0)if(treej.weightsmall1)small2=small1;small仁treej.weight; p2=p1;p1=j;else if(treej.weightsmall2) small2=treej.weight; p2=j;tre

7、ep1.pare nt=i;treep2.pare nt=i;treei. num=i;treei.pare nt=O;treei.lchild=p1;treei.rchild=p2;treei.weight=treep1.weight+treep2.weight; prin tf(n* n);printf（”哈弗曼樹初始化完畢n）;printf(* n);void prin t1(htree t)用于輸出哈夫曼樹的先序序列coutttt .num tt.weighte ndl; if(t.lchild!=O)prin t1(treet.lchild);if(t.rchild!=0)prin

8、t1(treet.rchild);void prin t2(htree t)用于輸出哈夫曼樹的中序序列if(t.lchild!=0)prin t2(treet.lchild);coutttt .num tt.weighte ndl; if(t.rchild!=0)prin t2(treet.rchild);void prin t3(htree t)用于輸出哈夫曼樹的中序序列if(t.lchild!=0)prin t3(treet.lchild);if(t.rchild!=0)prin t3(treet.rchild);coutttt .num tt.weightb)return a;retur

9、n b;int mai n()stri ng i,j; while(1) printf(n*printf(”歡迎使用菜單驅(qū)動(dòng)程序n);printf( * if(flag=1)printf(1初始化哈弗曼樹n);/第一級(jí)菜單prin tf(n請(qǐng)選擇您要的操作:);cin i;if(i=1)create。；flag=0;elseprintf(n*printf(”操作錯(cuò)誤n);printf(* n);con ti nue;printf(”1重新初始化哈弗曼樹n);/第二級(jí)菜單printf(”2輸出哈弗曼樹的高度n);printf(”3輸出哈弗曼樹的葉子結(jié)點(diǎn)的個(gè)數(shù)n);printf(”4輸出哈弗曼樹n

10、);printf(”5清屏 n);printf(”0結(jié)束操作n);prin tf(n請(qǐng)選擇您要的操作:;);cin i;if(i=1)create(); else if(i=2) if(n=0)prin tf(這是一棵空樹，高度為0n);printf(n*printf(*n); elseprintf(n*printf(”該樹的高度為 dn ,high(treem);printf( *else if(i=3)if(n=0)printf(n*printf(”這是棵空樹，葉子結(jié)點(diǎn)的個(gè)數(shù)為0n);printf( *elseprintf(n* printf(該樹的葉子結(jié)點(diǎn)的個(gè)數(shù)為%dn,n);print

11、f( *else if(i=4)if(n=0) printf(n* printf(這是一棵空樹n);printf( * con ti nue; while(1)printf(”歡迎使用菜單驅(qū)動(dòng)程序n);printf(n*prin tf(*n)printf(”1輸出哈弗曼樹的先序序列n); II第三級(jí)菜單printf(”2輸出哈弗曼樹的中序序列n ”)；printf(”3輸出哈弗曼樹的后序序列n ”)；printf(”4返回上層n);printf(”5清屏 n);printf(”0結(jié)束操作n);prin tf(n請(qǐng)輸入您要的操作：”)；fflush(stdi n); cinj; if(j=1)p

12、rintf(n*n)；printf(”哈弗曼樹的先序序列如下(左為結(jié)點(diǎn)序號(hào)，右為為結(jié)點(diǎn)權(quán)值prin tf(*n)；prin t1(treem);else if(j=2)printf(n*n)；prin tf(哈弗曼樹的中序序列如下(左為結(jié)點(diǎn)序號(hào)，右為為結(jié)點(diǎn)權(quán)值prin tf(*n)；prin t2(treem);else if(j=3)printf(n*n);printf(”哈弗曼樹的后序序列如下(左為結(jié)點(diǎn)序號(hào)，右為為結(jié)點(diǎn)權(quán)值)n);)n);)n);printf(“*n);prin t3(treem);else if(j=4)break;else if(j=5)system(cls); els

13、e if(j=0) prin tf(n*printf(”謝謝使用，再見n);printf(*n);return 1;elseprintf(n* printf(操作錯(cuò)誤 n);printf( * else if(i=5)system(cls);else if(i=O)prin tf(n* n);printf(”printf(謝謝使用，再見n);* n);return 1; elseprintf(n*printf(操作錯(cuò)誤n);printf( *運(yùn)行結(jié)果*歡迎使用菜單驅(qū)動(dòng)程序*1初始化哈夫曼樹請(qǐng)選擇您要的操作:op*操作錯(cuò)誤*歡迎使用菜單驅(qū)動(dòng)程序*1初始化哈夫曼樹請(qǐng)選擇您要的操作:1請(qǐng)輸入預(yù)處理的

14、結(jié)點(diǎn)數(shù)：0*這是一棵空樹*歡迎使用菜單驅(qū)動(dòng)程序1. 重新初始化哈夫曼樹2輸出哈夫曼樹的高度3. 輸出哈夫曼樹的葉子結(jié)點(diǎn)的個(gè)數(shù)4. 輸出哈夫曼樹5. 清屏0.結(jié)束操作請(qǐng)選擇您要的操作:2*這是一棵空樹，高度為 0*歡迎使用菜單驅(qū)動(dòng)程序*1. 重新初始化哈夫曼樹2. 輸出哈夫曼樹的高度3. 輸出哈夫曼樹的葉子結(jié)點(diǎn)的個(gè)數(shù)4. 輸出哈夫曼樹5. 清屏0.結(jié)束操作請(qǐng)選擇您要的操作:3*這是一棵空樹，葉子結(jié)點(diǎn)的個(gè)數(shù)為0*歡迎使用菜單驅(qū)動(dòng)程序*1. 重新初始化哈夫曼樹2. 輸出哈夫曼樹的高度3. 輸出哈夫曼樹的葉子結(jié)點(diǎn)的個(gè)數(shù)4. 輸出哈夫曼樹5. 清屏0.結(jié)束操作請(qǐng)選擇您要的操作:4*這是一棵空樹*歡迎使用

15、菜單驅(qū)動(dòng)程序*1. 重新初始化哈夫曼樹2輸出哈夫曼樹的高度3. 輸出哈夫曼樹的葉子結(jié)點(diǎn)的個(gè)數(shù)4. 輸出哈夫曼樹5. 清屏0.結(jié)束操作請(qǐng)選擇您要的操作:6*操作錯(cuò)誤*歡迎使用菜單驅(qū)動(dòng)程序*1. 重新初始化哈夫曼樹2. 輸出哈夫曼樹的高度3. 輸出哈夫曼樹的葉子結(jié)點(diǎn)的個(gè)數(shù)4. 輸出哈夫曼樹5. 清屏0.結(jié)束操作請(qǐng)選擇您要的操作:1請(qǐng)輸入預(yù)處理的結(jié)點(diǎn)數(shù)：5*請(qǐng)依次輸入個(gè)結(jié)點(diǎn)的權(quán)值（各權(quán)值以空格隔開）*1 2 3 4 5*哈夫曼樹初始化完畢*歡迎使用菜單驅(qū)動(dòng)程序*1. 重新初始化哈夫曼樹2輸出哈夫曼樹的高度3輸出哈夫曼樹的葉子結(jié)點(diǎn)的個(gè)數(shù)4. 輸出哈夫曼樹5清屏0.結(jié)束操作請(qǐng)選擇您要的操作:2*該樹的高

16、度為 4*歡迎使用菜單驅(qū)動(dòng)程序*1. 重新初始化哈夫曼樹2. 輸出哈夫曼樹的高度3. 輸出哈夫曼樹的葉子結(jié)點(diǎn)的個(gè)數(shù)4. 輸出哈夫曼樹5. 清屏0.結(jié)束操作請(qǐng)選擇您要的操作:3*該樹的葉子結(jié)點(diǎn)的個(gè)數(shù)為5*歡迎使用菜單驅(qū)動(dòng)程序*1. 重新初始化哈夫曼樹2. 輸出哈夫曼樹的高度3. 輸出哈夫曼樹的葉子結(jié)點(diǎn)的個(gè)數(shù)4. 輸出哈夫曼樹5. 清屏0.結(jié)束操作請(qǐng)選擇您要的操作:4*歡迎使用菜單驅(qū)動(dòng)程序*1.輸出哈夫曼樹的先序序列2輸出哈夫曼樹的中序序列3輸出哈夫曼樹的后序序列4返回上層5清屏0結(jié)束操作請(qǐng)輸入您要的操作：1*哈夫曼樹的先序序列如下（左為結(jié)點(diǎn)序號(hào)，右為為結(jié)點(diǎn)權(quán)值）*9157 63 36 31 12

17、 28 94 45 5*歡迎使用菜單驅(qū)動(dòng)程序*1輸出哈夫曼樹的先序序列2輸出哈夫曼樹的中序序列3輸出哈夫曼樹的后序序列4返回上層5清屏0結(jié)束操作請(qǐng)輸入您要的操作：2*哈夫曼樹的中序序列如下（左為結(jié)點(diǎn)序號(hào)，右為為結(jié)點(diǎn)權(quán)值）*3 37 6116 32 29 154 48 9*歡迎使用菜單驅(qū)動(dòng)程序*1輸出哈夫曼樹的先序序列2輸出哈夫曼樹的中序序列3輸出哈夫曼樹的后序序列4返回上層5清屏0結(jié)束操作請(qǐng)輸入您要的操作：3*哈夫曼樹的后序序列如下（左為結(jié)點(diǎn)序號(hào)，右為為結(jié)點(diǎn)權(quán)值）*3 311226 37 64 45 58 99 15*歡迎使用菜單驅(qū)動(dòng)程序*1輸出哈夫曼樹的先序序列2輸出哈夫曼樹的中序序列3輸出哈夫曼樹的后序序列4返回上層5清屏0結(jié)束操作請(qǐng)輸入您要的操作：6*操作錯(cuò)誤*歡迎使用菜單驅(qū)動(dòng)程序*1輸出哈夫曼樹的先序序列2輸出哈夫曼樹的中序序列3輸出哈夫曼樹的后序序列4返回上層5清屏0結(jié)束操作請(qǐng)輸入您要的操作：4*歡迎使用菜單驅(qū)動(dòng)程序*1.重新初始化哈夫曼樹2輸出哈夫曼樹的高度3. 輸出哈夫曼樹的葉子結(jié)點(diǎn)的個(gè)數(shù)4. 輸出哈夫