学号：2015111840 姓名：陈周擎 专业：计算机科学与技术 知识范畴：树 完成日期：2016年04月28日 实验题目：顺序存储完全二叉树先、中、后序遍历 实验内容及要求：
输入一个字符串，存储于一维数组。以该一维数组作为完全二叉树的存储结构，实现先、中、后序遍历，输出遍历结果。
将该完全二叉树转换为二叉链表存储结构，然后基于二叉链表存储结构再次进行先、中、后序遍历并输出遍历结果。
实验目的：掌握完全二叉树的顺序存储与链式存储结构以及遍历算法。 数据结构设计简要描述：
分别以一维数组和二叉链表为存储结构存储二叉树，并实现先序、中序、后序遍历。 算法设计简要描述：
分别以一维数组和二叉链表为存储结构存储二叉树。
以一维数组存储时，假设双亲结点的下标为i，则左儿子、右儿子的下标分别为2*i+1、2*i+2。利用递归算法分别对左子树和右子树进行遍历。
以二叉链表为存储结构时，结点数据域存储结点数据，然后依次递归左子树和右子树。 输入/输出设计简要描述：
本实验中输入和输出分别只有一次。 输入：输入一个字符串，存储到一维数组中
输出：分别以一维数组和二叉链表为存储结构存储二叉树时，先序、中序、后序遍历结果。 编程语言说明：
1.编程软件，Code Blocks 16.0； 2.代码均用C++语言实现；
3.输入输出采用C++语言的cout和cin函数； 4.程序注释采用C/C++规范；
5.动态存储分配采用C++的new和delete操作符实现 主要函数说明：
void preorder_array(char *s,int i,int count) //一维数组作为存储结构的前序遍历 void midorder_array(char *s,int i,int count) //一维数组作为存储结构的中序遍历 void lasorder_array(char *s,int i,int count) //一维数组作为存储结构的后序遍历 void trans_tree(BiT &bt,char *s,int count,int t) //将该完全二叉树存储结构转换
void preorder(BiT bt) //以二叉链表前序遍历 void midorder(BiT bt) //以二叉链表中序遍历 void lasorder(BiT bt) //以二叉链表后序遍历 程序测试简要报告： （1） 测试实例1
1 / 7
评分 满分——5分 输入：
Preorder: a b d e c Midorder: d b e a c Lasorder: d e b c a Please input：abcde Preorder_array: a b d e c Midorder_array: d b e a c Lasorder_array: d e b c a 输出：
运行界面：
结论：程序输出结果与期望输出结果相符。
（2） 测试实例1
输入：
Preorder: a b j d c h r Midorder: j b d a h o r Lasorder: j d b h r c a Please input：abcjdhr
Preorder_array: a b j d c h r Midorder_array: j b d a h o r Lasorder_array: j d b h r c a 输出：
运行界面：
2 / 7
结论：程序输出结果与期望输出结果相符。
（3） 测试实例1
输入：
Preorder:a b n r i j e d f k Midorder:r n i b e j a f d k Lasorder:r i n e j b f k d a Please input:abdnjfkrie
Preorder_array:a b n r i j e d f k Midorder_array:r n I b e j a f d k Lasorder_array:r I n e j b f k d a 输出：
运行界面：
结论：程序输出结果与期望输出结果相符。
（4） 测试实例1
输入：
Preorder:a b d h i e j k c f g Midorder:h d i b j e k a f c g
3 / 7
Please input：abcdefghijk
Preorder_array:a b d h i e j k c f g Midorder_array:h d i b j e k a f c g Lasorder_array:h i d j k e b f g c a
输出：
Lasorder:h i d j k e b f g c a
运行界面：
结论：程序输出结果与期望输出结果相符。 源程序代码： #include typedef struct node { char data; //数据域 struct node *lchild; //左指针 struct node *rchild; //右指针 }*BiT,BiTNode; void preorder_array(char *s,int i,int count) //一维数组作为存储结构的前序遍历 { if(i>count) //遍历结束时，退出 return; cout< void midorder_array(char *s,int i,int count) //一维数组作为存储结构的中序遍历 { if(i>count) //遍历结束时，退出 4 / 7 return; midorder_array(s,2*i+1,count); //递归遍历左儿子 cout< void lasorder_array(char *s,int i,int count) //一维数组作为存储结构的后序遍历 { if(i>count) //遍历结束时，退出 return; lasorder_array(s,2*i+1,count); //递归遍历左儿子 lasorder_array(s,2*i+2,count); //递归遍历右儿子 cout< if(t>count) //遍历结束时，退出 return; bt=new BiTNode(); bt->data=s[t]; //填充结点 bt->lchild=NULL; //左儿子置空 bt->rchild=NULL; //右儿子置空 trans_tree(bt->lchild,s,count,t*2+1); //递归遍历左儿子 trans_tree(bt->rchild,s,count,t*2+2); //递归遍历右儿子 } void preorder(BiT bt) //以二叉链表前序遍历 { if(bt) //树非空 { cout< preorder(bt->lchild); //递归遍历左儿子 preorder(bt->rchild); //递归遍历右儿子 } } 5 / 7 void midorder(BiT bt) //以二叉链表中序遍历 { if(bt) //树非空 { midorder(bt->lchild); //递归遍历左儿子 cout< midorder(bt->rchild); //递归遍历右儿子 } } void lasorder(BiT bt) //以二叉链表后序遍历 { if(bt) //树非空 { lasorder(bt->lchild); //递归遍历左儿子 lasorder(bt->rchild); //递归遍历右儿子 cout< int count=0,t=0; char *str=new char; cout<<\"please input array:\"; cin>>str; count=strlen(str); //求数组长度 cout<<\"preorder_array:\"; preorder_array(str,0,count); cout< 6 / 7 cout< 因篇幅问题不能全部显示，请点此查看更多更全内容