二叉树递归非递归遍历.docx

文档介绍：《数据结构》——算法设计
学号：
姓名：
专业班级：
成绩：
评语：
设计1：二叉树遍历
设计要求：
根据二叉树遍历思想，分别实现先序遍历、中序遍历、后序遍历、层次遍历的算法
遍历算法可以尝试使用递归或非递归的方法实现。若需要使用堆栈或队列，请直接使用C++自带的stack和queue对象。
设计分析
（说明自己实现了哪几个算法，对每个算法的设计思想做简单扼要的说明）
建立Tree类
类中的元素有
TreeNode *Root;//树的根节点
bool Find;//查找开关
bool Found;//判断是否找到指定编号的树叶
int pos;//结点数量
ElemType *data;//结点值的数组

（只需要写出核心代码和运行结果，对代码和结果做分析说明）
算法代码：
void Tree::PreOrder(TreeNode *t)//protected先序遍历输出树中所有的值
{
if(t)
{
cout<<t->data;
PreOrder(t->LeftChild);
PreOrder(t->RightChild);
}//if
}//PreOrder
void Tree::PreOrder(bool enter)//public先序遍历
{
PreOrder(Root);
if(enter)cout<<endl;
}//PreOrder
调用代码：
#define ElemType int
int main()
{
ElemType data[9]={1,2,NULL,3,NULL,NULL,4,NULL,NULL};
Tree T1;
TreeNode *t;
(t,5,true,NULL);
(data,9); //根据data和数组长度为9建立二叉树
(5,t); //在编号为5的树结点的左孩子插入数字5
(t,6,true,NULL);
(5,t); //在编号为5的树结点的右孩子插入数字6
(t,9,true,NULL);
(10,t); //在编号为10的树结点的左孩子插入数字9
(true);
return 0;
}
代码分析：
代码的访问顺序：
访问1，输出1；
访问2，输出2；
访问NULL（2的左孩子）；
访问3，输出3；
访问5，输出5；
访问9，输出9；
访问NULL（9的左孩子）；
访问NULL(9的右孩子)；
访问NULL（5的右孩子）；
访问6，输出6；
访问NULL（6的左孩子），访问NULL（6的右孩子）；
访问4，输出4；
访问NULL（4的左孩子），访问NULL（4的右孩子）；
输出
运行结果：

算法代码：
void Tree::Non_Recursive_PreOrder(TreeNode*T) //protected非递归先序遍历
{
/*——————————————————————————
首先进行p的输出。存储的内容基本上是右结点。
遍历左边缘不断输出，然后转到右结点入栈，继续
左边缘不断输出。等到再无左边缘的时候逆向输出
所有右孩子。
———————————————————————————*/
stack<TreeNode*> s;
TreeNode *p=T,*q;
(p);//把Root推入栈内
while(!())//如果s不空
{
cout<<p->data;
q=p->RightChild;
if(q)(q); //如果q(p的右孩子)不空则将q推入栈
p=p->LeftChild;
if(!p) //如果p(p的左孩子)为空则回到(p的右孩子)
{
p=();
();
}//if
}//while
}//Non_recursive_PreOrder
Status Tree::