数据结构二叉树前中后序非递归遍历.doc

数据结构《实验2》实验报告 实验项目2：二叉树前序、中序非递归遍历 学　　号 姓　　名 课程号 实验地点 指导教师 时间 评语： 按时完成实验；实验内容和过程记录完整；回答问题完整、正确；实验报告的撰写认真、格式符合要求；无抄袭的行为。 成绩 教师签字 二叉树中序、后序非递归遍历 1、预习要求：二叉树结构定义。 2、实验目的： （1）了解二叉树结构遍历概念； （2）理解二叉树二种不同遍历过程； （3）掌握二叉树遍历算法程序。 3、实验内容及要求： （1）建立包含10个结点的二叉树（树结构和数据元素的值由自己设定）； （2）完成二叉树非递归遍历程序； （3）给出程序和每种遍历程序的结果。 4、实验设备（环境）及要求 硬件：支持 Intel Pentium Ⅱ及其以上 CPU ，内存 128MB 以上、硬盘 1GB 以上容量的微机。 软件：配有 Windows98/2000/XP 操作系统，安装 Visual C++ 。 5、实验时间：10学时 6、该文档的文件名不要修改，存入学号 姓名 命名的文件夹中 7、该表中的数据只需填空，已有内容不要修改 实验结果（运行结果界面及源程序，运行结果界面放在前面）： 依次是前序，中序，后序遍历的截屏 #define STUDENT EType #includeiostream.h #include stdlib.h #includestring.h #includemath.h #includeiomanip.h //二叉树链式结构定义 struct STUDENT { char name[10]; char number[12]; char place[10]; char sex[3]; int age; }; struct BinaryTreeNode { EType data; BinaryTreeNode *LChild; BinaryTreeNode *RChild; }; typedef BinaryTreeNode BinaryTree; //堆栈结构定义 struct SType { BinaryTreeNode *ptr; bool status; }; struct Stack { SType *element; int top; int Maxsize; }; struct Node_Ptr { BinaryTreeNode *ptr; } ; void DigitalToString(char str[],int n) { char temp; char k=1; int i=0; while (n i80) { k=n%10+48; n=n/10; str[i]=k; i++; } str[i]=\0; int len=strlen(str); for (i=0;ilen/2;i++) { temp=str[i]; str[i]=str[len-i-1]; str[len-i-1]=temp; } } void CreatStack(Stack S,int MaxStackSize) {//构造一个最大容量为MaxStackSize的堆栈 S.Maxsize=MaxStackSize; S.element=new SType[S.Maxsize]; S.top=-1; } bool IsEmpty(Stack S) {//判断堆栈是否为空 if(S.top==-1)return true; return false; } bool IsFull(Stack S) {//判断堆栈是否为满 if(S.top= S.Maxsize-1) return true; else return false; } bool GetTop(Stack S,SType result) {//返回堆栈S中栈顶元素 if(IsEmpty(S))return false; result=S.element[S.top]; return true; } bool Pop(Stack S,SType result) {//将S栈顶的值取至result中，返回出栈后的状态 if(IsEmpty(S))return false; result.ptr=S.element[S.top].ptr; result.status=S.element[S.top].status; S.top--; return true; } bool Push(Stack S,SType result) {/