实验报告-二叉树

《实验报告-二叉树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、广东商学院GUANGDONGUNIVERSITYOFBUSINESSSTUDIES实验报告课程名称数据结构实验项目名称由遍历序列构造••叉树并实现中序线索化班级与班级代码软件工程二班112511042实验室名称（或课室）ssl-201软件工程任课教师杨创新学号：11251104230姓名：土丽乔实验日期：2012年11月29EI广东商学院教务处制姓名评语：实验报告成绩项目得分实验报告完整性实验报告格式实验过程实验结果正确性实验分析情况总分指导教师（签名）年月曰实验由遍历序列构造二叉树并实现中序线索化实验目的了解和熟悉构造和线索化二叉树的算法实验设备Win32平台的

2、电脑实验内容与算法分析#includc#include#defineMaxSize100#defineMaxWidth40typedefcharElemType;typedefstructnode/*数据元素*//*指向左孩子*//*指向右孩子*/{ElcmTypcdata;structnode*lchild;structnode*rchild;}BTNodc;BTNodc*CrcatcBTl(char*pre,char*in,intn){BTNode*s:char*p;intk;if(nV二0)returnNULL;s二(B

3、TNodc*)malloc(sizeof(BTNode));/*创建二叉树结点*$*/s->data=*prc;for(p=in;plchild=CreateBT1(prc+1,in,k);s->rchild=CreateBT1(pre+k+1,p+1^n-k-l);returns;}voidDispBTNode(BTNode*b){if(b!二NULL){printf(n%c",b->data);if(b->lchild!二NULL

4、

5、b>r

6、child!二NULL)/*递归处理左子树*/printffC);DispBTN()de(b->lchild);if(b->rchild!=NULL)printfC；');DispBTNode(b->rchiId);/*递归处理右子树*/printfm；}typedefstructtnode{ElcmTypcdata;intltag,rtag;/*增加的线索标记*/structtnode*lchild;structuiode*rchild;}TBTNode;voidCreateTBTNode(TBTNode*&b,char*str){TBTNodc*St[MaxS

7、izc],*p二NULL;inttop=-l,k,j=0;charch;b二NULL;/*建立的二叉树初始时为空=7ch=strQ];while(ch!=*)/*str未扫描完时循环*/{switch(ch){cascf:top++;St[top]二p;k二1;break;/*为左结点*/caseYrtop—;break;case*,'^=2;break;/*为右结点*/defaultp=(TBTNode*)malloc(sizeof(TBTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b二二NULL)/**p为二

8、叉树的根结点*/b=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){prin,b->data);if(b->lchild!=NULL

9、

10、b->rchild!=NULL)printffC)；DispTBTNodc(b->lchild);if(b->rchild!=NULL)printfC；*);DispTBTNode(l>>rchil

11、d);printfCT);}}/*全局变量*/}TBTNodc*prc;voidThread(TBTNode*&p)if(p!二NULL){Thread(p->Ichild);if(p->lchild==NULL){p->lchild=prc;p->ltag=l;/*左子树线索化*//*前驱线索*//*建立当前结点的前驱线索/*后继线索*//*建立前驱结点的后继线索*/elsep->ltag=0;if(pre->rchild==NULL){prc->rchild=p;prc->rtag=l;elsepre->rtag=0;pre二p;/*右子树线索化*//*中序线

12、索化二叉树