数据结构实验三实验报告

1、数据结构与算法设计实验报告实验三学院：自动化学院班级：_06111006_学号：_1120101652姓名：_陈惠娟_一 实验目的了解并熟悉二叉树的存储结构及其各种操作，掌握各种二叉树的遍历方法。二实验内容 遍历二叉树：要求：请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。例如：1 2 4 * 5 * * * 3三程序设计 1概要设计程序的主要功能为:根据输入的二叉树的扩展的前序序列生成一棵完全二叉树，然后分别对生成的二叉树进行前序中序和后序的遍历，并分别输出遍历结果。开始输入要建立的二叉树的扩展前序序列（空位用*补齐）建立该二叉树分别

2、前序中序和后序遍历该二叉树并输出遍历结果结束2.详细设计 定义的数据类型：typedef struct BiTNode char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;建立二叉树的函数：void buildtree(BiTree &t) char ch;cin>>ch;if(ch='*') t=NULL;elseif(!(t=(BiTree)malloc(sizeof(BiTNode) exit(0);t->data=ch;buildtree(t->lchild);buildtr

3、ee(t->rchild);前序遍历二叉树并输出遍历结果的函数：void PreOrderTraverse(BiTree t)if(t) cout<<t->data;PreOrderTraverse(t->lchild);PreOrderTraverse(t->rchild);中序遍历二叉树并输出遍历结果的函数：void InOrderTraverse(BiTree t)if(t) InOrderTraverse(t->lchild);cout<<t->data;InOrderTraverse(t->rchild);后序遍历二叉

4、树并输出遍历结果的函数：void PostOrderTraverse(BiTree t)if(t) PostOrderTraverse(t->lchild);PostOrderTraverse(t->rchild);cout<<t->data;主函数：void main() BiTree T;buildtree(T);cout<<"先序序列为：" PreOrderTraverse(T); cout<<endl; cout<<"中序序列为：" InOrderTraverse(T);cout&

5、lt;<endl; cout<<"后序序列为：" PostOrderTraverse(T);cout<<endl;四程序调试分析 程序运行中遇到的问题：在运行函数的初期总是不能解决怎样判断该另起一层来建立二叉树，导致建立的二叉树排布不到正确的位置上。改正措施：后来发现其实我考虑的有点复杂化了，因为二叉树的存储顺序的特殊性，不用考虑建立二叉树的时候是否会在一层上超出可用的空间或者非最后一层上排布不满的问题，设计标记来控制二叉树的层次问题反而是多此一举。对程序调试的体会与收获：应该更深入的理解二叉树的结构，就能避免在编写程序时因为对二叉树结构的不熟

6、悉而导致的程序复杂化，一个好的程序应该是用最精简的语言来完成较为复杂的任务，同时保证其正确性，这是我体会到的。五用户使用说明 输入扩展的二叉树前序序列的结点的值，没有赋值的结点输入*，回车后，程序会输出此二叉树的前序中序和后序的遍历结果（没有*的结点）；六程序运行结果七程序清单#include<iostream>#include<stdlib.h>using namespace std;typedef struct BiTNode char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree; /定义结点中包括数据和

7、指向左右孩子的指针void buildtree(BiTree &t) /建立二叉树char ch;cin>>ch;/输入二叉树的结点数据if(ch='*') t=NULL; /如果输入*，则将结点置为空elseif(!(t=(BiTree)malloc(sizeof(BiTNode) exit(0); /判定结点空间是否申请成功t->data=ch; /将输入的数据赋给对应的结点buildtree(t->lchild); /同样建立结点的左孩子buildtree(t->rchild); /同样建立结点的右孩子void PreOrderTra

8、verse(BiTree t) /前序遍历二叉树if(t) cout<<t->data;PreOrderTraverse(t->lchild);PreOrderTraverse(t->rchild);void InOrderTraverse(BiTree t) /中序遍历二叉树if(t) InOrderTraverse(t->lchild);cout<<t->data;InOrderTraverse(t->rchild);void PostOrderTraverse(BiTree t) /后序遍历二叉树if(t) PostOrderTraverse(t->lchild);PostOrderTraverse(t->rchild);cout<<t->data; void main() /主函数 BiTree T; /定义一个二叉树的根结点buildtree(T); /建立二叉树cout<<"先序序列为：" PreOrderTraverse(T); /前序遍历二叉树 cout<<endl; cout<<&quo