1、課程設計報告2013 /2014學年 第 2 學期）二叉樹基本操作與哈夫曼編碼譯碼系統的設計專業： 學生姓名： 班級學號： 指導教師 指導單位 日期評分項成績遵守機房規章制度（5分）上機時的表現（5分）學習態度（5分）程序準備情況（5分）程序設計能力（10分）團隊合作精神（5分）課題功能實現情況（10分）算法設計合理性（10分）用戶界面設計（10分）報告書寫認真程度（5分）內容詳實程度（10分）文字表達熟練程度（10分）回答問題準確度（10分）評 分 細 則教師簽名:年月日評分等級有五種：優秀、良好、中等、及格、不及格課題題目叉樹基本操作與哈夫曼編碼譯碼系統的設計課題內容和要求創建一棵二叉樹，

2、分別實現先序、中序和后序遍歷一棵二叉樹，計 算二叉樹結點個數等操作。設計哈夫曼編碼/譯碼系統。能成功演示 二叉樹的有關運算，運算完畢后能成功釋放二叉樹所有結點占用的 系統內存。二、需求分析建立二叉搜索樹2 建立二叉樹方式二先序遞歸遍歷二叉樹4中序遞歸遍歷二叉捌后序遞歸遍歷二叉樹石計算二叉樹的高度人刪除某個二叉樹節點8 -從文件讀取文本得到權值生成哈夫晨樹乩結束程序運行我們根據需求得到以上的菜單，以鏈表方式存儲二叉樹，以插入二 叉搜索樹的方式，將數據一個一個地插入二叉樹， 以遞歸的方式分別實 現先、中、后三種方式的遍歷和計算二叉樹的高度，刪除二叉樹時，先 搜索找到那個節點，若有兩個子節點，查找中

3、序遍歷直接后繼節點，之 后常規的替代刪除操作，最后是哈夫曼樹的實現，從文件讀取字符串的時候，用 while 循環來得到每個字母的出現次數，得到權值，之后實現哈夫曼樹，通過譯碼函數輸出譯碼序列。三、概要設計typedef char Etype; typedef struct btnode Etype data;struct btnode * lch,* rch;int weight;btnode;typedef struct btreestruct btnode * root;btree;typedef struct int weight;int parent,lchild,rchild;HTN

4、ode,*HuffmanTree;typedef char * HuffmanCode; 其他的就是各類函數，見下文。四、詳細設計#include<stdio.h>#include<stdlib.h>#include<string.h>#include<iostream.h>#include<conio.h>#include<fstream.h>typedef char Etype; typedef struct btnodeEtype data;struct btnode * lch,* rch;int weight;b

