實驗五_二叉樹與最優(yōu)二叉樹_09082229劉增鵬

1、實驗5二叉樹與最優(yōu)二叉樹一、實驗要求1、了解樹和二叉樹的特性，以及它們在實際問題中的應用。2、掌握樹和二叉樹的實現方法以及它們的基本操作，學會運用樹和二叉樹 來解決問題。二、實驗題目1、用菜單驅動的手法，編寫一個完整的程序，生成一棵二叉樹，求二叉樹 的高度，求二叉樹的葉子結點數，輸出二叉樹的所有結點。2、編寫一個完整的程序實現，利用哈夫曼算法建立哈夫曼樹，并輸出這棵 樹中所有結點數據。三、算法描述二叉樹：一般常用的是動態(tài)鏈式存儲，這時一般不用擔心空間溢出問題， 也不必關心存儲管理的細節(jié)（由系統(tǒng)完成），這使我們能用更多的精力去考慮其 他問題。在此用動態(tài)鏈表存儲二叉樹。二叉鏈表是二叉樹最常用的存儲

2、結構，其中每個結點除了存儲結點本身的 數據外，還設置兩個指針域Ichild和rchild，分別指向該結點的左孩子和右孩 子。這是二叉樹鏈式存儲的二指針形式。就像單鏈表由頭指針惟一確定一樣， 一個二義鏈表也由指向根結點的根指針惟一確定。為了某些運算的方便，也可 給二義鏈表增加頭結點（但一般并沒有這樣做）。二叉樹的生成是指如何在內存中建立二叉樹的存儲結構。建立順序存儲結 構的問題較簡單，這里僅討論如何建立二叉鏈表。要建立二叉鏈表，就需要按 照某種方式輸人二叉樹的結點及其邏輯信息。注意到對二叉樹遍歷時，不僅得 到了結點信息，而且由序列中結點的先后關系還可獲得一定的邏輯信息，如果 這些信息足夠，就可根

3、據遍歷序列生成相應的二叉樹二叉樹的生成方法就是基于遍歷序列的，相當于遍歷問題的逆問題，即由 遍歷序列反求二叉樹，這需要分析和利用二叉樹遍歷序列的特點。哈夫曼算法（最優(yōu)二叉樹）：在許多應用中，常常將樹中結點賦予一個有某種 意義的實數，稱為該結點的權。結點到樹根之間的路徑長度與該結點權的乘積 稱為該結點的帶權路徑長度。樹的（外部）帶權路徑長度（Weighted Path Length），定義為樹中所有葉于結點的帶權路徑長度之和，通常記為：WPL=芝 wli=1其中，n表示子結點的數目，w和分別表示葉結點i的權值和它到根之間的路徑長度。在權為w1，w2,，wn的n個葉結點的所有二叉樹中，帶權路徑 長

4、度WPL最小的二叉樹.n（1）首先，根據給定的n個權值w1，w2，wn構造含有n棵二叉樹的森林F=T；，T2，T ，其中每棵二叉樹T.中只有一個權值為W.的 根結點，沒有左右子樹。 11（2）在森林F中選出兩棵根結點權值最小的樹（當這樣的樹不止兩棵樹 時，可從中任選兩棵），將這兩棵樹合并成一棵新的二叉樹。這時會增加一個新的根結點， 它的權取為原來兩棵樹的根的權值之和，而原來的兩棵樹就作為它的左右子樹 （誰左，誰右無關緊要）。（3）對新的森林F重復（2），直到森林F中只剩下一棵樹為止。這棵樹 便是哈大曼樹。由算法知，哈夫曼樹不一定惟一（但WPL是相同的，并且都為最?。?。原 因在于每次合并時，原兩

