《数据结构实验三实验报告(共5页).docx》由会员分享，可在线阅读，更多相关《数据结构实验三实验报告(共5页).docx（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、精选优质文档-倾情为你奉上数据结构与算法设计实验报告实验三学院：自动化学院班级：_学号：_姓名：_陈惠娟_一 实验目的了解并熟悉二叉树的存储结构及其各种操作，掌握各种二叉树的遍历方法。二实验内容 遍历二叉树：要求：请输入一棵二叉树的扩展的前序序列，经过处理后生成一棵二叉树，然后对于该二叉树输出前序、中序和后序遍历序列。例如：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;cinch;if(ch=*) t=NULL;elseif(!(t=(BiTree)malloc(sizeof(BiTNode) exit(0);t-data=ch;buildtree(t-lchild);buildtree(t-rchild);前序遍历二叉树并输出遍历结果的函数：void
3、PreOrderTraverse(BiTree t)if(t) coutdata;PreOrderTraverse(t-lchild);PreOrderTraverse(t-rchild);中序遍历二叉树并输出遍历结果的函数：void InOrderTraverse(BiTree t)if(t) InOrderTraverse(t-lchild);coutdata;InOrderTraverse(t-rchild);后序遍历二叉树并输出遍历结果的函数：void PostOrderTraverse(BiTree t)if(t) PostOrderTraverse(t-lchild);PostOr
4、derTraverse(t-rchild);coutdata;主函数：void main() BiTree T;buildtree(T);cout先序序列为：; PreOrderTraverse(T); coutendl; cout中序序列为：; InOrderTraverse(T);coutendl; cout后序序列为：; PostOrderTraverse(T);coutendl;四程序调试分析 程序运行中遇到的问题：在运行函数的初期总是不能解决怎样判断该另起一层来建立二叉树，导致建立的二叉树排布不到正确的位置上。改正措施：后来发现其实我考虑的有点复杂化了，因为二叉树的存储顺序的特殊性，
5、不用考虑建立二叉树的时候是否会在一层上超出可用的空间或者非最后一层上排布不满的问题，设计标记来控制二叉树的层次问题反而是多此一举。对程序调试的体会与收获：应该更深入的理解二叉树的结构，就能避免在编写程序时因为对二叉树结构的不熟悉而导致的程序复杂化，一个好的程序应该是用最精简的语言来完成较为复杂的任务，同时保证其正确性，这是我体会到的。五用户使用说明 输入扩展的二叉树前序序列的结点的值，没有赋值的结点输入*，回车后，程序会输出此二叉树的前序中序和后序的遍历结果（没有*的结点）；六程序运行结果七程序清单#include#includeusing namespace std;typedef stru
6、ct BiTNode char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree; /定义结点中包括数据和指向左右孩子的指针void buildtree(BiTree &t) /建立二叉树char ch;cinch;/输入二叉树的结点数据if(ch=*) t=NULL; /如果输入*，则将结点置为空elseif(!(t=(BiTree)malloc(sizeof(BiTNode) exit(0); /判定结点空间是否申请成功t-data=ch; /将输入的数据赋给对应的结点buildtree(t-lchild); /同样建立结点的左孩子b
7、uildtree(t-rchild); /同样建立结点的右孩子void PreOrderTraverse(BiTree t) /前序遍历二叉树if(t) coutdata;PreOrderTraverse(t-lchild);PreOrderTraverse(t-rchild);void InOrderTraverse(BiTree t) /中序遍历二叉树if(t) InOrderTraverse(t-lchild);coutdata;InOrderTraverse(t-rchild);void PostOrderTraverse(BiTree t) /后序遍历二叉树if(t) PostOrderTraverse(t-lchild);PostOrderTraverse(t-rchild);coutdata; void main() /主函数 BiTree T; /定义一个二叉树的根结点buildtree(T); /建立二叉树cout先序序列为：; PreOrderTraverse(T); /前序遍历二叉树 coutendl; cout中序序列为：; InOrderTraverse(T);coutendl; /中序遍历二叉树 cout后序序列为：;PostOrderTraverse(T);coutendl; /后序遍历二叉树专心-专注-专业