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

《数据结构》——算法设计学号: 姓名: 专业班级: 成绩: 评语: 《数据结构》课程 2/ 44 深圳大学制设计 1 :二叉树遍历设计要求: 1. 根据二叉树遍历思想, 分别实现先序遍历、中序遍历、后序遍历、层次遍历的算法 2. 遍历算法可以尝试使用递归或非递归的方法实现。若需要使用堆栈或队列,请直接使用 C++ 自带的 stack 和 queue 对象。设计分析(说明自己实现了哪几个算法,对每个算法的设计思想做简单扼要的说明) 建立 Tree 类类中的元素有 TreeNode *Root; //树的根节点 bool Find;// 查找开关 bool Found;// 判断是否找到指定编号的树叶 int pos; //结点数量 ElemType *data; //结点值的数组算法 1. 先序遍历的递归实现(只需要写出核心代码和运行结果,对代码和结果做分析说明) 算法代码: void Tree::PreOrder(TreeNode *t) //protected 先序遍历输出树中所有的值《数据结构》课程 3/ 44 深圳大学制{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 ); 《数据结构》课程 4/ 44 深圳大学制 return 0; }代码分析: 代码的访问顺序: 访问 1,输出 1; 访问 2,输出 2; 访问 NULL (2的左孩子); 访问 3,输出 3; 访问 5,输出 5; 访问 9,输出 9; 访问 NULL (9的左孩子); 访问 NULL(9 的右孩子); 访问 NULL (5的右孩子); 《数据结构》课程 5/ 44 深圳大学制访问 6,输出 6; 访问 NULL (6的左孩子),访问 NULL (6的右孩子); 访问 4,输出 4; 访问 NULL (4的左孩子),访问 NULL (4的右孩子); 输出 1235964 运行结果: 算法 2. 先序遍历的非递归实现算法代码: void Tree::Non_Recursive_PreOrder(TreeNode*T) //protected 非递归先序遍历{ 《数据结构》课程 6/ 44 深圳大学制/*——————————————————————————首先进行 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 O