资源描述：
《非递归算法课程设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、课程设计（论文）任务书题目名称二叉树非递归算法实现学生学部（系）专业班级姓名学号一、课程设计（论文）的内容利用非递归算法实现二叉树的先序、中序和后序遍历二、课程设计（论文）的要求与数据①需求分析②概要设计③详细设计④编程实现⑤测试：提供数个测试用例⑥符合撰写规范设计的必要说明文档三、课程设计（论文）应完成的工作（1）根据要求完成课题；（2）程序书写符合规范，程序设计完善;（3）对程序进行初步的测试；（4）程序运行结果和过程的界面截图；（5）根据设计规范撰写报告并按时提交;（6）设计内容用A4纸打印并按要求装订。四、课程设计（论文）进程安排序号设计（论文）各阶段内容地点起止日期1搜集资料图书
2、馆12.05-12.102需求分析图书馆12.10-12.143概要设计图书馆12.14-5.174详细设计图书馆12.17-12.205程序实现图书馆12.20-12.296系统测试、运行机房12.19-12.307提交报告12.30五、应收集的资料及主要参考文献[1]朱战立•数据结构-使用C语言（第四版）•北京：电子工业出版社，2010.[2]严蔚敏，吴伟民•数据结构[M].北京：清华大学出版社,2002.发出任务书日期：2011年12月12H指导教师签名:目录1序言11.1内容11.2目的12需求分析12.1需求分析12.2功能分析13概要设计23.1设计思想24详细设计25程序实现
3、2参考文献41序言1.1内容对二叉树的遍历过程进行了深入的分析，根据二叉树三种遍历的内在关系给出了求先序序列、中序序列和后序序列的非递归算法。1.2@的该算法只需对二叉树遍历一次即可求出三种遍历序列。2需求分析2.1需求分析先序遍历算法：若二叉树为空，则空操作；否则，(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树。中序遍历算法：若二叉树为空，则空操作；否则，(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右了树。后序遍历算法：若二叉树为空，则空操作；否则，(1)后序遍历右子树；(2)后序遍历左子树;(3)访问根结点。2.2功能分析图1三种遍历示意图3概要设计3.1设计思
4、想要想给出三种遍历算法的非递归程序，就是要设计一个非递归算法，实现从1出发沿虚线进行遍历到2结束的过程。既然这种遍历是一次就能完成的过程，就应该能够写出一个三种遍历的通用的非递归算法。分析上述过程可以发现，只需要设置一个栈，即可一次遍历得到二叉树的三种遍历序列。4详细设计首先,（先序访问根结点A）,A和1进栈（1表示结点A的右子树还未访问），（先序访问A的左子树的根结点B）,B和1进栈，由于B的左子树为空，所以B和1出栈,（中序访问B）,B和0进栈（0表示开始遍历结点B的右子树），由于B的右子树为空,B和0出栈,（后序访问B）,A和1出栈,（中序访问A）,A和0进栈,（先序访问A的右子树的
5、根结点C）,C和1进栈，由于C的左子树为空,C和1出栈,（屮序访问C）,C和0进栈，由于C的右子树为空,C和0出栈,（后序访问C）,A和0出栈,（后序访问A）,此时栈已空，遍历过程结束。5程序实现设二叉树与栈的结构如下（用C语言描述）：typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;typedefstructelemtype{BiTreet;intr;//r用于标志t的右子树是否已遍历，若已遍历为0,否则为1}elemtype;typedefstructArray{chardata;in
6、txh;//xh为1表示此时的data为先序遍历时的元素，xh为2表示此时的data为中序遍历吋的元素，xh为3表示此吋的data为后序遍历时的元素}Array,sequence[Max];//sequence[Max]存放遍历时访问的元素，用xh的值区分各种遍历结果typedefstruct{elemtype*base;elemtype*top;}sqstack;二叉树遍历的通用非递归算法描述如下：(1)初始化栈S;sum=O;(2)for(pt=T;pt;pt=pt->lchild){sequenee[sum].data=pt・>data;〃先序visit(pt・>data)seque
7、nce[sum].xh=1;sum++;pr=1;〃表示pt的右子树还未访问push(S,p);//p进栈}(3)若栈S非空，则{pop(S,p);〃p出栈if(pr==O){-sequence[sum].data=pt->data;〃后序visit(pt・>data)sequence[sum].xh=3;sum++;}else{sequence[sum].data=pt・>data;〃中序visit(pt・>data)
