C++二叉树遍历实验报告
华大计科学院
课程设计说明书
题目： 二叉树的递归和非递归遍历 专业： 计算机科学与技术 班级： 网络工程1班 姓名： 刘群
学号： 1125111023
完成日期： 2012-11
一、设计题目与要求
设计题目：二叉树的遍历
实验要求：
以二叉树表为存储结构，实现二叉树的先、中、后三种次序的递归和非递归遍历。
选作内容
1、借助队列，实现二叉树的层序遍历
2、按凹入表或树形打印所遍历的二叉树
二、算法设计
1.结构体类型
{
T data;
BinTreeNode *lchild,*rchild; //左，右孩子
};
具体程序代码：
#include
#include
using namespace std;
template //生成一个通用数据域类型的模板T
struct BinTreeNode
{
T data;
BinTreeNode *lchild,*rchild; //左，右孩子
// BinTreeNode (T x=T(), BinTreeNode*
BinTreeNode*r=NULL):data(x),lchild(l),rchild(r){};
//可选择参数的构造函数
};
//------------------------------------------------------------------------------ //递归建立二叉树
template
void CreateBinTree(BinTreeNode * & subTree)
{
T item;
cin>>item; //读入二叉树（先序）
if(item !=-1) //用-1表示空树
{ l=NULL,
subTree = new BinTreeNode();
if(subTree == NULL)
{
cout
exit(1);
}
subTree->data = item;
CreateBinTree(subTree->lchild); //递归建立左子树 CreateBinTree(subTree->rchild); //递归建立右子树 }
else subTree = NULL; //封闭指向空子树的指针
}
//---------------------------------------------------------------------------------------------------------
//非递归先序遍历二叉树
template
void PreOrder1 (BinTreeNode *p)
{
stack * > S; //建立栈
while (p!=NULL || !S.empty())
{
while (p!=NULL)
{
coutdata
S.push(p); //p入栈
p=p->lchild; //遍历左孩子结点
}
if(!S.empty()) //栈不空时退栈
{
p=S.top(); //取出栈顶元素
S.pop(); //删除栈顶元素
p=p->rchild; //遍历右孩子结点
}
}
}
//-------------------------------------------------------------------
//非递归中序遍历二叉树
template
void InOrder1(BinTreeNode *p)
{
stack*>S;
do
{
while(p!=NULL) //遍历指针未到最左下结点，为空时结束
{
S.push(p);
p=p->lchild;
}
if(!S.empty()) //遍历
{
p=S.top(); //取出
S.pop(); //删除
coutdata
p=p->rchild;
}
}
while (p!=NULL || !S.empty());
}
//-------------------------------------------------------------------------
//非递归后序遍历二叉树
template
void PostOrder1(BinTreeNode*p)
{
stack *>S;
stacktag; //定义一个新的栈保存tag域判别根结点的左右子树是否均遍历过
while(p!=NULL || !S.empty()) //
{
while(p!=NULL)
{
S.push(p);
tag.push(0); //标记为0（右子树未访问） p=p->lchild;
}
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->rchild;
}
else break;
}
}
//--------------------------------------------------------------------------
//递归中序遍历二叉树
template
void InOrder2(BinTreeNode* subTree)
{
if(subTree !=NULL) //NULL是递归终止条件
{
InOrder2(subTree->lchild); //中序遍历根的左子树
coutdata
InOrder2(subTree->rchild); //中序遍历根的右子树
}
}
//------------------------------------------------------------------------------- //递归先序遍历二叉树
template
void PreOrder2(BinTreeNode * subTree)
{
if(subTree !=NULL) //递归结束条件
{
coutdata
PreOrder2(subTree->lchild); //前序遍历根的左子树 PreOrder2(subTree->rchild); //前序遍历根的右子树 }
}
//-----------------------------------------------------------------------
//递归后序遍历二叉树
template
void PostOrder2(BinTreeNode * subTree)
{
if(subTree !=NULL) //NULL是递归终止条件
{
PostOrder2(subTree->lchild); //后序遍历根的左子树
PostOrder2(subTree->rchild); //后序遍历根的右子树
coutdata
}
}
//----------------------------------------------------------------------
//主函数
main()
{
BinTreeNode*Tree=NULL;
cout
cout
PreOrder1(Tree);
cout
cout
InOrder1(Tree);
cout
cout
PostOrder1(Tree);
cout
cout
PreOrder2(Tree);
cout
cout
InOrder2(Tree);
cout
cout
PostOrder2(Tree);
cout
return 1;
}
三、调试分析
调试过程中出现很多定义上的问题，在做非递归后序遍历时关于标记栈的问题最初不是很清楚，请教了同学后弄好了。二叉树的建立也反复修改，最终还是采用先序递归建立。
四、运行环境
VC6.0
五．用户使用手册
1、打开“BinTree.cpp”
2、编译、组建无误后运行程序（已检测无误）
3、根据提示输入二叉树数据
4、显示结果
5、运行结果无误，按任意键结束运行
六、测试结果截图