非递归算法课程设计

PAGE课程设计（论文）任务书题目名称二叉树非递归算法实现学生学部（系）专业班级姓名学号一、课程设计（论文）的内容利用非递归算法实现二叉树的先序、中序和后序遍历二、课程设计（论文）的要求与数据①需求分析②概要设计③详细设计④编程实现⑤测试:提供数个测试用例⑥符合撰写规范设计的必要说明文档三、课程设计（论文）应完成的工作（1）根据要求完成课题；（2）程序书写符合规范，程序设计完善；（3）对程序进行初步的测试；（4）程序运行结果和过程的界面截图；（5）根据设计规范撰写报告并按时提交；（6）设计内容用A4纸打印并按要求装订。四、课程设计（论文）进程安排序号设计（论文）各阶段内容地点起止日期1搜集资料图书馆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月12日指导教师签名：计划完成日期：2011年12月30日教学单位责任人签章：PAGE5目录1序言 11.1内容……………………………11.2目的12需求分析 ...12.1需求分析 12.2功能分析 13概要设计 23.1设计思想……………………………24详细设计 25程序实现 2参考文献 4

1序言1.1内容对二叉树的遍历过程进行了深入的分析,根据二叉树三种遍历的内在关系给出了求先序序列、中序序列和后序序列的非递归算法。1.2目的该算法只需对二叉树遍历一次即可求出三种遍历序列。2需求分析2.1需求分析先序遍历算法:若二叉树为空,则空操作;否则,(1)访问根结点;(2)先序遍历左子树;(3)先序遍历右子树。中序遍历算法:若二叉树为空,则空操作;否则,(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树。后序遍历算法:若二叉树为空,则空操作;否则,(1)后序遍历右子树;(2)后序遍历左子树;(3)访问根结点。2.2功能分析:3概要设计3.1设计思想要想给出三种遍历算法的非递归程序,就是要设计一个非递归算法,实现从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的右子树的根结点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;intxh;//xh为1表示此时的data为先序遍历时的元素,xh为2表示此时的data为中序遍历时的元素,xh为3表示此时的data为后序遍历时的元素}Array,sequence[Max];//sequence[Max]存放遍历时访问的元素,用xh的值区分各种遍历结果typedefstruct{elemtype*base;elemtype*top;}sqstack;二叉树遍历的通用非递归算法描述如下:(1)初始化栈S;sum=0;(2)for(pt=T;pt;pt=pt->lchild){sequence[sum].data=pt->data;//先序visit(pt->data)sequence[sum].xh=1;sum++;pr=1;//表示pt的右子树还未访问push(S,p);//p进栈}(3)若栈S非空,则{pop(S,p);//p出栈if(pr==0){sequence[sum].data=pt->data;//后序visit(pt->data)sequence[sum].xh=3;sum++;}else{sequence[sum].data=pt->data;//中序visit(pt->data)sequence[sum].xh=2;sum++;pr=0;//表示开始访问pt的右子树push(S,p);//p进栈for(pt=pt->rchild;pt;pt=pt->lchild){sequence[sum].data=pt->data;//先序visit(pt->data)sequence[sum].xh=1;sum++;pr=1;push(S,p)}}}图2总结“数据结构”是计算机类各专业的核心课程。通过学习这门课，对于我的逻辑思维培养和程序设计思想体系的建立有着重要的影响。在调试过程中，碰到诸多问题，比如时间复杂度的长度、定义表长过小、处理记录数量错误时程序的异常，调试时的语法错误等等。处在不断调试，询问老师,和同学探讨之后，终于解决，运行成功。参考文献[1]朱战立.数据结构-使用C语言（第四版）.北京：电子工业出版社，2010.[2]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,2002.[3]广树建.新编C/C++程序设计教程.广州：华南理工出版社，2008[4]陈玉坤,计元.以问题结构为基础的递归程序设计[J].小型微型计算机系统,2001.[5]张文祥,杨兆楠.递归程序的非递化算法[J].煤炭技术,2003(22).心得体会经过“数据结构”的学习和这次课程设计，使我对C语言的各种法有了更加深刻的了解和认识。以前长辈给我们说，学习知识才是你们以后好的生活的保证，我总是不以为然，觉得没有知识，也是可以很好的生活，也就边玩边学，可是通过这次课程设计，我认识到，没有扎实的知识做基础，很难完成很多工作。在这个科技高级发达的社会，没有知识是行不通的。在这次非递归算法的课程设计当中，我们可以深刻体会到“数字结构”里面严谨的逻辑运算，并对C语言有了更深程度的一个理解。这个程序的主要功能就是在非递归的算法下实现先、中、后序的遍历。从中加深对树的理解。2011年12月29日教师评语2012年01月05日成绩