数据结构课程设计-二叉树的遍历算法集成.doc

安徽理工大学数据结构课程设计说明书题目:二叉树的遍历算法集成院系:计算机科学与工程学院专业班级:学号:学生姓名:指导教师:2010年1月11日安徽理工大学课程设计(论文)任务书计算机科学与工程学院计算机软件教研室学号2008303003学生姓名刘威专业(班级)信息08-1设计题目二叉树的遍历算法集成设计技术参数系统平台:WindowsXP开发工具:VC++(1)界面友好,易于操作。可采用菜单或其它人机对话方式进行选择(2)实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归或非递归算法。(3)要求能查找任一结点在某种遍历序列中的前驱和后继。(4)演示程序以人机对话的形式进行。每次测试完毕正确显示各种遍历序列。工作量课程设计报告要求不少于3000字。源程序要求不少于300行工作计划12月14日-12月16日查找相关资料12月18日-12月21日思考相关问题12月22日-12月28日设计算法12月29日-1月05日编写代码1月06日-1月09日撰写课程设计报告参考资料[1](C语言版).合肥:中国科学技术大学出版社,2007[2]++:清华大学出版社2006[3]:高等教育出版社,2008指导教师签字教研室主任签字2009年11月16日学生姓名:刘威学号:2008303003专业班级:信息08-1课程设计题目:二叉树的遍历算法集成指导教师评语:成绩:指导教师:年月日安徽理工大学课程设计(论文)成绩评定表目录1、需求分析 12、概要设计 33、详细设计 184、总结 18参考文献 191、需求分析数据结构是计算机、信息管理、信息与计算机科学等信息类专业最重要的专业基础课程,掌握好数据结构的知识将直接关系到后续专业课程的学****数据结构只要研究四个方面的问题:(1)数据的逻辑结构,即数据之间的逻辑关系;(2)数据的物理结构,即数据在计算机内的存储方式;(3)对数据的加工,即基于某种存储方式的操作算法;(4)算法的分析;即评价算法的优劣。本实验是用链式存储结构来存储二叉树并进行一系列的算法,且结点内容的数据类型为字符型。本程序用VC++,可以实现各种二叉树的遍历。包括先序遍历、中序遍历、后序遍历的递归算法,先序遍历、中序遍历、后序遍历的非递归算法以及能查找任一结点在某种遍历序列中的前驱和后继。根据题目知,程序主要是根据给定二叉树的先序遍历结果,构造出二叉树并输出按中,后序遍历的结果,以及求二叉树的叶子个数等。其中二叉树的结点用字符表示。(1)先创建二叉树:按先序次序输入,构造二叉链表表示的二叉树。(2)设计算法:先序遍历,中序遍历,,应注意算法如下:根结点入队,队头元素出队,左孩子不为空入队右孩子不为空入队的顺序进行。(3)可以加入求二叉树的深度二叉树的叶子数二叉树的结点总数等一些简单的算法。(4)设计main()函数调用以上步骤实现相关功能。2、(1)typedefstructBTNode定义一个用链式存储结构存储的二叉树,其中包括左孩子和右孩子以及数据元素的内容。和单链表类似,一个二叉链表由头指针唯一确定,若二叉树为空,则头指针指向空。并且结点内容的数据类型为字符型。(2)CreateBiTree(BiTree&T)此函数的功能是构建二叉树。从键盘上按先序次序输入字符构造二叉链表表示的二叉树T,其中用星号表示空树。(3)NRPreOrder(BiTreebt)此函数的功能是用非递归的方法实现二叉树的先序遍历算法。调用此函数可以获得二叉树的非递归的先序遍历的结果。(4)NRInOrder(BiTreebt)此函数的功能是用非递归的方法实现二叉树的中序遍历算法。调用此函数可以获得二叉树的非递归的中序遍历的结果。(5)NRPostOrder(BiTreebt)此函数的功能是用非递归的方法实现二叉树的后序遍历算法。调用此函数可以获得二叉树的非递归的后序遍历的结果。其中bt是要遍历树的根指针,后序遍历要求在遍历完左右子树后,再访问根。需要判断根结点的左右子树是否均遍历过。可采用标记法,结点入栈时,配一个标志tag一同入栈1:遍历左子树的现场保护,2:遍历右子树前的现场保护。首先将bt和tag(为1)入栈,遍历左子树;返回后,修改栈顶tag为2,遍历右子树;最后访问根结点。(6)PreOrderTraverse(BiTreeT)函数功能是用递归的方法对二叉树进行先序遍历,调用此函数可以获得二叉树的递归的先序遍历的结果。(7)InOr