文档介绍：------------------------------------校验:_____________--------------------------------日期:_____________湖南文理学院课程设计报告湖南文理学院课程设计报告课程名称:计算机基础课程设计系部:电气工程系专业班级:D05201学生姓名:丁纯指导教师:曹玲玲完成时间:2006年9月28日报告成绩:评阅意见:评阅教师日期目录计题目及要求……………………………………………1二、设计的作用目的……………………………………………三、具体设计……………………………………………问题及解决方法……………………………………………心得体会……………………………………………参考文献…………………………………………课程设计报告计题目及要求设计题目——二叉树遍历演示要求:收集资料,全面分析课题,分解问题,形成整体编程思路;深入分析各个小问题,编写各部分程序模块;对于设计中用到的关键函数,要联系问题进行具体介绍;上机调试,确保程序能正确运行;完成设计报告,并进行答辩。二、设计的作用目的通过本项课程设计,培养学生独立思考、综合运用所学有关相应知识的能力,使学生巩固《C语言程序设计》课程学****的内容,掌握工程软件设计的基本方法,强化上机动手编程能力,闯过理论与实践相结合的难关;为了培养学生综合运用所学知识、独立分析和解决实际问题的能力,培养创意识和创新能力,使学生获得科学研究的基础训练。为后续各门计算机课程的学****和毕业设计打下坚实基础。同时,可以利用这次机会来检验自己的c语言水平,提高自己的写作水平,锻炼自己的动手能力。三、:⑴二叉树的递归定义:二叉树(BinaryTree)是n(n≥0)个结点的有限集,它或者是空集(n=0),或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成。⑵二叉树的五种基本形态二叉树可以是空集;根可以有空的左子树或右子树;或者左、右子树皆为空。二叉树的五种基本形态如下图所示。 ⑶二叉树不是树的特例①二叉树与无序树不同:二叉树中,每个结点最多只能有两棵子树,并且有左右之分。二叉树并非是树的特殊情形,它们是两种不同的数据结构。②二叉树与度数为2的有序树不同:在有序树中,虽然一个结点的孩子之间是有左右次序的,但是若该结点只有一个孩子,就无须区分其左右次序。而在二叉树中,即使是一个孩子也有左右之分。 【例】下图中(a)和(b)是两棵不同的二叉树,它们同右图中的普通树(作为有序树或无序树)很相似,但却不等同于这棵普通树。若将这三棵树均看做普通树,则它们就是相同的了。⑷二叉树的遍历:二叉树是数据结构中一种非常重要的非线形结构。二叉树的一个重要运算是按深度遍历二叉树,即前序遍历和后序遍历。用程序实现图形演示这三种遍历二叉树的过程。二叉树是一种特殊的树,这种特殊不仅仅在于其分支最多为2以及其它特征,一个最重要的特殊之处是在于:二叉树是有序的!即:二叉树的左右孩子是不可交换的,如果交换了就成了另外一棵二叉树,这样交换之后的二叉树与原二叉树我们认为是不相同的两棵二叉树。但是,对于普通的双分支树而言,不具有这种性质。二叉树的遍历算法有三种:先序,中序和后序。其划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握三种遍历的递归算法,理解其执行的实际步骤,并且应该熟练掌握三种遍历的非递归算法。由于二叉树一章的很多算法,可以直接根据三种递归算法改造而来(比如:求叶子个数),所以,掌握了三种遍历的非递归算法后,对付诸如:“利用非递归算法求二叉树叶子个数”这样的题目就下笔如有神了。:⑴遍历方案:从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:①访问结点本身(N),②遍历该结点的左子树(L),③遍历该结点的右子树(R)。以上三种操作有六种执行次序:NLR、LNR、LRN、NRL、RNL、RLN。注意:前三种次序与后三种次序对称,故只讨论先左后右的前三种次序。⑵三种遍历的命名:根据访问结点操作发生位置命名:①NLR:前序遍历(PreorderTraversal亦称(先序遍历))——访问结点的操作发生在遍历其左右子树之前。②LNR:中序遍历(InorderTraversal)——访问结点的操作发生在遍历其左右子树之中(间)。③LRN:后序遍历(PostorderTraversal)——访问结点的操作发生在遍历其左右子树之后。注意:由于被访问的结点必是某子树的根,所以N(Node)、L(Leftsubtlee)和R(Rightsubtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和