二叉树前序或中序或后序遍历

1、数学与计算机学院计算机系实验报告课程名称： 数据结构指导教师课程名称： 数据结构指导教师： 黄襄念实验名称：二叉树前序或中序或后序遍历实验序号：实验3年级：2010实验成绩姓名：实验教室学号：实验日期实验时间：8:0011:40实验学时6A-4132012/6/104一、实验目的熟悉的掌握树的创建，和树的前序、中序、后序遍历。二、实验环境操作系统：Windows7开发软件： Microsoft Visual C+ 6.0三、实验内容程序功能本程序完成了以下功能前序遍历中序遍历后序遍历 数据结构本程序中使用的数据结构(若有多个，逐个说明)：1. 它的优缺点1 ) 可以快速的查找数据。2) 让数据

2、层次更加清晰。2. 逻辑结构图3. 存储结构图2. 逻辑结构图3. 存储结构图4. 存储结构的 C/C+ 语言描述 typedef struct node DataType data; struct node *lchild; struct node *rchild; BiTNode, *BiTree; typedef BiTree type;算法描述本程序中采用的算法算法名称：递归算法原理或思想 是通过访问结点的左右孩子来进行循环查找的方法，拿中序遍历来说明：先从头结 点开始，再去访问头结点的右孩子如果为空就访问头结点的左孩子，依次进行访问 当结点的左右孩子都为空时，就访问上一级，到了最后。

3、算法特点它能将查找进行 2 分，体现出了更高效快捷的特点，并且层次很清晰。 程序说明代码：void InOrder(BiTree root) Stack S(100);initStack(S);BiTNode *p = root; do while(p != NULL) Push(S, p);p = p-lchild; if(!isEmpty(S)Pop(S, p);cout data rchild; while(p != NULL | !isEmpty(S); cout rchild; if(!isEmpty(S)Pop(S, p);p = p-lchild; while(p != NULL

4、 | !isEmpty(S); while(!isEmpty(SS) Pop(SS, p); cout data ; cout endl;3) 中序遍历模块：将树进行从左孩子开始再头结点再右孩子 代码： void PreOrder(BiTree root)Stack S(100); initStack(S);BiTNode *p = root;do while(p != NULL) Push(S, p);cout data lchild;if(!isEmpty(S)Pop(S, p);p = p-rchild; while(p != NULL | !isEmpty(S); cout endl;

5、四、调试与运行1. 程序调试本程序开发过程中，采用的调试方法或手段如下：方法1：在程序执行的终止的函数中加一条输出语句coutvv”*”vvendl；进行 错误的定位，调试了指针没有正确使用的错误。方法 2：输出一些树中的数据，看能不能正确的输出，调试了其左右孩子是不是正 确。2. 运行结果本次实验多个功能需分别截图，逐个说明。MHXMHXMHXMHXMHXMH JCH X运行结果图1历历历序 H 12 3 0B C D E G F输入你的选屋B C D E G F输入你的选毘B E G D F A输入你的选择:G E F D B A输入尔的选择:ress any key to continu

6、e五、实验总结结果分析：本程序完成了树的前序遍历、中序遍历、后序遍历功能；但是还是存在不 完善的地方，没有对结点进行删除增加等操作，没有将树的结构给输出。心得体会：通过这个实验我更熟练的掌握了二叉树的结构同时也更了解了递归算法， 觉得数据结构是一个很不错的一门课程。代码：#include #include using namespace std;using std:cout;using std:endl;typedef char DataType;typedef struct node DataType data;struct node *lchild;struct node *rchild;

7、 BiTNode, *BiTree;typedef BiTree type;class Stackfriend void initStack(Stack &S);friend bool isEmpty(Stack &S);friend bool Push(Stack &S, type x);friend bool Pop(Stack &S, type &x);friend bool getTop(Stack &S, type &x);public:Stack(int maxSize)if(maxSize maxSize = maxSize; this-s = NULL;virtual Stac

8、k()if(this-s != NULL)delete this-s; this-s = NULL;protected:int maxSize; std:stack *s;void initStack(Stack &S)if(S.s != NULL)delete S.s;S.s = NULL; S.s = new std:stack(); bool isEmpty(Stack &S) return S.s-empty();bool Push(Stack &S, type x)if(S.s-size() = S.maxSize) return false;S.s-push(x); return

9、true;bool Pop(Stack &S, type &x)if(S.s-empty()return false;x = S.s-top();S.s-pop();return true;bool getTop(Stack &S, type &x)if(S.s-empty()return false;x = S.s-top(); return true;void PreOrder(BiTree root)Stack S(100); initStack(S); BiTNode *p = root; do while(p != NULL)Push(S, p); cout data lchild;

10、 if(!isEmpty(S) Pop(S, p);p = p-rchild; while(p != NULL | !isEmpty(S); cout lchild; if(!isEmpty(S) Pop(S, p);cout data rchild; while(p != NULL | !isEmpty(S); cout rchild; if(!isEmpty(S)Pop(S, p);p = p-lchild; while(p != NULL | !isEmpty(S); while(!isEmpty(SS)Pop(SS, p);cout data cout endl;void menu()coutvv*1.中序遍历*vvendl;coutvv*2.前序遍历*vvendl;coutvv*3.后序遍历*vvendl;coutvv*0.退出程序*vvendl;!cout!c