正文描述:《大数据结构实验实现中序线索化二叉树构造哈夫曼树》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、实用实验报告课程名称数据结构实验项目名称实现中序线索化二叉树,构造哈夫曼树班级与班级代码实验室名称(或课室)SS1-204文档实用专业软件工程任课教师学号:姓名:实验日期:2011年11月18日广东商学院教务处制姓名实验报告成绩评价:评价项目优良一般差实验任务是否明确实验步骤是否清晰详尽实验任务是否完成实验结果是否正确程序设计是否规范标准版面整体效果是否美观文档实用指导教师(签名)2011年月日说明:指导教师评分后,实验报告交院(系)办公室保存。实验题7.5实现中序线索化二叉树/*文件名:exp7-5.cpp*/#incl
2、ude#include#defineMaxSize100typedefcharElemType;typedefstructnode{ElemTypedata;intltag,rtag;/*增加的线索标记*/structnode*lchild;structnode*rchild;}TBTNode;voidCreateTBTNode(TBTNode*&b,char*str){TBTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL;
3、/*建立的二叉树初始时为空*/文档实用ch=str[j];while(ch!='')/*str未扫描完时循环*/{switch(ch){case'(':top++;St[top]=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){case1:St[top]->lchild=p;break;case2:St[top]->rchild=p;break;}}}j++;ch=str[j];}}voidDispTBTNode(TBTNode*b){if(b!=NULL){printf("%c",b->data);if(b->lchild!=NULL
5、
6、b->rchild!=NULL){printf("(");DispTBTNode(b->lchild);文档实用if(b->rchild!=NULL
7、)printf(",");DispTBTNode(b->rchild);printf(")");}}}TBTNode*pre;/*全局变量*/voidThread(TBTNode*&p){if(p!=NULL){Thread(p->lchild);/*左子树线索化*/if(p->lchild==NULL)/*前驱线索*/{p->lchild=pre;/*建立当前结点的前驱线索*/p->ltag=1;}elsep->ltag=0;if(pre->rchild==NULL)/*后继线索*/{pre->rchild=p;/*建立
8、前驱结点的后继线索*/pre->rtag=1;}elsepre->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;els
9、e{root->lchild=b;pre=root;/*pre是*p的前驱结点,供加线索用*/Thread(b);/*中序遍历线索化二叉树*/pre->rchild=root;/*最后处理,加入指向根结点的线索*/pre->rtag=1;root->rchild=pre;/*根结点右线索化*/}returnroot;}voidThInOrder(TBTNode*tb){TBTNode*p=tb->lchild;/*指向根结点*/while(p!=tb){while(p->ltag==0)p=p->lchild;printf
10、("%c",p->data);while(p->rtag==1&&p->rchild!=tb){p=p->rchild;printf("%c",p->data);}p=p->rchild;}}voidmain(){TBTNode*b,*tb;CreateTBTNode(b,"A(B(D,E(H(J,K(
显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。