数据结构实验报告（二叉树和赫夫曼树）.docx

实验报告课程名称 数据结构 实验名称 二叉树和赫夫曼树 实验日期 班级 姓名 学号 实验报告要求 1.实验目的 2.实验要求 3.实验步骤 4.程序清单 5.运行情况 6.流程图 7.实验体会 实验目的：掌握建立哈夫曼树的操作。实验内容：1根据给定的前序序列和中序序列，后序序列和中序序列构造二叉树。2根据哈夫曼编码原理，编写一个在用户输入结点权值的基础上建立的哈夫曼编码的程序。程序设计思路构造一个哈夫曼树，由此得到的二进制前缀码便为哈夫曼编码。由于哈夫曼树没有度为1的结点，则一棵有n个叶子结点的哈夫曼树共有2n1个结点。设计一个结构数组，存储2n1个结点的值，包括权值、父结点、左结点和右结点等。程序清单：程序一（已知前序中序构造二叉树）：#include#include#include#include#define MAX_TREE_SIZE 100#define maxsize 1000#define N 50typedef char datatype;typedef struct node datatype data; struct node *lchild,*rchild;bitree;typedef struct bitree *stackmaxsize; int front,rear; sequeue;void SETNULL(sequeue *sq) (sq-front) = maxsize-1; (sq-rear) = maxsize-1;void ENQUEUE(sequeue *sq,bitree *T) if(sq-front=(sq-rear+1)%maxsize) /满队列 printf(full); else sq-rear=(sq-rear+1)%maxsize; sq-stacksq-rear=T; /入队bitree *DEQUEUE(sequeue *sq) if(sq-front=sq-rear) printf(empty); /空队列 else sq-front=(sq-front+1)% maxsize; return (sq-stacksq-front); /出队void f(bitree *T)sequeue L;SETNULL(&L);bitree *p;ENQUEUE(&L,T); /树根入队while(L.front!=L.rear) p=DEQUEUE(&L); /出队一个结点 printf(%c,p-data);if(p-lchild) /左孩子入队 ENQUEUE(&L,p-lchild);if(p-rchild) /右孩子入队 ENQUEUE(&L,p-rchild); /层次遍历void main() char ch,aN,bN;int dN;bitree *hN;int n,i,j,m,k=0; bitree *root,*t; printf(要输入的元素个数:); scanf(%d,&n); if(nN) printf(flown);system(pause);exit(0); /溢出的情况 if(n=0) printf(NULLn);system(pause);exit(0); /空树的情况 printf(前序:); ch=getchar(); for(i=0;in;i+) ch=getchar();ai=ch; printf(中序:); ch=getchar(); for(i=0;in;i+) ch=getchar();bi=ch; for(i=0;ilchild=NULL;root-rchild=NULL;root-data=a0;j=0;h0=root; if(n=1) f54(root);system(pause);exit(0); /树就一个结点的情况 for(i=1;ilchild=NULL;t-rchild=NULL;t-data=ai;hi=t;k=di-1-di; /比较前序中的前后项在中序里的前后关系 if(k0) for(j=0;j0 & (dj-di)lchild=hi; else for(j=0;ji;j+) if(dj-di)=k) k=dj-di;m=j; hm-rchild=hi; /向前逐一比较寻找同侧的dN差值最少的结点作为双亲 printf(层次遍历:n); /层次遍历 f(root);system(pause); 程序二（已知中序后序构造二叉树）#include#include#include#include#define MAX_TREE_SIZE 100#define maxsize 1000#define N 50typedef char datatype;typedef struct node datatype data; struct node *lchild,*rchild;bitree;typedef struct bitree *stackmaxsize; int front,rear; sequeue;void SETNULL(sequeue *sq) (sq-front) = maxsize-1; (sq-rear) = maxsize-1;void ENQUEUE(sequeue *sq,bitree *T) if(sq-front=(sq-rear+1)%maxsize) /满队列 printf(full); else sq-rear=(sq-rear+1)%maxsize; sq-stacksq-rear=T; /入队bitree *DEQUEUE(sequeue *sq) if(sq-front=sq-rear) printf(empty); /空队列 else sq-front=(sq-front+1)% maxsize; return (sq-stacksq-front); /出队void f(bitree *T)sequeue L;SETNULL(&L);bitree *p;ENQUEUE(&L,T); /树根入队while(L.front!=L.rear) p=DEQUEUE(&L); /出队一个结点 printf(%c,p-data);if(p-lchild) /左孩子入队 ENQUEUE(&L,p-lchild);if(p-rchild) /右孩子入队 ENQUEUE(&L,p-rchild); /层次遍历void main() char ch,aN,bN;int dN;bitree *hN;int n,i,j,m,k=0; bitree *root,*t; printf(要输入的元素个数:); scanf(%d,&n); if(nN) printf(flown);system(pause);exit(0); if(n=0) printf(NULLn);system(pause);exit(0); printf(中序:); ch=getchar(); for(i=0;in;i+) ch=getchar();ai=ch; printf(后序:); ch=getchar(); for(i=0;in;i+) ch=getchar();bi=ch; for(i=0;ilchild=NULL;root-rchild=NULL;root-data=bn-1;j=0;hn-1=root; if(n=1) f54(root);system(pause);exit(0); for(i=n-2;i=0;i-) t=(bitree *)malloc(sizeof(bitree); t-lchild=NULL;t-rchild=NULL;t-data=bi;hi=t;k=di-di+1; if(k0) for(j=i+1;j0 & (di-dj)rchild=hi; else for(j=i+1;jn;j+) if(di-dj)=k) k=di-dj;m=j; hm-lchild=hi; printf(层次遍历:n); f(root);system(pause); 程序三 (构造赫夫曼树)#include#include#include#include#define maxsize 1024#define N 50typedef int datatype;typedef struct int weight; int parent, child;Huffmantree; typedef struct datatype datamaxsize;/共享数组的大小 int top; /两个栈顶指针seqstack;int PUSH(seqstack *s,datatype x) if(s-top=maxsize-1) printf(栈满n);return -1; /*栈满的情况*/ else s-top+ ; s-datas-top=x ;return 1; /进栈int POP(seqstack *s) if(s-top=-1) printf(栈空n); /*下溢的情况*/ else s-top-;return s-datas-top+1; /出栈void main() Huffmantree hfmN;int wN;int n,m,i,j=0,k,p,q,t,sum=0;seqstack L; L.top=-1; printf(要输入的权重个数:); scanf(%d,&n); if(nN) printf(flown);system(pause);exit(0); /溢出的情况 if(n=0) printf(NULLn);system(pause);exit(0); /空树的情况 printf(依次输入权重:n); for(i=0;i2*n-1;i+) if(in) scanf(%d,&wi);hfmi.weight=wi;hfmi.child=-1;hfmi.parent=-1;sum=sum+wi; else hfmi.weight=0;hfmi.child=-1;hfmi.parent=-1;wi=sum+1; if(n=1) printf(error);system(pause);exit(0); /一个结点的情况 while(jn-1) p=sum+1;q=p; for(i=0;i2*n-1;i+) if(wip) p=wi;m=i; /找最小权重 wm=sum+1;hfmm.child=0;hfmm.parent=n+j; /把最小数用sum+1来覆盖 for(i=0;i2*n-1;i+) if(wiq) q=wi;k=i; wk=sum+1;hfmk.child=1;hfmk.parent=n+j; wn+j=p+q;j+; for(i=0;in;i+) j=