数据结构-二叉树的建立与遍历

《数据结构-二叉树的建立与遍历》由会员分享，可在线阅读，更多相关《数据结构-二叉树的建立与遍历（12页珍藏版）》请在装配图网上搜索。

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、 二叉树结点的类型描述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;（二） 每个模块的分析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月

10、1日下午完毕代码的编写并修改对的。由于本次实验和广义表的建立和输出有相似之处，因此大的问题基本没有浮现，某些小的问题也及时发现并纠正。本次实验，我很感谢教师和同窗对我的指点。通过本次实验，对二叉树的存储构造有了更深的结识，对某些细节更加理解，收获了诸多。教师评语：实验成绩：指引教师签名： 批阅日期： 代码：# 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域和rch

12、ild域为空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=,)/若字符为,，执行如下操作

13、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=K.pinK.top;/出栈，令目前结点p为栈顶元素K.top-;else/若字符为字母，执行如下操作p-data=sj;/令目前结点p的data域为该字母if(sj+1=()/若该字

14、母的下一种字符为(则令目前结点指针p进栈K.top+;K.pinK.top=p;printf(n);/void Preorder(BiTNode *B,SeqStack &K)/遍历二叉树函数printf(先序遍历成果为:);/提示如下成果为先序遍历成果BiTNode *p;/p指针指向目前结点p=B;/目前结点为根结点K.top+;/令目前结点指针p进栈K.pinK.top=p;while(K.top!=-1)/当栈不为空时执行如下操作p=K.pinK.top;/出栈，栈顶元素所指的结点作为目前结点pK.top-;printf(%c,p-data);/输出目前结点p中的字母if(p-rchi

15、ld!=NULL)/若目前结点p的右孩子不为空，则令目前结点p的右孩子进栈K.top+;K.pinK.top=p-rchild;if(p-lchild!=NULL)/若目前结点p的左孩子不为空，则令目前结点p的左孩子进栈K.top+;K.pinK.top=p-lchild;printf(n);/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(s0!=0)Preorder(B,K);/若输入不为空，调用遍历二叉树的函数else printf(二叉树未建立n);/若输入为空，则输出该提示printf(n与否继续?（是,输入1;否,输入0）:);/提示与否继续scanf(%d,&i);if(i=1) getchar();/输入1表达继续printf(n);if(i=0) break;/输入0表达结束return 0;