5、棵樹誰左誰右、以及候選的兩棵樹有多個時選哪兩個 等。在哈夫曼算法中，初始森林共有n棵二叉樹，每棵樹中僅有一個結點，它 們既是根，又是葉子。算法的第二步是將當前森林中的兩棵根結點權值最小的 二叉樹合并成一棵新二叉樹。每合并一次，森林中就減少一棵樹。顯然，要進 行nl次合并，才能使森林中二叉樹的數目由n棵減少到只剩一棵，即最終的 哈夫曼樹。另外，每合并一次都要產生一個新結點，合并n- l次共產生n- l個新結點。 由此可知，最終求得的哈大曼樹中共有n+（nl）=2n1個結點，其中的葉 結點就是初始森林中的n個孤立結點。在哈夫曼樹中，每個分支結點都是合并過程中產生的，它們的度為2,所 以樹中沒有度為

6、1的分支結點。四、程序清單#include#include#include#define M 200#define null 0#define n 8葉子結點數，假設為20#define m 15 結點總數#define max 1000typedef char Etype; /* 定義數據類型 */typedef struct BiTNode/* 定義結點類型 */ Etype data;struct BiTNode *lch,*rch;/*左 右子樹 */ BiTNode,*BiTree;BiTree queM;int front=0,rear=0;int count=0;BiTNode

