资源描述：
《数据结构报告树的二叉树存储与遍历.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、《数据结构》实验报告◎实验题目:森林的二叉树存储与遍历◎实验目的：掌握森林的二叉树存储方式，进一步熟悉二叉树的建立与遍历过程。◎实验内容：以广义表形式输入森林，建立其二叉树存储结构，用中序遍历的方法输出森林元素，要求程序非递归。一、需求分析以广义表形式输入森林，建立其二叉树存储结构，用中序遍历的方法输出森林元素，要求程序非递归。1、输入的形式和输入值的范围；本程序要求以广义表的形式输入森林元素，仅能使用字母，逗号和左右括号，其中，左括号表示双亲与孩子的关系，逗号表示兄弟关系。例如：(a(b(d)
2、,c),e(f),g(h,i(j,k)))2、输出的形式；本程序输出为二叉树的中序遍历，输出全为字母。3、程序所能达到的功能；程序的功能即是用二叉树存储结构存储森林，并能遍历并输出森林中的元素。4、测试数据：输入数据：(a(b(d),e(f),g(h,i(j,k)))输出数据：dbcafehjkig二概要设计本程序中，首先需定义一个结构体作为二叉树的结点，结点需包含一个字符型变量与两个指向二叉树结点类型的指针，分别指向其左右孩子。还需定义一个栈结构，以及栈的各种操作，用来存放指针。主程序中，首先
3、将输入元素存在一个字符型数组中，然后分别通过调用创建二叉树函数，与遍历输入函数，完成该实验。在调用各个子函数的时候，还会调用栈的各种操作。三详细设计 1.定义二叉树节点：typedefstructsnode//定义二叉树结点{chardata;structsnode*lchild,*rchild;}BTree;2.定义栈结构以及栈的各种操作：typedefstruct//定义栈结构{BTree*data[maxlen];inttop;}SeqStack;intPush(SeqStack*s,B
4、Tree*x)//进栈{s->top++;s->data[s->top]=x;return1;}BTree*Pop(SeqStack*s)//出栈{BTree*x;x=s->data[s->top];s->top--;returnx;}BTree*Get(SeqStack*s)//取栈顶元素{BTree*x;x=s->data[s->top];returnx;｝3.创建二叉树函数：BTree*CreateBT(char*s,SeqStack*k)//创建二叉树{BTree*root,*p;roo
5、t=p=NULL;charch;ch=*s;s++;if(ch!=' '){p=root=(BTree*)malloc(sizeof(BTree));p->lchild=p->rchild=NULL;ch=*s;s++;}while(ch!=' '){if(ch=='('){p->lchild=(BTree*)malloc(sizeof(BTree));p=p->lchild;p->lchild=p->rchild=NULL;}elseif(ch>=65&&ch<=90
6、
7、ch>=97&&c
8、h<=122){p->data=ch;Push(k,p);}elseif(ch==','){p->rchild=(BTree*)malloc(sizeof(BTree));p=p->rchild;p->lchild=p->rchild=NULL;Pop(k);}else{Pop(k);p=Get(k);}ch=*s;s++;}returnroot;}4.中序遍历输出函数：voidDispBT(BTree*g,SeqStack*k)//中序遍历并输出{BTree*q=g;while(q!=NULL
9、){Push(k,q);q=q->lchild;}q=Get(k);printf("%c",q->data);while(k->top!=-1){if(q->rchild==NULL){if(k->top!=-1)Pop(k);if(k->top!=-1){q=Get(k);printf("%c",q->data);}}else{q=q->rchild;if(k->top!=-1)Pop(k);while(q!=NULL){Push(k,q);q=q->lchild;}if(k->top!=-1
10、){q=Get(k);printf("%c",q->data);}}}}5.主程序以及其调用函数关系：voidmain(){BTree*t;printf("输入树的广义表形式:");charstr[maxlen];SeqStack*k;k=(SeqStack*)malloc(sizeof(SeqStack));k->top=-1;char*s=gets(str);t=CreateBT(s,k);printf("中序遍历输出为:");k->top=-1;DispBT(t,k);printf