5、tnode;typedef struct btreestruct btnode * root;btree;btnode * newnode() btnode * p=(btnode*)malloc(sizeof(btnode);return p;btnode * newnode(Etype e)btnode * p=(btnode*)malloc(sizeof(btnode); p->data=e;p->lch=NULL;p->rch=NULL;return p;void MAKEBTREE(btree * bt,int x,btree *lt,btree * rt) btn

6、ode * p=newnode(); p->weight=x;p->lch=lt->root; p->rch=rt->root; lt->root=NULL;rt->root=NULL;bt->root=p;*/void CREATEBTREE(btree * bt) /* 構造一顆空二叉數bt->root=NULL;/模仿先序遞歸遍歷方法，建立二叉樹btnode *creat_bt2()btnode *t;Etype e;scanf("%c",&e);if(e='#')t=NULL;/對于 &#

7、39;#'值，不分配新結點 elset=(btnode *)malloc(sizeof(btnode); t->data=e;t->lch=creat_bt2();/左孩子獲得新指針值t->rch=creat_bt2();/右孩子獲得新指針值return t; /creat_bt2void preorder(btnode *p)/前序遍歷if(p)printf("%3c",p->data);preorder(p->lch);preorder(p->rch); /preorder /中序遞歸遍歷二叉樹 void inorder(bt

8、node *p)if(p)inorder(p->lch);cout<<p->data<<endl;inorder(p->rch); /inorder /后序遞歸遍歷二叉樹 void postorder(btnode *p)if(p) postorder(p->lch);postorder(p->rch); cout<<p->data<<endl; /postorder int Depth(btnode * p)if(!p)return 0;elsereturn 1+(Depth(p->lch)>De

9、pth(p->rch)?Depth(p->lch):Depth(p->rch);/輸入 btree 的 rootint leafcount(btnode * bt)/計算葉結點數int count=0;if(bt!=NULL)leafcount(bt->lch); leafcount(bt->rch);if(bt->lch=NULL)&&(bt->rch=NULL)count+;return count;int remove(btree *bt)/輸入那個節點的值btnode *p=bt->root; btnode *c,*r,*

10、s,*q;Etype x,e;cout<<" 請輸入要刪除的節點的值 "<<endl;cin>>e;while(p&&p->data!=e)q=p;if(e<p->data)p=p->lch;else p=p->rch;if(!p)coutvv"不存在"<<e ndl;return 0;x=p->data; if(p->lch&&p->rch) s=p->rch;r=p; while(s->lch)r=s;s=s-&

11、gt;lch; p->data=s->data;p=s;q=r;if(p->lch)c=p->lch;else c=p->rch; if(p=bt->root)bt->root=c; else if(p=q->lch)q->lch=c;else q->rch=c;free(p);return 1;int insert(btree *btr,Etype et)/二叉搜索樹的插入函數btnode * r, *p=btr->root, *q;while(p)q=p;if(et<p->data)p=p->lch;els

12、e if(et>p->data)p=p->rch;elsecout<<"duplicate"<<endl;return 0;r=newnode(et);if(btr->root)if(et<q->data)q->lch=r; else q->rch=r;else btr->root=r;return 1;bt.root->data=btn.data;void mycreate (btree bt)/創建二叉搜索樹int x=1;Etype c;coutvv"第一個輸入的值為根的值，

13、請輸入根值"<<endl;cin>>c;btnode btn;btn.lch=NULL;btn.rch=NULL;btn.data=c;bt.root->lch=btn.lch;bt.root->rch=btn.rch;c=getchar();coutvv"其他節點的值"<<endl;while(c=getchar()!='n'&& x)x=insert(&bt,c);void Fmin(btree ht,int * k1,int * k2,int k) int a,b,c,d

14、;a=ht0.root->weight; b=ht0.root->weight; *k1=0;*k2=0;for(c=0;c<k;c+)if(a>=htc.root->weight)a=htc.root->weight;*k1=c; for(d=0;d<k;d+)if(d=*k1)continue;if(b>=htd.root->weight)b=htd.root->weight;*k2=d;MAKEBTREE(&htk1,htk1.root->weight+htk2.root->weight,&htk1,

15、&htk2);btree createhfmtree()/生成哈弗曼樹btree zero,ht26;int i,k,k1,k2;int w26;for(i=0;i<26;i+)wi=0; CREATEBTREE(&zero); FILE* fp; fp=fopen("c:test.txt","r+");while(!feof(fp)wfgetc(fp)-97+;for(i=0;i<26;i+)MAKEBTREE(&hti,wi,&zero,&zero);hti.root->data=97+i;p

16、rintf("%3d ",hti.root->data);for(k=25;k>0;k-)Fmin(ht,&k1,&k2,k);htk1.root->data='!'printf("%3d ",htk1.root->data);htk2=htk; return ht0;int m,s1,s2;typedef struct int weight;int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char * HuffmanCode;void Se

17、lect(HuffmanTree HT,int n) int i,j;for(i=1;i<=n;i+) if(HTi.parent=0)s1=i;break;for(j=i+1;j<=n;j+)if(HTj.parent=0) s2=j;break;for(i=1;i<=n;i+)if(HTi.parent=0)if(HTs1.weight>HTi.weight)if(s2!=i)s1=i;for(j=1;j<=n;j+)if(HTj.parent=0)if(HTs2.weight>HTj.weight) if(s1!=j)s2=j;if(s1>s2)

18、int temp=s1;s1=s2;s2=temp;void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n) int i;char *cd;int p;int cdlen;if (n<=1) return;m = 2 * n - 1;HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); for (i=1; i<=n; i+)HTi.weight=wi-1;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for (i=n

19、+1; i<=m; i+) HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;/添加查看，便于調試 /*printf（" 構造過程顯示： n"）;for(i=1;i<=m;i+)printf("%4d%4d%4d%4d%4dn",i,HTi.weight, HTi.parent,HTi.lchild,HTi.rchild);system("pause");*/ for(i=n+1;i<=m;i+)Select(HT,i-1);HTs1.parent = i; HT

20、s2.parent = i;HTi.lchild = s1; HTi.rchild = s2;HTi.weight = HTs1.weight + HTs2.weight;/添加查看，便于調試/*printf("s1=%d,s2=%dn",s1,s2); for(j=1;j<=i;j+)printf("%d%4d%4d%4d",j,HTj.weight,HTj.parent,HTj.lchild,HTj.rchild);system("pause");*/cd = (char *)malloc(n*sizeof(char);p=

21、m;cdlen=0;for(i=1;i<=m;i+)HTi.weight=0;while(p) if(HTp.weight=0)HTp.weight=1;if(HTp.lchild!=0)p=HTp.lchild;cdcdlen+='0'else if(HTp.rchild=0)HCp=(char *)malloc(cdlen+1)*sizeof(char);cdcdlen='0'strcpy(HCp,cd);else if(HTp.weight=1)HTp.weight=2;if(HTp.rchild!=0) p=HTp.rchild; cdcdlen+

22、='1' elseHTp.weight=0; p=HTp.parent; -cdlen; inthfm()HuffmanTree HT;HuffmanCode HC;int *w,i;int n=0;int x,y,z=0;FILE *fp;fp=fopen("c:test.txt","r+");FILE * fp2=fopen("c:test.txt","r+"); int zimu26=0; repeat:while(!feof(fp)y=fgetc(fp);for(x=97;x<123;

23、x+)for(i=0;i<z;i+) if(y=zimui) goto repeat; if(x=y)n+;zimuz=y;z+;HC = (HuffmanCode)malloc(n*sizeof(HuffmanCode);w=(int *)malloc(n*sizeof(int);for(i=0;i<n;i+)wi=0;while(!feof(fp2)wfgetc(fp2)-97+;HuffmanCoding(HT,HC,w,n);printf(" 輸出編碼： n");for(i=1;i<=n;i+)printf("%2d(%4d):%sn&q

24、uot;,i,wi-1,HCi);return 0;void main()char ch;int k;btree * t;btree bt,hfmbt;bt.root=(btnode *)malloc(sizeof(btnode);doprintf("n");printf("nnn");printf("nn2.建立二叉樹方式二 ");printf("nn3.先序遞歸遍歷二叉樹 ");printf("nn4.中序遞歸遍歷二叉樹 ");printf("nn5.后序遞歸遍歷二叉樹 "

25、;);printf("nn6.計算二叉樹的高度 ");printf("nn7.刪除某個二叉樹節點 ");printf("nn8.從文件讀取文本得到權值生成哈夫曼樹 ");printf("nnxr/iii.0.結束程序運行 ");printf("n=printf("n請輸入您的選擇 (0,1,2,3,4,5,6,7,8)");主菜單1.建立二叉搜索樹 ");printf("nnscanf("%d",&k);switch(k)case 1:m

26、ycreate(bt);t=&bt;break;case 2:printf（"n請輸入二叉樹各結點值："）;/調fflush(stdin);t->root=creat_bt2();break;用遞歸建立二叉樹算法case 3:if(t)printf(" 先序遍歷二叉樹 :");preorder(t->root); printf("n");else printf("二叉樹為空！n");break;case 4:if(t)printf（" 中序遍歷二叉樹 :"）;inorder(

27、t->root); printf("n");else printf("二叉樹為空!n");break;case 5:if(t)printf(" 后序遍歷二叉樹 :");postorder(t->root); printf("n");else printf("二叉樹為空!n");break;case 6:if(t)printf("二叉樹的高度為：d",Depth(t->root);prin tf("n");else printf("二叉樹為空！ n");break;case 7:remove(t);break;case 8:hfm();break;case 0:exit(0); /switchwhile(k>=1 &&k<=10);printf(