数据结构二叉树

浙江万里学院实验报告

成绩： 课程名称： 数据结构 教师： 刘晓利 实验名称： 树与二叉树 专业班级： 计算机111 实验小组： 十 实验日期： 2012-11-9 成员姓名 李俊 成 绩 成员姓名 成 绩 （以下写实验内容、分析与程序清单、调试报告等） 一、 实验目的 1．熟练掌握二叉树的二叉链表存储结构。掌握二叉树的非线性和递归性特点。熟练掌握二叉树的递归遍历操作的实现方法，掌握二叉树的非递归遍历操作的实现。 2．掌握线索二叉树的定义和基本操作。 3．加深对二叉树结构和性质的理解，逐步培养解决实际问题的编程能力。 二、实验内容 1从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.； 2．利用已经建好的哈夫曼树htmTree，键盘输入的正文进行译码，输出字符正文再输出该文的二进制码。 3．利用书中的表格构建哈弗曼树。并实现以下报文的译码和输出： THIS PROGRAM IS MY FAVORITE 胡一凡 魏净达 程俊鹏

(1) 算法思想：构造哈夫曼树，对其遍历并将A~Z个字母编码，将哈弗曼编码存入hfmtree.txt中。对文件进行查找变可以对文字进行转码，再次对哈弗曼树遍历又可以译码。 (2) 源代码: #include #include #include #define N 1000 typedef struct { unsigned int weight; unsigned int parent,LChild,RChild; }HuffmanTree; HuffmanTree *ht,*p; typedef struct { char ch; char code[10]; }HuffmanCode; HuffmanCode *List; void select(HuffmanTree *ht,int n,int *s1,int *s2) //挑选了两个无父节点的节点 { int i; int min; for(i=1; i<=n; i++){ if(ht[i].parent == 0) { min = i;break; } } for(i=1; i<=n; i++){ if(ht[i].parent == 0){ if(ht[i].weight < ht[min].weight) min = i; } } *s1 = min; for(i=1; i<=n; i++){ if(ht[i].parent == 0 && i!=(*s1)){ min = i;break; } } for(i=1; i<=n; i++){ if(ht[i].parent == 0 && i!=(*s1)){ if(ht[i].weight < ht[min].weight) min = i; } } *s2 = min; }

HuffmanTree *CreatHuffmanTree(HuffmanTree *ht,int *w, int n) { int m=2*n-1; int i; int s1,s2; ht=(HuffmanTree*)malloc((m+1)*sizeof(HuffmanTree)); for(i=1;i<=m;i++){ if(i<=n) ht[i].weight=w[i-1]; else ht[i].weight=0; ht[i].parent=0;ht[i].LChild=0;ht[i].RChild=0;} for(i=n+1;i<=m;i++){ select(ht,i-1,&s1,&s2); ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s1].parent=i;ht[s2].parent=i; ht[i].LChild=s1;ht[i].RChild=s2;} return ht; } void CreatHuffmanCode(HuffmanTree *ht,int n,char *ch) //创建哈弗曼编码存入hfmtree中 { FILE *fp;char cd[N];int i,j,len;unsigned c,p,st; fp=fopen(\"d:\\\\hfmtree.txt\ for(i=1;i<=n;i++){ st=1; for(c=i,p=ht[i].parent; ;c=p,p=ht[p].parent){ if(p!=0){ if(ht[p].LChild==c) cd[st++]='0'; else cd[st++]='1';} else{ cd[st]='\\0'; break;} } len=strlen(cd); fprintf(fp,\"%c\\ for(j=len;j>0;j--) fprintf(fp,\"%c\ fprintf(fp,\"\\n\");} fclose(fp); }

void BeCode(int n) //调用hfmtree.txt进行编码 { FILE *fp;char str[N];int i,j,t; fflush(stdin); gets(str); fp=fopen(\"d:\\\\hfmtree.txt\ List=(HuffmanCode *)malloc(n*sizeof(HuffmanCode)); for(i=0;ivoid main() { int *w; //定义权值数组 char *ch; int i,m,n; printf(\"请输入字符集的大小:\"); scanf(\"%d\ //有多少种字符 w=(int*)malloc(n*sizeof(int)); ch=(char*)malloc(n*sizeof(char)); printf(\"请输入:(例如:A,32)\\n\"); for(i=0;id盘中出现了hfmtree其内容为 编码： 三、心得体会 哈夫曼树让我们更好得体会了树在编码时的实际应用，这个程序对于数据的处理，文件流的处理有很好得加深映像的作用。