还剩8页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
《数据结构》实验报告◎实验题目:二叉树的建立与遍历◎实验目的
1、掌握使用Visual C++
6.0上机调试程序的基本方法;
2、掌握二叉树的存储结构和非递归遍历操作的实现方法
3、提高自己分析问题和解决问题的能力,在实践中理解教材上的理论◎实验内容利用链式存储结构建立二叉树,然后先序输出该二叉树的结点序列,在在本实验中不使用递归的方法,而是用一个栈存储结点的指针,以此完成实验要求
一、需求分析
1、输入的形式和输入值的范围根据提示,输入二叉树的括号表示形式,按回车结束
2、输出的形式输出结果为先序遍历二叉树所得到的结点序列
3、程序所能达到的功能输入二叉树后,该程序可以建立二叉树的链式存储结构,之后按照一定的顺序访问结点并输出相应的值,从而完成二叉树的先序遍历
4、测试数据输入二叉树的括号表示形式:ABD,G,CE,F先序遍历结果为:ABDGCEF;是否继续?是,输入1否,输入0:1输入二叉树的括号表示形式二叉树未建立;是否继续?是,输入1否,输入0:0Press anykey tocontinue二概要设计
1、二叉树的链式存储结构是用一个链表来存储一棵二叉树,二叉树中每一个结点用链表中的一个链结点来存储每一个结点的形式如下图所示I childdata rchild其中data表示值域,用于存储对应的数据元素,Ichild和rchild分别表示左指针域和右指针域,用于分别存储左孩子结点和右孩子结点的存储位置
2、二叉树的建立本程序中利用数组存储所输入的二叉树,然后从头到尾扫描数组中的每一个字符根据字符的不同分别执行不同的操作,并用一个存储结点指针的栈辅助完成在扫描前先申请一个结点作为根结点,也是当前指针所指结点,在二叉树的建立的过程中,每次申请一个新结点,需对其进行初始化,即令Ichild域和rchild域为空按照本程序的思路,二叉树A BD,G,C E,F的链式存储结构如下图所示二叉树建立的具体过程见详细设计部分
3、二叉树的先序遍历在二叉树的先序遍历过程中也需利用一个存储结点指针的栈辅助完成,初始时栈为空,二叉树遍历结束后栈也为空,所以在开始时将头结点入栈,之后根据当前指针所指结点的特性的不同执行不同的操作,以栈空作为二叉树遍历的结束条件二叉树先序遍历的具体过程见详细设计部份A BD,G,C E,F
4、本程序的基本操作和模块建立二叉树的函数void CreateBiTNode*B,SeqStack K,char s[]遍历二叉树的函数voidPreorderBiTNode*B,SeqStack K主函数main函数的调用关系如下图所示函数Create函数Preorder三详细设计一元素类型、结点类型
1、二叉树结点的类型描述typedef struct node/*二叉树结点的类型描述*/char data;/*data用于存储二叉树中的字母*/struct node*lchild;/*lchild为指向该结点左孩子的指针*/struct node*rchild;/child为指向该结点下一层的指针*/}BiTNode;
2、顺序栈的类型描述typedef struct//顺序栈的类型描述*/(/*指针数组,用于存储广义表结点指针*/BiTNode*pin
[40];int top;/*栈顶指针★/}SeqStack;
(二)每一个模块的分析
1、主程序模块main
①定义数组,存储输入的字符串
②定义并申请根结点
③初始化顺序栈
④⑴while调用建立二叉树的函数,建立二叉树的链式存储结构调用遍历二叉树的函数,输出所建立的二叉树的结点选择是否继续,若是,则重新执行循环中的操作;若否,则退出循环
2、建立二叉树的函数void CreateBiTNode*B,SeqStack K,char s[]
①定义表示当前结点的指针p,和表示新申请结点的指针q令p指向根结点,根结点的Ichild域和rchild域为空
②输入二叉树
③从头到尾扫描输入的字符,进入以下循环,当遇到空字符时结束循环;forj=0s[j]!=\0;j++◎若字符为,执行以下操作]a.若T的下一个字符为工当前结点p的Ichild域为空b.若的下一个字符不为?则执行以下的操作申请新结点q,并令新结点q的Ichild域和rchild域为空令当前结点p的Ichild域指向新申请的结点q将新申请的结点q作为新的当前结点p◎若字符为二执行以下操作令当前结点p为栈顶元素,但不退栈申请新结点q,并令新结点q的Ichild域和rchild域为空令当前结点p的rchild域指向新申请的结点q将新申请的结点q作为新的当前结点p◎若字符为,执行以下操作出栈,令当前结点p为栈顶元素}◎若字符为字母,执行以下操作.令当前结点p的data域为该字母若该字母的下一个字符为则令当前结点指针p进栈}
3、遍历二叉树的函数void DisplayGLNode*G,SeqStack K{
①定义表示当前结点的指针p,并令P指根结点
②指向根结点的指针P入栈,使栈不空
③当栈不空时执行以下操作whileK.top!=-1出栈,栈顶元素所指的结点作为当前结点p,输出当前结点P中的字母若当前结点P的右孩子不为空,则令当前结点P的右孩子进栈若当前结点P的左孩子不为空,则令当前结点P的左孩子进栈}四使用说明、测试分析及结果
1、程序使用说明;1本程序运行环境为Visual C++
6.02根据界面提示进行操作,注意输入的字符为西文字符
2、测试结果与分析页面提示“输入二叉树的括号表示形式:输入“ABD,G,CE,F,按回车确定,页面显示如下:“先序遍历结果为:ABDGCEF;是否继续?(是,输入否,输入)”10,输入序号“1”按回车确定,表示继续操作页面提示“输入二叉树的括号表示形式:不输入二叉树,直接按回车确定,则页面显示如下“二叉树未建立;是否继续?(是,输入否,输入)10:,输入序号“0”按回车确定,表示结束操作,页面显示如下“Press anykey tocontinue”由上测试结果分析得,该程序功能满足题目要求
3、调试过程中遇到的问题及解决方法当代码编写完成后,编译过程浮现了不少小错误,比如语句末尾漏掉分号,使用了某些变量却未定义,但这些问题很快发现并及时纠正总的来说,因为本次实验和广义表的建立和输出有相似之处,所以避免了不少问题,比较顺利
4、运行界面
五、实验总结本次实验提前作了预习,在编写程序上花费的时间不算太多,我在11月1日下午完成代码的编写并修改正确因为本次实验和广义表的建立和输出有相似之处,所以大的问题基本没有浮现,一些小的问题也及时发现并纠正本次实验,我很感谢老师和同学对我的指点通过本次实验,对二叉树的存储结构有了更深的认识,对一些细节更加理解,收获了不少实验成绩:指导教师签名:审阅日期教师评语:代码#includestdio.h#includestdlib.h//------------------------------------------------------------------------------------------------------------------------------------typedef struct node〃二叉树结点的类型描述char data;//data用于存储二叉树中的字母structnode*lchild;//Ichild为指向该结点左孩子的指针structnode*rchild;//rchild为指向该结点下一层的指针JBiTNode;//typedef struct〃顺序栈的类型描述BiTNode*pin
[40];〃指针数组,用于存储广义表结点指针int top;〃栈顶指针}SeqStack;//---------------------------------------------------------------------------------------------------------------------void CreateBiTNode*B,SeqStack K,char s[]〃建立二叉树的函数BiTNode*p,*q;//p指针指向当前结点,q指针指向新申请的结点intj;//j用于标记输入的字符在数组中的位置printf输入二叉树的括号表示形式:〃提示输入二叉树getss;P=B;〃当前结点为根结点p-lchild=NULL;p-rchild=NULL;〃根结点的Ichild域和rchild域为空forj=0;sO]!=\0;j++〃进入循环,建立二叉树ifsO]==C〃若字符为,执行以下操作{;〃若的下一个字符为二当前结点p的Ichild域为空if so+l]==p-lchild=NULL;else〃若的下一个字符不为q=BiTNode*mallocsizeofBiTNode;〃申请新结点qq-lchild=NULL;q-rchild=NULL;〃令新结点q的Ichild域和rchild域为空p-lchild=q;//令当前结点p的Ichild域指向新申请的结点p=q;〃将新申请的结点q作为新的当前结elseifsU]==Z〃若字符为,执行以下操作p=K.pin[K.top];〃令当前结点p为栈顶元素,但不退栈q=BiTNode*mallocsizeofBiTNode;〃申请新结点qq-lchild=NULL;q-rchild=NULL;〃令新结点q的Ichild域和rchild域为空p-rchild=q;//令当前结点p的Ichild域指向新申请的结点qp=q;〃将新申请的结点q作为新的当前结点pelse{〃若字符为,执行以下操作〃出栈,令当前结点p为栈顶元素p=K.pin[K.top];K.top-;〃若字符为‘字母,执行以下操作〃令当前结点p的data域为该字母else〃若该字母的下一个字符为则令当前结点指针p进栈p-data=s[j];if sOl]==+K.top++;K.pin[K.top]=p;printf\n;//■void PreorderBiTNode*B,SeqStack K〃遍历二义树函数printf先序遍历结果为:;〃提示以卜结果为先序遍历结果BiTNode*p;P=B;〃p指针指向当前结点K.top++;〃当前结点为根结点K.pin[K.top]=p;〃令当前结点指针p进栈whileK.top!=-1〃当栈不为空时执行以下操作p=K.pin[K.top];〃出栈,栈顶元素所指的结点作为当前结点PK.top-;printf%c,p-data;〃输出当前结点p中的字母ifp-rchild!=NULL〃若当前结点p的右孩子不为空,则令当前结点p的右孩子进栈{K.top++;K.pin[K.top]=p-rchild;ifp-lchild!=NULL〃若当前结点p的左孩子不为空,则令当前结点p的左孩子进栈K.top++;K.pin[K.top]=p-lchild;;printf”\n//--------------------------------------------------------------------------------------------------------------------------------------int mainchars
[40];〃定义数组,存储输入的字符串int i;BiTNode*B;〃定义根结点,并申请存储空间B=BiTNode*mallocsizeofBiTNode;SeqStack K;//定义栈并初始化栈K.top=-1;while1{CreateB,K,s;〃调用建立二叉树的函数ifs[O]!=\O PreorderB,K;〃若输入不为空,调用遍历二叉树的函数elseprintf二叉树未建立\n“;〃若输入为空,则输出该提示printf”\n是否继续?是,输入1;否,输入0:;//提示是否继续scanfH%d,i;Hi==1getchar;〃输入1表示继续printf\n;ifi==0break;〃输入0表示结束return0;。