二叉树递归非递归遍历.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的右孩子);
输出1235964
运行结果:

算法代码:
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::Non_Recursive_PreOrder(bool enter)//非递归先序遍历
{
Non_Recursive_PreOrder(Root);
if(enter)cout<<endl;
return OK;
}//Non_r