7、*t,*p;typedef int datatype;typedef struct float weight;int parent,lchild,rchild;hftree; 結點類型hftree treem+1,tree2m+1;哈夫曼樹類型，數組從0號單元開始使用哈夫曼樹向量/*建立二叉樹(層次法)*/BiTNode *creat_bt1()(BiTNode *t,*p,*v20;int i,j; Etype e;printf(輸入二叉樹各結點的編號和對 應的值(用空格隔開)：，scanf(%d %c”,&i,&e);while(i!=-1)(p=(BiTNode*)malloc(size

8、of(BiTNode);p-data=e;p-lch=NULL;p-rch=NULL;vi=p;if(i=1)t=p;else( j=i/2;if(i%2=0)vj-lch=p;else vj-rch=p;printf(輸入二叉樹各結點的編號和對應的值(輸入i為-1時結束)：，scanf(%d %c”,&i,&e);return(t);/先根法建立二叉樹BiTNode *creat_bt2()(BiTNode *t;char ch;fflush(stdin);scanf(%c”,&ch);if(ch=)return null;else(t=(BiTNode*)malloc(sizeof(BiT

9、Node);t-data=ch;t-lch=creat_bt2();t-rch=creat_bt2();return t;void huffman(hftree tree)( int i,j,p1,p2,kz,ky,exchange; /p1,p2 十己當 前選的權值最小的兩棵樹根結點在向量T 中的下標float sm1,sm2;for(i=1;i=n;i+)(/初始化，根結點(葉子)的雙親和左、右孩子指針置為-1treei.parent=0;treei.lchild = treei.rchild=0;treei.weight=0.0;printf(Hello huffman!n);print

10、f(t請輸入d個葉子結點的權值： n,n);for(i=1;i=n;i+)輸入n個葉子的權值( scanf (%f”,&treei.weight); for(i=1;i=n;i+)printf(%2.2f ”,treei.weight);printf(nn);for(i=n+1;i=m;i+)/第 i 次合并，產生第i棵新樹(結點).共進行n-l次合并。(p1=p2=0;/此句可不要sm1=sm2=max;/max 為float型的最大值,它大于所有結點權值for (j=1;j=i-1;j+)從第0i-1棵樹中找兩個權值最小的根結點，/作為第i個生成的新樹( if (treej.parent

11、!= 0) continue;/ 不考慮已合并的點,雙親域不為-1時就不是 根if(treej.weightsm1)/修改最小權和次小權及位置( sm2=sm1;/sml中記當前找到的最小者權值,sm2記次小者 權值sm1= treej.weight;p2=p1; /pl 中記當 前找到的權值最小者結點的下標，/ p2記當前權值次小者結 點的下標p】=j；else if(treej.weight0;i-) printf(%4d”,i);printf(%10d: ,treei.parent);k=treei.parent;printf(%5.2f,treek.weight);printf(%10

12、d: ,treei.lchild);k=treei.lchild;printf(%5.2f,treek.weight);printf(%10d: ,treei.rchild);k=treei.rchild;printf(%5.2f,treek.weight);printf(%10.2fn,treei.weight);printf(Print end！ nn);void preorder(BiTNode *p )/* 先序遍歷二叉 樹*/ if(p) printf(%c ,p-data);preorder(p-lch);preorder(p-rch); void inorder(BiTNode

13、*p) /* 中序遍歷*/ if(p) inorder(p-lch);printf(%c ,p-data);inorder(p-rch); void postorder(BiTNode *p) /*后序遍歷 */ if(p) postorder(p-lch);postorder(p-rch);printf(%c ,p-data);void enqueue(BiTree T)( if(front!=(rear+1)%M)( rear=(rear+1)%M;querear=T;BiTree delqueue()( if(front=rear)return NULL;front=(front+1)%

14、M;return (quefront);void levorder(BiTree T)/*層次遍歷二叉樹 */( BiTree p;if(T)( enqueue(T);while(front!=rear)( p=delqueue();printf(%c ,p-data);if(p-lch!=NULL)enqueue(p-lch);if(p-rch!=NULL)enqueue(p-rch);int treedepth(BiTree bt)/*二 叉樹高度*/( int hl,hr,max1;if(bt!=NULL)( hl=treedepth(bt-lch);hr=treedepth(bt-rc

15、h);max1=(hlhr)? hl:hr;return(max1+1);else return(0);void prtbtree(BiTree bt,int level)/*打 印 */ int j;if(bt) prtbtree(bt-rch,level+1);printf(%dn,bt-data);prtbtree(bt-lch,level+1);void exchange(BiTree bt)/*交換二叉樹左右 子樹*/ BiTree p;if(bt) p=bt-lch;bt-lch=bt-rch;bt-rch=p;exchange(bt-lch);exchange(bt-rch);i

16、nt leafcount(BiTree bt) /* 葉子結點數*/ if(bt!=NULL) leafcount(bt-lch);leafcount(bt-rch);if(bt-lch=NULL)&(bt-rch=NUL L)count+;return(count);void paintleaf(BiTree bt)/* 葉子結點值 */ if(bt!=NULL)if(bt-lch=NULL&bt-rch=NULL)printf(%d ,bt-data);paintleaf(bt-lch);paintleaf(bt-rch);void print_menu()printf(主 菜單); pr

17、intf(n 1.建立二叉樹(層次發(fā))”)； printf(n 2.建立二叉樹(先根法); printf(n 3.先序遞歸遍歷二叉樹”)；printf（n 4.中序遞歸遍歷二叉樹”）；break;printf（n 5.后序遞歸遍歷二叉樹”）； printf（n 6.層次遍歷二叉樹”）； printf（n7.計算二叉樹的高度和葉子結點個數”）；printf（n8.建立哈夫曼樹”）；printf（n 9.打印哈夫曼樹”）；printf（n 0.打印二叉樹”）；printf（n E.結束程序運行”）；printf（n）；case 3:if(t) printf(先序遍歷二 叉樹:，preorder(t

18、);printf(n);else printf(該二叉樹 為空!n);break;printf(n 請選擇：n)；char chioce_menu()( char ch;for(；)( scanf(%c”,&ch);if(chE)printf(”輸入錯誤，重新選擇：n”); elsebreak;case 4:if(t) printf(中序遍歷 二叉樹:，inorder(t);printf(n);else printf(該二叉樹 為空!n);break;return ch；main()( char x;do( print_menu();switch(chioce_menu()(case 1:t=

19、creat_bt1();break;case 5:if(t) printf(后序遍歷 二叉樹:，postorder(t);printf(n);else printf(該二叉樹 為空!n);break;/*建立二叉樹算法*/case 2: printf（t先根遍歷 建立二叉樹：n）;printf（t 請輸入二 叉樹結點的值！ n）;printf（可以輸那 個值均為字母或（n100）字符間以回車 換行，想結束時輸多個：n）;case 6:if(t)printf(-層次遍歷二叉樹:，levorder(t);printf(n);else printf(該二叉樹 為空!n);break;t=creat_bt2();case 7:if(t)printf(二叉樹的高度為:dn”,treedepth(t);printf(二叉樹的葉 子結點數為:dn”,leafcount