《数据结构报告树的二叉树存储与遍历》由会员分享，可在线阅读，更多相关《数据结构报告树的二叉树存储与遍历（5页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告实验题目: 森林的二叉树存储与遍历实验目的：掌握森林的二叉树存储方式，进一步熟悉二叉树的建立与遍历过程。实验内容：以广义表形式输入森林，建立其二叉树存储结构，用中序遍历的方法输出森林元素，要求程序非递归。一、需求分析以广义表形式输入森林，建立其二叉树存储结构，用中序遍历的方法输出森林元素，要求程序非递归。1、输入的形式和输入值的范围；本程序要求以广义表的形式输入森林元素，仅能使用字母，逗号和左右括号，其中，左括号表示双亲与孩子的关系，逗号表示兄弟关系。例如：(a(b(d),c),e(f),g(h,i(j,k)2、输出的形式； 本程序输出为二叉树的中序遍历，输出全为字母。3、程序
2、所能达到的功能； 程序的功能即是用二叉树存储结构存储森林，并能遍历并输出森林中的元素。4、测试数据：输入数据：(a(b(d),e(f),g(h,i(j,k)输出数据：dbcafehjkig二 概要设计本程序中，首先需定义一个结构体作为二叉树的结点，结点需包含一个字符型变量与两个指向二叉树结点类型的指针，分别指向其左右孩子。还需定义一个栈结构，以及栈的各种操作，用来存放指针。主程序中，首先将输入元素存在一个字符型数组中，然后分别通过调用创建二叉树函数，与遍历输入函数，完成该实验。在调用各个子函数的时候，还会调用栈的各种操作。三 详细设计1.定义二叉树节点：typedef struct snode
3、 /定义二叉树结点char data;struct snode *lchild,*rchild;BTree;2.定义栈结构以及栈的各种操作：typedef struct /定义栈结构BTree *datamaxlen;int top;SeqStack;int Push(SeqStack *s,BTree *x) /进栈s-top+;s-datas-top=x;return 1;BTree * Pop(SeqStack *s) /出栈 BTree *x;x=s-datas-top;s-top-;return x;BTree * Get(SeqStack *s) /取栈顶元素 BTree *x;x
4、=s-datas-top;return x;3.创建二叉树函数：BTree * CreateBT(char *s,SeqStack *k) /创建二叉树BTree *root,*p;root=p=NULL;char ch;ch=*s;s+;if(ch!=0)p=root=(BTree *)malloc(sizeof(BTree); p-lchild=p-rchild=NULL;ch=*s;s+;while(ch!=0)if(ch=()p-lchild=(BTree *)malloc(sizeof(BTree);p=p-lchild;p-lchild=p-rchild=NULL;else if(
5、ch=65&ch=97&chdata=ch;Push(k,p);else if(ch=,)p-rchild=(BTree *)malloc(sizeof(BTree);p=p-rchild;p-lchild=p-rchild=NULL;Pop(k);elsePop(k);p=Get(k);ch=*s;s+;return root;4.中序遍历输出函数：void DispBT(BTree *g,SeqStack *k) /中序遍历并输出BTree *q=g;while(q!=NULL)Push(k,q);q=q-lchild;q=Get(k);printf(%c,q-data);while(k-
6、top!=-1)if(q-rchild=NULL)if(k-top!=-1)Pop(k);if(k-top!=-1)q=Get(k);printf(%c,q-data);elseq=q-rchild;if(k-top!=-1)Pop(k);while(q!=NULL)Push(k,q);q=q-lchild;if(k-top!=-1)q=Get(k);printf(%c,q-data);5.主程序以及其调用函数关系：void main()BTree *t;printf(输入树的广义表形式:n);char strmaxlen;SeqStack *k;k=(SeqStack *)malloc(si
7、zeof(SeqStack);k-top=-1;char *s=gets(str);t=CreateBT(s,k);printf(中序遍历输出为:n);k-top=-1;DispBT(t,k);printf(n);四 使用说明、测试分析及结果1、说明如何使用你编写的程序；程序名为5.exe，运行环境为visual C+。程序执行后显示： 输入树的广义表形式：然后按要求输入内容，程序运行输出遍历结果。2、测试结果与分析；测试元素为：(a(b(d),c),e(f),g(h,i(j,k)输出结果为：dbcafehjkig3、运行界面。五、实验总结(实验心得)你在编程过程中花时多少？三个小时多少时间在纸上设计？半个小时多少时间上机输入和调试？编写程序一小时，调试一个半小时多少时间在思考问题？编程过程中一直在思考遇到了哪些难题？程序出现很多小错误，导致输出有问题你是怎么克服的？用单步调试，以及自己在纸上按照程序流程实现，从而发现问题并且解决。你的收获有哪些？更加熟悉二叉树的建立与遍历操作，学会更有效率的调试程序。教师评语：实验成绩：指导教师签名： 批阅日期：
