实验报告-二叉树.doc

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

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

2、oc.h>#defineMaxSize100#defineMaxWidth40typedefcharElemType;typedefstructnode{ElemTypedata;/*数据元素*/structnode*lchild;/*指向左孩子*/structnode*rchild;/*指向右孩子*/}BTNode;BTNode*CreateBT1(char*pre,char*in,intn){BTNode*s;char*p;intk;if(n<=0)returnNULL;s=(BTNode*)malloc(sizeof(BTN

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

4、

5、b->rchild!=

6、NULL){printf("(");DispBTNode(b->lchild);/*递归处理左子树*/if(b->rchild!=NULL)printf(",");DispBTNode(b->rchild);/*递归处理右子树*/printf(")");}}}typedefstructtnode{ElemTypedata;intltag,rtag;/*增加的线索标记*/structtnode*lchild;structtnode*rchild;}TBTNode;voidCreateTBTNode(TBTNode*&b,char*s

7、tr){TBTNode*St[MaxSize],*p=NULL;inttop=-1,k,j=0;charch;b=NULL;/*建立的二叉树初始时为空*/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=

8、ch;p->lchild=p->rchild=NULL;if(b==NULL)/**p为二叉树的根结点*/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){printf("%c",b->data);if(b->lchild!=NULL

9、

10、b->rchild!=NULL){printf(

11、"(");DispTBTNode(b->lchild);if(b->rchild!=NULL)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

12、->rchild==NULL)/*后继线索*/{pre->rchild=p;/*建立前驱结点的后继线索*/pre->rtag=1;}elsepre->rtag=0;pre=p;Thread(p->rchild);/*右子树线索化*/}}TBTNod