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

《C++ 二叉树的创建与遍历实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构集中上机试验报告学院：计算机科学与技术专业：计算机科学与技术学号：班级：姓名：2010/11/26题目：二叉树的创建与遍历一、实验目的1．学会实现二叉树结点结构和对二叉树的基本操作。2．掌握对二叉树每种操作的具体实现，学会利用递归和非递归方法编写对二叉树这种递归数据结构进行处理的算法。二、实验要求1．认真阅读和掌握和本实验相关的教材内容。2．编写完整程序完成下面的实验内容并上机运行。3．整理并上交实验报告。三、实验内容1．编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归和非递归

2、遍历算法(前序、中序、后序)对这棵二叉树进行遍历。四、实验步骤源程序代码#include#includeusingnamespacestd;templatestructBinTreeNode//二叉树结点类定义{Tdata;//数据域BinTreeNode*leftChild,*rightChild;//左子女、右子女域BinTreeNode(Tx=T(),BinTreeNode*l=NULL,BinTreeNode*r=NULL):dat

3、a(x),leftChild(l),rightChild(r){}//可选择参数的默认构造函数};//-------------------------------------------------------------------------templatevoidPreOrder_2(BinTreeNode*p)//非递归前序遍历{stack*>S;while(p!=NULL

4、

5、!S.empty()){while(p!=NULL){cout<

6、>data;//访问根结点S.push(p);p=p->leftChild;//遍历指针进到左子女结点}if(!S.empty())//栈不空时退栈{p=S.top();S.pop();p=p->rightChild;//遍历指针进到右子女结点}}}//----------------------------------------------------------------templatevoidInOrder_2(BinTreeNode*p)//非递归中序遍历{stack

7、nTreeNode*>S;do{while(p!=NULL)//遍历指针未到最左下的结点，不空{S.push(p);p=p->leftChild;}if(!S.empty())//栈不空时退栈{p=S.top();S.pop();cout<data;p=p->rightChild;}}while(p!=NULL

8、

9、!S.empty());}//------------------------------------------------------------------template

10、lassT>voidPostOrder_2(BinTreeNode*p)//非递归后序遍历{stack*>S;stacktag;//定义一个新的栈用来保存tag域判别根结点的左右子树是否均遍历过while(p!=NULL

11、

12、!S.empty())//左子树经过结点加L进栈{while(p!=NULL){S.push(p);//首先将t和tag为0入栈，遍历左子树tag.push(0);//遍历左子树前的现场保护p=p->leftChild;}while(!S.e

13、mpty()&&tag.top()==1){p=S.top();S.pop();tag.pop();cout<data;//最后访问根结点。}if(!S.empty()){tag.pop();tag.push(1);//遍历右子树前的现场保护,修改栈顶tag为1，遍历右子树p=S.top();//取栈顶保存的指针p=p->rightChild;}elsebreak;}}//----------------------------------------------------------------

14、----templatevoidInOrder_1(BinTreeNode*subTree){//递归函数：中序次序遍历以subTree为根的子树。if(subTree!=NULL)//NULL是递归终止条件{InOrder_1(subTree->leftChild);//中序遍历根的左子树cout<data;//访问根结点InOrder_1(subTree->right