树-顺序存储完全二叉树先、中、后序遍历-实验内容与要求.doc

数据结构实验报告评分满分5分学号：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输入：Please input：abcde输出：Preorder_array: a b d e cMidorder_array: d b e a cLasorder_array: d e b c aPreorder: a b d e cMidorder: d b e a cLasorder: d e b c a运行界面：结论：程序输出结果与期望输出结果相符。（2） 测试实例1输入：Please input：abcjdhr输出：Preorder_array: a b j d c h r Midorder_array: j b d a h o rLasorder_array: j d b h r c aPreorder: a b j d c h r Midorder: j b d a h o rLasorder: j d b h r c a运行界面：结论：程序输出结果与期望输出结果相符。（3） 测试实例1输入：Please input:abdnjfkrie输出：Preorder_array:a b n r i j e d f kMidorder_array:r n I b e j a f d kLasorder_array:r I n e j b f k d aPreorder:a b n r i j e d f kMidorder:r n i b e j a f d kLasorder:r i n e j b f k d a运行界面：结论：程序输出结果与期望输出结果相符。（4） 测试实例1输入：Please input：abcdefghijk输出：Preorder_array:a b d h i e j k c f gMidorder_array:h d i b j e k a f c gLasorder_array:h i d j k e b f g c aPreorder:a b d h i e j k c f gMidorder:h d i b j e k a f c gLasorder:h i d j k e b f g c a运行界面：结论：程序输出结果与期望输出结果相符。源程序代码：#include #include #include using namespace std;typedef struct node char data; /数据域 struct node *lchild; /左指针 struct node *rchild; /右指针*BiT,BiTNode;void preorder_array(char *s,int i,int count) /一维数组作为存储结构的前序遍历 if(icount) /遍历结束时，退出 return; coutsicount) /遍历结束时，退出 return; midorder_array(s,2*i+1,count); /递归遍历左儿子 coutsicount) /遍历结束时，退出 return; lasorder_array(s,2*i+1,count); /递归遍历左儿子 lasorder_array(s,2*i+2,count); /递归遍历右儿子 coutsicount) /遍历结束时，退出 return; bt=new BiTNode(); bt-data=st; /填充结点 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) /树非空 coutdatalchild); /递归遍历左儿子 preorder(bt-rchild); /递归遍历右儿子 void midorder(BiT bt) /以二叉链表中序遍历 if(bt) /树非空 midorder(bt-lchild); /递归遍历左儿子 coutdatarchild); /递归遍历右儿子 void lasorder(BiT bt) /以二叉链表后序遍历 if(bt) /树非空 lasorder(bt-lchild); /递归遍历左儿子 lasorder(bt-rchild); /递归遍历右儿子 coutdata ; int main() int count=0,t=0; char *str=new char; coutstr; count=strlen(str); /求数组长度 coutpreorder_array:; preorder_array(str,0,count); coutendl; coutmidorder_array:; midorder_array(str,0,count); coutendl; coutlasorder_array:; lasorder_array(str,0,count); coutendl; BiT bt; trans_