C++ 二叉树的创建与遍历实验报告.doc

数据结构集中上机试验报告学院： 计算机科学与技术 专业：计算机科学与技术学号： 班级： 姓名： 2010/11/26题目：二叉树的创建与遍历 一 、实验目的1学会实现二叉树结点结构和对二叉树的基本操作。2掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。二 、实验要求1认真阅读和掌握和本实验相关的教材内容。2编写完整程序完成下面的实验内容并上机运行。3整理并上交实验报告。 三、实验内容1编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归和非递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历。 四、实验步骤源程序代码#include#includeusing namespace std;templatestruct BinTreeNode /二叉树结点类定义T data; /数据域BinTreeNode *leftChild,*rightChild; /左子女、右子女域 BinTreeNode(T x=T(),BinTreeNode* l =NULL,BinTreeNode* r = NULL ) :data(x),leftChild(l),rightChild(r) /可选择参数的默认构造函数;/-templatevoid PreOrder_2(BinTreeNode *p) /非递归前序遍历stackBinTreeNode * S; while(p!=NULL | !S.empty()while(p!=NULL) coutdata; /访问根结点S.push(p);p=p-leftChild; /遍历指针进到左子女结点if(!S.empty() /栈不空时退栈p=S.top(); S.pop(); p = p-rightChild; /遍历指针进到右子女结点/-templatevoid InOrder_2(BinTreeNode *p) /非递归中序遍历stackBinTreeNode* S; dowhile(p!=NULL) /遍历指针未到最左下的结点，不空S.push(p); p=p-leftChild; if(!S.empty() /栈不空时退栈p=S.top();S.pop(); coutdata; p=p-rightChild; while(p !=NULL | !S.empty(); /-templatevoid PostOrder_2(BinTreeNode *p) /非递归后序遍历stackBinTreeNode * S;stack tag;/定义一个新的栈用来保存tag域判别根结点的左右子树是否均遍历过while(p != NULL | !S.empty() /左子树经过结点加L进栈while(p!=NULL)S.push(p); /首先将t和tag为0入栈，遍历左子树 tag.push(0);/遍历左子树前的现场保护p=p-leftChild;while( !S.empty() & tag.top()=1)p=S.top();S.pop();tag.pop();coutdata;/最后访问根结点。if( !S.empty()tag.pop();tag.push(1);/遍历右子树前的现场保护,修改栈顶tag为1，遍历右子树p=S.top(); / 取栈顶保存的指针p=p-rightChild;elsebreak;/-templatevoid InOrder_1(BinTreeNode * subTree)/递归函数：中序次序遍历以subTree为根的子树。if(subTree !=NULL) /NULL是递归终止条件InOrder_1(subTree-leftChild); /中序遍历根的左子树coutdata; /访问根结点InOrder_1(subTree-rightChild); /中序遍历根的右子树/-templatevoid PreOrder_1(BinTreeNode * subTree)/递归函数：前序遍历以subTree为根的二叉树。if(subTree !=NULL) /递归结束条件 coutdata;/访问根结点PreOrder_1(subTree-leftChild); /前序遍历根的左子树PreOrder_1(subTree-rightChild); /前序遍历根的右子树/-templatevoid PostOrder_1(BinTreeNode * subTree)/递归函数：后序次序遍历以subTree为根的子树。if(subTree !=NULL) /NULL是递归终止条件PostOrder_1(subTree-leftChild); /后序遍历根的左子树PostOrder_1(subTree-rightChild); /后序遍历根的右子树 coutdata; /访问根结点/-templatevoid CreateBinTree(BinTreeNode * & subTree)/递归方式建立二叉树T item; cinitem;if(item !=-1)subTree = new BinTreeNode();if(subTree = NULL)cerr存储分配错！data = item;CreateBinTree(subTree-leftChild); /递归建立左子树CreateBinTree(subTree-rightChild); /递归建立右子树else subTree = NULL; /封闭指向空子树的指针int main() BinTreeNode * Tree = NULL;cout请输入每个结点，回车确认，并以-1结束：;CreateBinTree(Tree); cout先序遍历二叉树结果：; PreOrder_1(Tree); coutendl;cout中序遍历二叉树结果：;InOrder_1(Tree);coutendl; cout后序遍历二叉树结果：; PostOrder_1(Tree);coutendl;cout非递归前序