数据结构实验实现中序线索化二叉树构造哈夫曼树.doc

实验报告课程名称 数据结构 实验项目名称 实现中序线索化二叉树，构造哈夫曼树班级与班级代码 实验室名称（或课室） SS1-204 专 业 软件工程 任课教师 学 号： 姓 名： 实验日期： 2011年 11 月 18 日 广东商学院教务处制 姓名 实验报告成绩 评价：评 价 项 目优良一般差实验任务是否明确实验步骤是否清晰详尽实验任务是否完成实验结果是否正确程序设计是否规范标准版面整体效果是否美观 指导教师（签名） 2011 年 月 日说明：指导教师评分后，实验报告交院（系）办公室保存。实验题7.5实现中序线索化二叉树/*文件名:exp7-5.cpp*/#include #include #define MaxSize 100typedef char ElemType;typedef struct node ElemType data;int ltag,rtag; /*增加的线索标记*/struct node *lchild;struct node *rchild; TBTNode;void CreateTBTNode(TBTNode * &b,char *str)TBTNode *StMaxSize,*p=NULL;int top=-1,k,j=0; char ch;b=NULL;/*建立的二叉树初始时为空*/ch=strj;while (ch!=0)/*str未扫描完时循环*/ switch(ch) case (:top+;Sttop=p;k=1; break;/*为左结点*/case ):top-;break;case ,:k=2; break; /*为右结点*/default:p=(TBTNode *)malloc(sizeof(TBTNode);p-data=ch;p-lchild=p-rchild=NULL; if (b=NULL)/*p为二叉树的根结点*/b=p;else /*已建立二叉树根结点*/switch(k) case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;void DispTBTNode(TBTNode *b) if (b!=NULL)printf(%c,b-data);if (b-lchild!=NULL | b-rchild!=NULL)printf();DispTBTNode(b-lchild);if (b-rchild!=NULL) printf(,);DispTBTNode(b-rchild);printf();TBTNode *pre;/*全局变量*/void Thread(TBTNode *&p)if (p!=NULL)Thread(p-lchild); /*左子树线索化*/if (p-lchild=NULL)/*前驱线索*/p-lchild=pre; /*建立当前结点的前驱线索*/p-ltag=1;else p-ltag=0;if (pre-rchild=NULL)/*后继线索*/pre-rchild=p; /*建立前驱结点的后继线索*/ pre-rtag=1;else pre-rtag=0; pre=p; Thread(p-rchild); /*右子树线索化*/TBTNode *CreaThread(TBTNode *b) /*中序线索化二叉树*/TBTNode *root;root=(TBTNode *)malloc(sizeof(TBTNode); /*创建根结点*/root-ltag=0;root-rtag=1;root-rchild=b;if (b=NULL) /*空二叉树*/root-lchild=root;else root-lchild=b;pre=root; /*pre是*p的前驱结点,供加线索用*/Thread(b); /*中序遍历线索化二叉树*/pre-rchild=root; /*最后处理,加入指向根结点的线索*/pre-rtag=1;root-rchild=pre; /*根结点右线索化*/ return root;void ThInOrder(TBTNode *tb)TBTNode *p=tb-lchild;/*指向根结点*/while (p!=tb)while (p-ltag=0) p=p-lchild;printf(%c ,p-data);while (p-rtag=1 & p-rchild!=tb)p=p-rchild;printf(%c ,p-data);p=p-rchild;void main()TBTNode *b,*tb;CreateTBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I); printf( 二叉树:);DispTBTNode(b);printf(n);tb=CreaThread(b);printf( 线索中序序列:);ThInOrder(tb);printf(n);结果截图：7.6构造哈夫曼树/*文件名:exp7-6.cpp*/#include #include #define N 50/*叶子结点数*/#define M 2*N-1/*树中结点总数*/typedef structchar data5;/*结点值*/int weight;/*权重*/int parent;/*双亲结点*/int lchild;/*左孩子结点*/int rchild;/*右孩子结点*/ HTNode;typedef structchar cdN;/*存放哈夫曼码*/int start; HCode;void CreateHT(HTNode ht,int n)int i,k,lnode,rnode;int min1,min2;for (i=0;i2*n-1;i+)/*所有结点的相关域置初值-1*/hti.parent=hti.lchild=hti.rchild=-1;for (i=n;i2*n-1;i+)/*构造哈夫曼树*/min1=min2=32767;/*lnode和rnode为最小权重的两个结点位置*/lnode=rnode=-1;for (k=0;k=i-1;k+)if (htk.parent=-1)/*只在尚未构造二叉树的结点中查找*/if (htk.weightmin1)min2=min1;rnode=lnode;min1=htk.weight;lnode=k;else if (htk.weightmin2)min2=htk.weight;rnode=k;htlnode.parent=i;htrnode.parent=i;hti.weight=htlnode.weight+htrnode.weight;hti.lchild=lnode;hti.rchild=rnode;void CreateHCode(HTNode ht,HCode hcd,int n)int i,f,c;HCode hc;for (i=0;in;i+)/*根据哈夫曼树求哈夫曼编码*/hc.start=n;c=i;f=hti.parent;while (f!=-1)/*循序直到树根结点*/if (htf.lchild=c)/*处理左孩子结点*/hc.cdhc.start-=0;else/*处理右孩子结点*/hc.cdhc.start-=1;c=f;f=htf.parent;hc.start+;/*start指向哈夫曼编码最开始字符*/hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n)int i,k;int sum=0,m=0,j;printf( 输出哈夫曼编码:n); /*输出哈夫曼编码*/for (i=0;in;i+)j=0;printf( %s:t,hti.data);for (k=hcdi.start;k=n;k+)printf(%c,hcdi.cdk);j+;m+=hti.weight;sum+=hti.weight*j;printf(n);printf(n 平均长度=%gn,1.0*sum/m);void main()int n=15,i;char *str=The,of,a,to,and,in,that,he,is,at,on,for,His,are,be;int fnum=1192,677,541,518,462,450,242,195,190,