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

1、广东商学院GUAHGDONG UNIVERSITY OF BUSINESS STUDIES实验报告课程名称实验项目名称 实现中序线索化二叉树，构造哈夫曼树班级与班级代码实验室名称（或课室）SS1-204专 业任课教师学 号：姓 名：实验日期：2011年11月18日商学院教务处制实验报告成绩评价:评价项目优良般差实验任务是否明确实验步骤是否清晰详尽实验任务是否完成实验结果是否正确程序设计是否规标准版面整体效果是否美观指导教师（签名）2011年 月 日说明：指导教师评分后，实验报告交院（系）办公室保存。实验题7.5实现中序线索化二叉树/* 文件名：exp7-5.cpp*/#in elude <

2、;stdio.h>#i nclude <malloc.h>#defi ne MaxSize 100typedef char ElemType;typedef struct nodeElemType 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;/*建立的二叉

3、树初始时为空 */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=

4、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)prin tf("%c",b->data);if (b->lchild!=NULL | b->rchild!=NULL) prin tf("(");DispTBTNode(b->lchild);if (b->rchild!=NULL) pri

5、 ntf(",");DispTBTNode(b->rchild);prin tf(")");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-

6、>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; elseroot->lchild

7、=b; pre=root;Thread(b); pre->rchild=root;pre->rtag=1; root->rchild=pre;return root;void ThI nO rder(TBTNode *tb)/*空二叉树*/*pre是*p的前驱结点，供加线索用*/*中序遍历线索化二叉树*/*最后处理，加入指向根结点的线索*/*根结点右线索化*/TBTNode 故件宝按包丫匚&划艸呵电ct小“0？_52出口0护可了_5, eKe"线索中序钢壯D BJHLKHNIAFCGI i*ess any key to continue-p=tb->l

8、child;/*指向根结点 */while (p!=tb)while (p->ltag=O) p=p->lchild;prin tf("%c ",p->data);while (p->rtag=1 && p->rchild!=tb)p=p->rchild;prin tf("%c ",p->data);p=p->rchild;void mai n()TBTNode *b,*tb;CreateTBTNode(b,"A(B(D,E(H(J,K(L,M(,N),C(F,G(,l)"

9、;); printf("二叉树:");DispTBTNode(b);printf("n"); tb=CreaThread(b);printf("线索中序序列:");ThInOrder(tb);printf("n”);结果截图：7.6构造哈夫曼树/* 文件名:exp7-6.cpp*/#in elude <stdio.h>#in elude <stri ng.h>#defi ne N 50#defi ne M 2*N-1 typedef structchar data5;int weight;int pa

10、re nt;/*叶子结点数*/*树中结点总数*/*结点值*/*权重*/*双亲结点*/*左孩子结点*/*右孩子结点*/int lchild;int rchild; HTNode;typedef structchar cdN;int start; HCode;void CreateHT(HTNode ht,i nt n)/*存放哈夫曼码*/int i,k,l no de,r node;int min 1,mi n2;for (i=0;i<2* n-1;i+)/*所有结点的相关域置初值-1*/hti.pare nt=hti.lchild=h ti.rchild=-1;for (i=n; i&l

11、t;2* n-1;i+)min 1=mi n2=32767;Ino de=r no de=-1;for (k=0;k<=i-1;k+)if (htk.pare nt=-1)/*构造哈夫曼树*/*lnode和rnode为最小权重的两个结点位置*/*只在尚未构造二叉树的结点中查找*/if (htk.weight<mi n1)mi n2=mi n1;rnode=l no de;min 仁htk.weight; Ino de=k;else if (htk.weight<mi n2)min 2=htk.weight;r no de=k;ht Ino de.pare nt=i;htr n

12、o de.pare nt=i;hti.weight=ht Ino de.weight+htr no de.weight;hti .l child=Ino de;hti.rchild=r no de;void CreateHCode(HTNode ht,HCode hcd,i nt n)int i,f,c;HCode hc;for (i=0;i< n; i+)/*根据哈夫曼树求哈夫曼编码*/hc.start=n; c=i;f=hti.pare nt;while (f!=-1)/*循序直到树根结点*/if (htf.lchild=c)/* 处理左孩子结点 */hc.cdhc.start-=&

13、#39;0'else/*处理右孩子结点*/hc.cdhc.start-='1'c=f;f=htf.pare nt;hc.start+;/*start指向哈夫曼编码最开始字符*/hcdi=hc;void DispHCode(HTNode ht,HCode hcd,int n)int i,k;int sum=O,m=O,j;printf(”输出哈夫曼编码：n"); /*输出哈夫曼编码*/for (i=0;i< n;i+)j=0;printf(" %s:t",hti.data);for (k=hcdi.start;k<=n ;k+)p

14、rin tf("%c",hcdi.cdk);j+;m+=hti.weight;sum+=hti.weight*j;prin tf("n");prin tf("n平均长度=%gin",1.0*sum/m); void mai n()int n=15,i;char *str="The","of","a","to","a nd","i n","that","he","is&

15、quot;,"at","o n","for","His","are","be"int fnum=1192,677,541,518,462,450,242,190,181,174,157,124,123;HTNode htM;HCode hcdN;for (i=0;i< n;i+)strcpy(hti.data,stri); hti.weight=fnumi;prin tf("n ”);CreateHT(ht, n);CreateHCode(ht,hcd, n);DispHCode(ht,hcd, n); prin tf("n ”);结果截图："飪镇住安装包