1、二叉树的基本操作及哈夫曼编译译码 系统的实现实 验 报 告（2015/2016学年 第2学期）课程名称数据结构A实验名称二叉树的基本操作及哈夫曼编译译码 系统的实现实验时间2016年4月13日指导单位计算机科学与技术系指导教师骆健学生姓名班级学号学院(系) 管理学院专 业信息管理与信息系统实验一：二叉树基本操作一、 问题陈述在二叉链表上实现二叉树的建立、删除、求高度、求子叶节点数、左右交换、遍历等操作。二、 概要设计建立不同函数，分别实现二叉树的各项基本运算。三、 详细设计1.层次结构：文件一共需要5个函数。文件中包含各个函数函数的声明。分别是：status createbitree(bitr
2、ee *t);status preordertraverse(bitree t);int height(bitree t);void swap(bitree *t);void leafcounts(bitree t);2.核心算法：主函数四、 程序代码#include#include#define FALSE 0#define TRUE 1#define OK 1#define maxsize 100typedef int status;typedef int elemtype;typedef struct binode elemtype data; struct binode *lchild
3、,*rchild;binode,*bitree;status treecreated=FALSE;int leafcount=0;status createbitree(bitree *t);status preordertraverse(bitree t);int height(bitree t);void swap(bitree *t);void leafcounts(bitree t);void main() int choice=0; status leave=FALSE,flag; binode *bt; cout=二叉树演示程序=endl; do cout1：创建二叉树，按先序遍历
4、结果输入endl; cout2：先序遍历二叉树，递归方式遍历二叉树 endl; cout3：求叶子数endl; cout4：计算二叉树的高度endl; cout5: 树进行左右翻转endl; cout0：退出endl; cout-请输入:choice; switch(choice) case 1: if(treecreated) cout树还没有建立endl; break; ; cout请输入代表树的数字：endl; flag=createbitree(&bt); if(flag=OK) cout你已经建立了一棵树了！endl; treecreated=TRUE; break; case 2:
5、 if(!treecreated) coutsorry,you must create a tree for further steps!endl; break; cout先序遍历顺序:endl; preordertraverse(bt); coutendl; break; case 3: if(!treecreated) coutsorry,you must create a tree for further steps!endl; break; leafcounts(bt); cout树的叶子数:leafcountendl; coutendl; break; case 4: int h;
6、h=height(bt); cout树的高度:hendl; break; case 5: swap(&bt); cout树已经翻转！endl; break; case 0: leave=TRUE; break; while(!leave); cout 再见ch; if(ch=0) (*t)=NULL; else (*t)=(bitree)malloc(sizeof(binode); (*t)-data=ch; createbitree(&(*t)-lchild); createbitree(&(*t)-rchild); return OK;status preordertraverse(bit
7、ree t) if(t) coutdatalchild); preordertraverse(t-rchild); return OK; else return OK;int height(bitree t) int hl,hr; if(t=NULL) return 0; hl=height(t-lchild)+1; hr=height(t-rchild)+1; return (hlhr?hl:hr); void swap(bitree *t) bitree p; if(*t!=NULL) p=(*t)-lchild; (*t)-lchild=(*t)-rchild; (*t)-rchild=
8、p; swap(&(*t)-lchild); swap(&(*t)-rchild); void leafcounts(bitree t) if(t) if(t-lchild=NULL & t-rchild=NULL) leafcount+; leafcounts(t-lchild); leafcounts(t-rchild); 测试和调试建立如下树五、 实验小结（1） 加深了我对链表方面知识的理解与运用（2） 在进行输入时，一定要细心，少犯没有分号，括号数目不对等低级错误，这会大大增加调试的时间。（3） 采用模块化思想，主函数尽量只放函数调用实验二：哈夫曼编码和译码系统问题陈述实现哈夫曼编码译
9、码的功能一、 系统分析和概要分析基本操作：void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2) /选最小生成树void HuffmanCoding(HuffmanTree HT,Tdata *w,int n) /构建哈夫曼编码void HuffmanDecoding(HuffmanTree HT,Tdata) /译码详细设计建立哈夫曼数，得到生成的哈夫曼编码，用生成的哈夫曼编码进行译码。二、 核心算法和算法分析#include#include#include#define MAXSIZE 30#define MAX 100typede
10、f struct char data; int weight; int parent; int left; int right;HTNode,*HuffmanTree;typedef char * *HuffmanCode;typedef struct char data; int weight;Tdata;HuffmanTree HT; HuffmanCode HC; void SelectMinTree(HuffmanTree HT,int n,int *sl,int *s2);void HuffmanCoding(HuffmanTree HT,Tdata *w,int n);int ma
11、in() Tdata wMAXSIZE; int n,i; cout 请输入元素数n; for(i=1;i=n;i+) cout 输入第 i 点的数和权值:wi.datawi.weight; cout *结果*endl; HuffmanCoding(HT,w,n); for(i=1;i=n;i+) coutwi.dataHCia;HuffmanDecoding(a); return 0;void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2) int i,min1,min2; * s2=* s1 = 0; min1=min2=MAX; f
12、or(i=1;i=n;i+) if(HTi.parent=0) if(HTi.weightmin1) min2 = min1; min1 = HTi.weight; *s2 = *s1; *s1 = i; else if(HTi.weightmin2) min2 = HTi.weight; *s2 = i; void HuffmanCoding(HuffmanTree HT,Tdata *w,int n) int m,i,s1,s2,start,c,f; HTNode *p; char *cd; if(n = 1) return; m = 2*n -1; HT = (HuffmanTree)m
13、alloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;idata=wi.data; p-weight=wi.weight; p-left=0; p-right=0; p-parent=0; for(;iweight=0; p-left=0; p-right=0; p-parent=0; for(i=n+1;i=m;i+) SelectMinTree(HT,i-1,&s1,&s2); HTs1.parent = i; HTs2.parent = i; HTi.left = s1; HTi.right = s2; HTi.weight=HTs1.weight+HTs2
14、.weight; HC = (HuffmanCode) malloc(n+1)*sizeof(char *); cd = (char *)malloc(n*sizeof(char); cdn-1 = 0; for(i=1;i=n;i+) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.left = c) cd-start = 0; else cd-start = 1; HCi = (char *)malloc(n-start)*sizeof(char); strcpy(HCi,&cdstart); free(cd); 三、 测试用例四、 实验小结（1）在进行输入时，一定要细心，少犯没有分号，括号数目不对等低级错误，这会大大增加调试的时间。（2）程序必须有较强的健壮性。（3）用模式块的思想能增加程序的条理性。（4）程序出错时，可以先将一部分代码变成注释，一步步查错。
