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

1、数据结构实验报告 评分 2015111840 姓名：陈周擎 专业：计算机科学与技术学号： 日月28知识范畴：树 完成日期：2016年04 实验题目：顺序存储完全二叉树先、中、后序遍历 分5满分 实验内容及要求：输入一个字符串，存储于一维数组。以该一维数组作为完全二叉树的存储结构，实现先、 中、后序遍历，输出遍历结果。将该完全二叉树转换为二叉链表存储结构，然后基于二叉链表存储结构再次进行先、中、 后序遍历并输出遍历结果。 实验目的：掌握完全二叉树的顺序存储与链式存储结构以及遍历算法。 数据结构设计简要描述： 分别以一维数组和二叉链表为存储结构存储二叉树，并实现先序、中序、后序遍历。 算法设计简要

2、描述： 分别以一维数组和二叉链表为存储结构存储二叉树。、，则左儿子、右儿子的下标分别为i2*i+1以一维数组存储时，假设双亲结点的下标为 2*i+2。利用递归算法分别对左子树和右子树进行遍历。 以二叉链表为存储结构时，结点数据域存储结点数据，然后依次递归左子树和右子树。 输出设计简要描述：输入/ 本实验中输入和输出分别只有一次。 输入：输入一个字符串，存储到一维数组中 输出：分别以一维数组和二叉链表为存储结构存储二叉树时，先序、中序、后序遍历结果。 编程语言说明： ；1.编程软件，Code Blocks 16.0 语言实现；代码均用C+2. 函数；cin输入输出采用C+语言的cout和3. 程

3、序注释采用4.C/C+规范； delete操作符实现new5.动态存储分配采用C+的和 主要函数说明： 一维数组作为存储结构的前序遍历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) /将该完全二叉树存储结构转

4、换 以二叉链表前序遍历void preorder(BiT bt) / void midorder(BiT bt) /以二叉链表中序遍历 void lasorder(BiT bt) /以二叉链表后序遍历 程序测试简要报告：1 （ 1）测试实例 7/ 1 输入： Please input：abcde 输出： Preorder_array: a b d e c Midorder_array: d b e a c Lasorder_array: d e b c a Preorder: a b d e c Midorder: d b e a c Lasorder: d e b c a 运行界面： 程序输

5、出结果与期望输出结果相符。结论：1 ）测试实例（2 输入：abcjdhr Please input： 输出：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 Preorder: a b j d c h r Midorder: j b d a h o r Lasorder: j d b h r c a 运行界面： 7/ 2 程序输出结果与期望输出结果相符。结论：1 测试实例（3） 输入：Please input:abdnjfkrie 输出：Preorder_array

6、: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 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 运行界面： 结论：程序输出结果与期望输出结果相符。1 测试实例（4） 输入：Please input ：abcdefghijk 输出：Preorder_array:a b d h i e j k c f g Midorder_array:h d

7、 i b j e k a f c g Lasorder_array:h i d j k e b f g c a Preorder:a b d h i e j k c f g Midorder:h d i b j e k a f c g 7/ 3 Lasorder: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; 右指针

8、 /struct node *rchild; *BiT,BiTNode; 一维数组作为存储结构的前序遍历 /void preorder_array(char *s,int i,int count) 遍历结束时，退出 /if(icount) return; coutsicount) 7/ 4 return; midorder_array(s,2*i+1,count); /递归遍历左儿子 coutsicount) /遍历结束时，退出 return; lasorder_array(s,2*i+1,count); /递归遍历左儿子 lasorder_array(s,2*i+2,count); /递归遍

9、历右儿子 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)

10、; /递归遍历右儿子 7/ 5 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_