资源描述：
《数据结构实验 实现中序线索化二叉树 构造哈夫曼树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、实验报告课程名称数据结构实验项目名称实现中序线索化二叉树，构造哈夫曼树班级与班级代码实验室名称（或课室）SS1-204专业软件工程任课教师学号：姓名：实验日期：2011年11月18日广东商学院教务处制9姓名实验报告成绩评价：评价项目优良一般差实验任务是否明确实验步骤是否清晰详尽实验任务是否完成实验结果是否正确程序设计是否规范标准版面整体效果是否美观指导教师（签名）2011年月日说明：指导教师评分后，实验报告交院（系）办公室保存。9实验题7.5实现中序线索化二叉树/*文件名:exp7-5.cpp*/#include#i
2、nclude#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;/*建立的二叉树初始时为空*/ch=st
3、r[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=p;else/*已建立二叉树根结点*/{switch(k)
4、9{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)printf(",");DispTBTNode(b->rchild);pri
7、ntf(")");}}}TBTNode*pre;/*全局变量*/voidThread(TBTNode*&p){if(p!=NULL){Thread(p->lchild);/*左子树线索化*/if(p->lchild==NULL)/*前驱线索*/{p->lchild=pre;/*建立当前结点的前驱线索*/9p->ltag=1;}elsep->ltag=0;if(pre->rchild==NULL)/*后继线索*/{pre->rchild=p;/*建立前驱结点的后继线索*/pre->rtag=1;}elsepre->rtag=0;pre=
8、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(
9、b);/*中序遍历线索化二叉树*/pre->rchild=root;/*最后处理,加入指向根结点的线索*/pre->rtag=1;root->rchild=pre;/*根结点右线索化*/}returnroot;}voidThInOrder(TBTNode*tb){9TBTNode*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
10、;printf("%c",p->data);}p=p->rchild;}}voidmain(){TBTNode*b,*tb;CreateTBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G
