二叉树遍历演示

课程设计报告课程名称数据结构课题名称二叉树遍历演示专业计算机班级1202学号34姓名贺义君指导教师陈淑红李珍辉李杰君2014年6月16日湖南工程学院课程设计任务书课程名称数据结构课题二叉树遍历演示专业班级计算机1202学生姓名贺义君学号34指导老师陈淑红李珍辉李杰君审批任务书下达日期2014年6月16日任务完成日期2014年6月29日课程设计报告任务书1设计内容与设计要求1.1设计内容1.1.1算术24游戏演示由系统随机生成4张扑克牌，用户利用扑克牌的数字及运算符号“+”、“—”、“*”、“/”及括号“（”和“）”从键盘上输入一个计算表达式，系统运行后得出计算结果，如果结果等于24，则显示“Congratulation!”，否则显示“Incorrect!”设计思路：从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达式，利用后缀表达式求值。1.1.2迷宫探索随机生成一个迷宫图，迷宫大小为N*N，N预定义为常数，修改N的值可以改变迷宫的大小。用白色表示可走的路，蓝色表示墙壁不可以通过。系统设计两种运行方式：一种是系统自动探索（用递归方法实现）；另一种是由人工操作探索通路。设计思路：程序首先要考虑迷宫的表示，这是一个二维关系图，所以可选择二维数组来存储。数组元素只有两种值0和1，分别代表通路和墙壁。图形的显示可以根据数组元素的值来确定。如果是人工探索，则依据按键来确定探索物的位置坐标，利用循环语句实现。如果是系统自动探索，可采用递归算法实现。1.1.3二叉树遍历演示演示遍历二叉树的过程，所以首先建立二叉树，并用图形显示出树的形状。建立的过程是采用前序便利的方法来创建，设计两种生成树的方式：一种是系统随机生成，另一种是人工输入。考虑到屏幕界面的有限性，限定二叉树不超过5层，最多26个字符，输入字符小数点“.”代表NULL。初始树为某种颜色的结点，三种情况的遍历采用填充另外一种醒目的颜色，来表示当前遍历的结点，同时显示该结点的访问序号。同时在遍历的过程中在遍历图形的下方显示出遍历序列。1.1.4拓扑排序演示演示拓扑排序的过程。按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。要求每输出一个顶点后就演示从图中删去此顶点以及所有以它为尾的弧。1.1.5图的遍历演示图的深度优先,广度优先遍历过程，并输出原图结构及遍历结果。要求图的结点数不能少于6个。可以由系统随机生成图，也可以由用户手动输入图。报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一步改进图的效果。1.1.6双链表创建演示建立一个递增有序的双链表。功能是随机生成8个结点数据，每生成一个结点则申请空间得到一个指针，将数据存放到指针所指的数据域中，然后将结点插入到已经排好序的双链表中。所以第一步工作是判断新结点的插入位置，第二演示插入过程中指针的变化，第三步显示插入后的链表结果。1.1.7公园导游图给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。要求用图示展示最佳路径。1.1.8最小生成树算法演示随机生成一个网，并用图形展示，然后依据Prim算法或Kruskal算法求该图的最小生成树，并用图形展示相应的过程步骤。1.2选题方案：所选题目根据学号确定，学号模8加1，即（学号%8+1）。如你的学号为13，则所选题目号为：13%8+1＝（题目6）。注意，所有的课题都要求用图形方式演示步骤和结果。1.3设计要求：1.3.1课程设计报告规范（1）需求分析a.程序的功能。b.输入输出的要求。（2）概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。（3）详细设计a.采用C语言定义相关的数据类型。b.写出各模块的类C码算法。c.画出各函数的调用关系图、主要函数的流程图。（4）调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b.程序调试中遇到的问题以及解决问题的方法。c.课程设计过程经验教训、心得体会。（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。（6）书写格式a.设计报告要求用A4纸打印成册：b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。（7）附录a.源程序清单（带注释）1.3.2考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：（1）平时出勤（占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。（5）独立完成情况（占10%）。1.3.3课程验收要求（1）运行所设计的系统。（2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。2进度安排第17周：星期一8：00——12：00上课星期二14：00——18：00上机星期三14：00——18：00上机星期四14：00——18：00上机第18周：星期一14：00——18：00上机星期二14：00——18：00上机星期四14：00——18：00上机目录1.需求分析1.1功能需求分析..............................................11.2输入输出的要求............................................12.概要设计2.1数据结构类型..............................................22.2抽象数据类型..............................................22.3功能模块图................................................33.详细设计3.1设计思路..................................................43.2流程图....................................................74.程序调试4.1调试分析.................................................114.2测试结果分析.............................................125.总结.........................................................186.使用说明.....................................................197.参考文献.....................................................208.附录.........................................................211课程设计报告1.需求分析1.1功能需求分析演示遍历二叉树的过程，所以首先建立二叉树，并用图形显示出树的形状。建立的过程是采用前序便利的方法来创建，设计两种生成树的方式：一种是系统随机生成，另一种是人工输入。考虑到屏幕界面的有限性，限定二叉树不超过5层，最多26个字符，输入字符小数点“.”代表NULL。初始树为某种颜色的结点，三种情况的遍历采用填充另外一种醒目的颜色，来表示当前遍历的结点，同时显示该结点的访问序号。同时在遍历的过程中在遍历图形的下方显示出遍历序列。1.2输入输出要求1.2.1输入要求(1)人工输入二叉树的序列。(2)随机产生二叉树的序列。1.2.2输出要求用图形的方式演示二叉树的三种遍历：先序遍历，中序遍历，后序遍历。三种遍历采用不同的颜色来填充，同时显示该结点的访问序号。22.概要设计2.1数据结构类型typedefstructnode{chardata;structnode*lchild;structnode*rchild;intx;inty;intnum;}BTNode;2.2抽象数据类型数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可惟一标识数据元素的关键字。数据关系R：数据元素同属一个集合。基本操作P：structnode*CreatBT(BTNode*&t,char*str)操作结果：创建二叉树。PreOrder(BTNode*t,intm,intv)初始条件：二叉树存在；操作结果：先序遍历二叉树。InOrder(BTNode*t,intm,intv)初始条件：二叉树存在；操作结果：中序遍历二叉树。PostOrder(BTNode*t,intw,intv)初始条件：二叉树存在；操作结果：后序遍历二叉树。structnode*DrawBTree(BTNode*t,char*str,intx,inty)初始条件：二叉树存在；操作结果：将二叉树用图形表示出来。3RgCreate()操作结果：人工输入二叉树序列。SjCreate()操作结果：随机生成二叉树序列。2.3功能模块图2.3.1程序模块：用户在主界面中选择功能模块，根据用户的选择，继续执行小界面中的其他模块。图2.1功能模块图2.3.2函数功能说明：主界面：main()用户选择界面人工输入模块：RgCreate()用户手动输入二叉树序列随机生成模块：SjCreate()系统随机产生二叉树序列先序遍历模块：PreOrder()二叉树的先序遍历中序遍历模块：InOrder()二叉树的中序遍历后序遍历模块：PostOrder()二叉树的后序遍历菜单函数：menu()提示用户选择遍历的方式主界面1、人工输入2、随机生成1、先序遍历2、中序遍历3、后序遍历3、退出用户提示界面43.详细设计3.1设计思路3.1.1创建二叉树创建二叉树时，用ch扫描str，有四种字符：1、ch='(':表示前面刚创建的节点*p存在孩子节点，需要将其进栈，以便建立它和其孩子节点的关系，然后开始处理左孩子，k=1，其后创建的节点作为它的左孩子节点。2、ch=')':表示创建完毕，将其退栈。3、ch=',':开始处理栈顶节点的右孩子结点。3.1.2先序遍历二叉树先序遍历过程是先访问根节点，在访问左子树，最后才是右子树。因此，先将根节点进栈，在栈不空的情况下循环：出栈p,访问*p节点，若其右孩子结点不空将右孩子节点进栈，若其左孩子节点不空再将其左孩子节点进栈。3.1.3中序遍历二叉树：中序遍历过程是先访问二叉树的最左下方节点，其基本思路是先找到二叉树的开始节点，将其访问，再处理其右子树。用指针指向当前要处理的节点。先扫描根节点的所有左节点，并将它们一一进栈，当无左节点时表示栈顶节点无左子树，然后出栈这个节点，并访问，将p指向刚出栈节点的右孩子，对右子树进行同样的处理。如此重复操作，直到栈空为止。3.1.4后序遍历二叉树：后序遍历过程是先访问左子树，然后访问右子树，最后访问根节点。采用一个栈保存需要返回的节点指针，先扫描根节点的所有左孩子节点并一一进栈，出栈一个节点*t作为当前节点,然后扫描该节点的右子树。当一个节点的左右子树节点均访问后再访问该节点，如此重复操作，直到栈空为止。3.1.5人工输入二叉树的算法演示：voidRgCreate()//人工输入{chars[100];char*