《数据结构二叉树的建立与遍历.docx》由会员分享，可在线阅读，更多相关《数据结构二叉树的建立与遍历.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构实验报告实验题目:二叉树的建立与遍历实验目的：1、掌握使用Visual C+6.0上机调试程序的基本方法；2、掌握二叉树的存储结构和非递归遍历操作的实现方法。3、提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。实验内容：利用链式存储结构建立二叉树，然后先序输出该二叉树的结点序列，在在本实 验中不使用递归的方法，而是用一个栈存储结点的指针，以此完成实验要求。一、需求分析1、输入的形式和输入值的范围：根据提示，输入二叉树的括号表示形式，按回车结束。2、输出的形式：输出结果为先序遍历二叉树所得到的结点序列。3、程序所能达到的功能：输入二叉树后，该程序可以建立二叉树的链式存储结构，
2、之后按 照一定的顺序访问结点并输出相应的值，从而完成二叉树的先序遍历。4、测试数据：输入二叉树的括号表示形式:A(B(D(,G),C(E,F)先序遍历结果为:ABDGCEF是否继续？(是，输入1；否，输入0) :1输入二叉树的括号表示形式：二叉树未建立是否继续？(是，输入1；否，输入0) :0Press any key to continue二概要设计1、二叉树的链式存储结构是用一个链表来存储一棵二叉树，二叉树中每一个结点用链 表中的一个链结点来存储。每一个结点的形式如下图所示。I childdatar child其中data表示值域，用于存储对应的数据元素，Ichild和rchild分别表示
3、左指针域和右 指针域，用于分别存储左孩子结点和右孩子结点的存储位置。2、二叉树的建立本程序中利用数组存储所输入的二叉树，然后从头到尾扫描数组中的每一个字符根据字 符的不同分别执行不同的操作，并用一个存储结点指针的栈辅助完成。在扫描前先申请一个 结点作为根结点，也是当前指针所指结点，在二叉树的建立的过程中，每次申请一个新结点， 需对其进行初始化，即令Ichild域和rchild域为空。按照本程序的思路，二叉树A (B (D (,G), C (E , F)的链式存储结构如下图所示。二叉树建立的具体过程见详细设计部 分。3、二叉树的先序遍历在二叉树的先序遍历过程中也需利用一个存储结点指针的栈辅助完成
4、，初始时栈为空， 二叉树遍历结束后栈也为空，所以在开始时将头结点入栈，之后根据当前指针所指结点的特 性的不同执行不同的操作，以栈空作为二叉树遍历的结束条件。二叉树先序遍历的具体过程 见详细设计部份。A (B (D (, G), C (E, F)4、本程序的基本操作和模块：建立二叉树的函数：void Create(BiTNode *B,SeqStack &K,char s) 遍历二叉树的函数：void Preorder(BiTNode *B,SeqStack &K)主函数：main()函数的调用关系如下图所示：Create函数Preorder 函数三详细设计(一)元素类型、结点类型1、二叉树结点
5、的类型描述typedef struct node/*二叉树结点的类型描述*/char data;struct node *lchild;struct node *rchild;BiTNode;2、顺序栈的类型描述typedef struct（BiTNode *pin40;int top;SeqStack;（二）每一个模块的分析/*data用于存储二叉树中的字母*/ /*lchild为指向该结点左孩子的指针*/ /child为指向该结点下一层的指针*/顺序栈的类型描述*/*指针数组，用于存储广义表结点指针*/*栈顶指针/1、主程序模块main()(定义数组，存储输入的字符串定义并申请根结点初始化
6、顺序栈while(调用建立二叉树的函数，建立二叉树的链式存储结构调用遍历二叉树的函数，输出所建立的二叉树的结点选择是否继续，若是，则重新执行循环中的操作；若否，则退出循环2、建立二叉树的函数void Create(BiTNode *B,SeqStack &K,char s)(定义表示当前结点的指针p,和表示新申请结点的指针q 令p指向根结点，根结点的Ichild域和rchild域为空。输入二叉树从头到尾扫描输入的字符，进入以下循环，当遇到空字符时结束循环for(j=0；sj!=0;j+)若字符为(，执行以下操作a.若T的下一个字符为工当前结点p的Ichild域为空 b.若(的下一个字符不为？则
7、执行以下的操作：申请新结点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 Display(GLNode *G,Se
8、qStack &K)定义表示当前结点的指针p,并令P指根结点。指向根结点的指针P入栈，使栈不空。当栈不空时执行以下操作while(K.top !=-1)(出栈，栈顶元素所指的结点作为当前结点p,输出当前结点P中的字母 若当前结点P的右孩子不为空，则令当前结点P的右孩子进栈 若当前结点P的左孩子不为空，则令当前结点P的左孩子进栈)四使用说明、测试分析及结果1、程序使用说明：(1)本程序运行环境为Visual C+ 6.0；(2)根据界面提示进行操作,注意输入的字符为西文字符2、测试结果与分析：页面提示“输入二叉树的括号表示形式:输入“A(B(D(,G),C(E,F)，按回车确定，页面显示如下:“
9、 先序遍历结果为:ABDGCEF是否继续？（是，输入1；否，输入0）： ”输入序号“1”，按回车确定，表示继续操作。页面提示“输入二叉树的括号表示形式:不输入二叉树，直接按回车确定，则页面显示如下：“ 二叉树未建立是否继续？（是，输入1；否，输入0）: 输入序号“0”，按回车确定，表示结束操作，页面显示如下：“ Press any key to continue ”由上测试结果分析得，该程序功能满足题目要求。3、调试过程中遇到的问题及解决方法当代码编写完成后，编译过程浮现了不少小错误，比如语句末尾漏掉分号，使用了某些 变量却未定义，但这些问题很快发现并及时纠正。总的来说，因为本次实验和广义表的
10、建立和输出有相似之处，所以避免了不少问题，比 较顺利。4、运行界面五、实验总结本次实验提前作了预习，在编写程序上花费的时间不算太多，我在11月1日下午完成 代码的编写并修改正确。因为本次实验和广义表的建立和输出有相似之处，所以大的问题基 本没有浮现，一些小的问题也及时发现并纠正。本次实验，我很感谢老师和同学对我的指点。通过本次实验，对二叉树的存储结构有了 更深的认识，对一些细节更加理解，收获了不少。教师评语:实验成绩:指导教师签名:审阅日期：代码：# include # include/typedef struct node二叉树结点的类型描述( char data;/data用于存储二叉树中
11、的字母struct node *lchild; /Ichild为指向该结点左孩子的指针 struct node *rchild;/rchild为指向该结点下一层的指针 JBiTNode; /typedef struct顺序栈的类型描述( BiTNode *pin40; 指针数组，用于存储广义表结点指针 int top;栈顶指针SeqStack; /void Create(BiTNode *B,SeqStack &K,char s)建立二叉树的函数BiTNode *p,*q；/p指针指向当前结点,q指针指向新申请的结点intj；/j用于标记输入的字符在数组中的位置printf(输入二叉树的括号表
12、示形式:)提示输入二叉树gets(s);P=B;当前结点为根结点p-lchild=NULL;p-rchild=NULL;根结点的Ichild域和rchild域为空for(j=0;sO!=0;j+)(if(sO=C)if(so+l =；)p-lchild=NULL;进入循环，建立二叉树若字符为(，执行以下操作若的下一个字符为二当前结点p的Ichild域为空else若(的下一个字符不为q=(BiTNode *)malloc(sizeof(BiTNode); q-lchild=NULL;q-rchild=NULL;p-lchild=q;申请新结点q令新结点q的Ichild域和rchild域为空/令当
13、前结点p的Ichild域指向新申请的结点p=q;将新申请的结点q作为新的当前结elseif(sU=Z)(p=K.pinK.top;q=(BiTNode *)malloc(sizeof(BiTNode);q-lchild=NULL;q-rchild=NULL;若字符为，执行以下操作令当前结点p为栈顶元素，但不退栈申请新结点q令新结点q的Ichild域和rchild域为空/令当前结点p的Ichild域指向新申请的结点将新申请的结点q作为新的当前结若字符为)，执行以下操作出栈，令当前结点p为栈顶元素若字符为字母，执行以下操作令当前结点p的data域为该字母若该字母的下一个字符为(则令当前结点指针p进
14、栈p-rchild=q;qp=q;点p)else(p=K.pinK.top;K.top-;)else(p-data=sj;if(sO+l =() (K.top+;K.pinK.top=p;)printf(n);/void Preorder(BiTNode *B,SeqStack &K) (printf(先序遍历结果为:)；BiTNode *p;P=B;K.top+;K.pinK.top=p;while(K.top !=-1)遍历二义树函数提示以卜结果为先序遍历结果p指针指向当前结点当前结点为根结点令当前结点指针p进栈当栈不为空时执行以下操作p=K.pinK.top;K.top-;printf(
15、%c,p-data);if(p-rchild!=NULL)K.top+;K.pinK.top=p-rchild;)if(p-lchild!=NULL)(K.top+;K.pinK.top=p-lchild;)printf(”n)；出栈，栈顶元素所指的结点作为当前结点P输出当前结点p中的字母若当前结点p的右孩子不为空，则令当前结点p的右孩子进栈若当前结点p的左孩子不为空，则令当前结点p的左孩子进栈/int main()(char s40;定义数组，存储输入的字符串int i;BiTNode *B;定义根结点，并申请存储空间B=(BiTNode *)malloc(sizeof(BiTNode);SeqStack K;/定义栈并初始化栈K.top=-1;while(1) Create(B,K,s);调用建立二叉树的函数if(sO!=O) Preorder(B,K); 若输入不为空，调用遍历二叉树的函数 elseprintf(二叉树未建立n“)；若输入为空，则输出该提示 printf(”n是否继续？(是，输入1;否，输入0) :)；/提示是否继续scanf(H%d,&i);H(i=1) getchar(); 输入 1 表示继续printf(n);if(i=0) break;输入0表示结束return 0;