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