2023年实验报告二叉树

［广东商学院'GUANGDONGUNIVERSITYOFBUSINESSSTUDIES实验报告课程名称数据结构实验项目名称由遍历序列构造二叉树并实现中序线索化班级与班级代码软件工程二班实验室名称（或课室）ss1-201专业软件工程任课教师杨创新学号：姓名：王丽乔实验日期:20日年112291广东商学院教务处制姓名王丽乔实验报告成绩评语:项目得分实验报告完整性实验报告格式实验过程实验结果对的性实验分析情况总分指导教师（署名）实验由遍历序列构造二叉树并实现中序线索化实验目的了解和熟悉构造和线索化二叉树的算法实验设备Win32平台的电脑实验内容与算法分析#includc<stdio.h>include<ma11oc.h>defineMaxSize100defineMaxWidth40typedefCharElemType;typedefStructnode{0ElemTypedata;。。/*数据元素*/struCtnode*1child。/*指向左孩子*/structnode*rchild;e。/*指向右孩子*/}BTNode；BTNode*CreateBTl(char*pre,char*in,intn)(。BTNode*s;Char*p;intk;。if(n<=0)returnNULL;。s=(BTNode*)ma11oc(sizeoRBTNode));。/*创建二叉树结点*s*/。s->data=*pre;for(p=in;p<in+n;p++)»，/*在中序序列中找等于*ppos的位置k*/°if(*p二=*pre)°break;。k=p-in;s->lchild=CreateBT1(pre+1,in,k);s->rchild二CreateBT1(pre+k+1,p+l,n-k-1);returns;voidDispBTNode(BTNode*b){if(b!=NULL){aprintf("%cH,b—>data);。if(b->lchild!=NULL||b->rchi1d!=NULL)0{®®printff,C*);«>DispBTNodc(b->lchild);06。/*递归解决左子树*/if(b->rchi1d!=NULL)printf(",");o。DispBTNode(b->rchild);-。。/*递归解决右子树*/。。prin;typcdcfstructmodesE1cmTypedata;

33int1tag,rtag;3int1tag,rtag;/*增长的线索标记*/。3int1tag,rtag;/*增长的线索标记*/3struc11node*rchild;}TBTNode;voidCreateTBTNode(TBTNode*&b,char*str)(0TBTNode*St[MaxSize],*p=NULL;°inttop="l,k,j=0;charch;sb=NULL;。。/*建立的二叉树初始时为空*/ch=str[j];while(ch!='\0,)/*str未扫描完时循环*/{。3switch(ch)3O{case1(r:top++;St[top]=p;k=1;break;。。/*为左结点*/0°casc')'：top--;brcak;scase\':k=2;break;。/*为右结点*/°。defau1t：p=(TBTNode*)malloc(sizeof(TBTNode));»。p—>data=ch;p->lchild=p—>rchi1d=NULL;…if(b==NULL)。/**p为二叉树的根结点*/aao6b二p；。。else。。。。/*已建立二叉树根结点*/switch(k)casel：St[top]->lchild=p;break;case2:StLtop]->rchild=p;break;casej++；。ch=str[j];})voidDispTBTNode(TBTNode*b)(if(b!=NULL)a{«®printf(n%c'\b->data);if(b->lchikl!=NULL||b->rchi1cl!=NULL)°{…printf("C);DispTBTNode(b->lchi1d);。if(b->rchild!=NULL)printf(V)；°°DispTBTNode(b->rchild);…printfC'D；a}}}TBTNode*pre；®®。。/*全局变量*/voidhrcad(TBTNode*&p)if(p!=NULL)。Thread(p->1child);/*左子树线索化*/。if(p->】chi1d二二NULL)。/*前驱线索*/ao>°。p—>lchild=pre；/*建立当前结点的前驱线索*/0°p->1tag=l;00133eIsep->ltag=O;。oif(pre—>rchild==NULL)»/*后继线索*/pre->rchi1d=p；。/*建立前驱结点的后继线索*/«*pre->rtag=1;。}。elsepre->rtag=O;prc=p;sThread(p->rchi1d);。/*右子树线索化*/0)}TBTNode*CreaThreadfTBTNode*b)/*中序线索化二叉树*/(TBTNode*root；。root=(TBTNode*)ma11oc(sizeoffTBTNode));/*创建根结点*/。root->ltag=0;root->rtag=l；root—>rchi1d=b;/*/*空二叉树*//*空二叉树*/。if(b==NULL)3oroot->lchild=root;0/*空二叉树*/0{0。root—>1child=b；°pre=root;。/*pre是*p的前驱结点，供加线索用*/…Thread。));。/*中序遍历线索化二叉树*/。prc->rchi1d=root;。/*最后解决，加入指向根结点的线索*/°°pre->rtag=1；8°root->rchild=pre;/*根结点右线索化*/0}returnr0ot；)voidThInOrder(TBTNode*tb)(，TBTNode*p=tb->lchiId;/*指向根结点*/°whi1c(p!=tb)«°{while(p->ltag==0)p=p->lchild;。aprintf("%c",p->data);»while(p->rtag==1&&p->rchild!=tb)(»p=p->rchild;°printf("%cH,p—>data)；p=p—>rchild;voidmain。{BTNode*b;oE1emTypepre口:"ABDEHJKLMNCFGI”；3ElcmTypein|J="DBJHLI<MNEAFCGr'；oElemTypepost[]="DJLNMKHEBFIGCAH;b=CrcatcBT1(pre,in,l4);。printf("先序序列：%s\n",pre);printf("中序序列:％s\n”,in);printf("构造一棵二叉树b:\n");，printf(11括号表达法：")；DispBTNode(b)；printf(M\nM);°TBTNode*C,