二叉树遍历演示

1、课 程 设 计 报 告课程名称 数据结构 课题名称 二叉树遍历演示 专 业 计算机 班 级 1202 学 号 34 姓 名 贺 义 君 指导教师 陈淑红 李珍辉 李杰君 2014年 6 月 16 日湖南工程学院课 程 设 计 任 务 书课程名称 数据结构 课 题 二叉树遍历演示 专业班级 计算机1202 学生姓名 贺义君 学 号 34 指导老师 陈淑红 李珍辉 李杰君 审 批 任务书下达日期 2014 年 6 月 16 日任务完成日期 2014年 6 月 29 日课程设计报告任务书1设计内容与设计要求1.1设计内容1.1.1 算术24游戏演示由系统随机生成4张扑克牌，用户利用扑克牌的数字及运算

2、符号“+”、“”、“*”、“/”及括号“（”和“）”从键盘上输入一个计算表达式，系统运行后得出计算结果，如果结果等于24，则显示“Congratulation!”，否则显示“Incorrect!”设计思路：从键盘输入中缀表达式，然后将中缀表达式转换为后缀表达式，利用后缀表达式求值。1.1.2 迷宫探索随机生成一个迷宫图，迷宫大小为N*N，N预定义为常数，修改N的值可以改变迷宫的大小。用白色表示可走的路，蓝色表示墙壁不可以通过。系统设计两种运行方式：一种是系统自动探索（用递归方法实现）；另一种是由人工操作探索通路。设计思路：程序首先要考虑迷宫的表示，这是一个二维关系图，所以可选择二维数组来存储。

3、数组元素只有两种值0和1，分别代表通路和墙壁。图形的显示可以根据数组元素的值来确定。如果是人工探索，则依据按键来确定探索物的位置坐标，利用循环语句实现。如果是系统自动探索，可采用递归算法实现。1.1.3 二叉树遍历演示演示遍历二叉树的过程，所以首先建立二叉树，并用图形显示出树的形状。建立的过程是采用前序便利的方法来创建，设计两种生成树的方式：一种是系统随机生成，另一种是人工输入。考虑到屏幕界面的有限性，限定二叉树不超过5层，最多26个字符，输入字符小数点“.”代表NULL。初始树为某种颜色的结点，三种情况的遍历采用填充另外一种醒目的颜色，来表示当前遍历的结点，同时显示该结点的访问序号。同时在遍

4、历的过程中在遍历图形的下方显示出遍历序列。1.1.4 拓扑排序演示演示拓扑排序的过程。按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。要求每输出一个顶点后就演示从图中删去此顶点以及所有以它为尾的弧。1.1.5 图的遍历演示图的深度优先, 广度优先遍历过程，并输出原图结构及遍历结果。要求图的结点数不能少于6个。可以由系统随机生成图，也可以由用户手动输入图。报告中要写出画图的思路；画出图的结构，有兴趣的同学可以进一步改进图的效果。1.1.6 双链表创建演示建立一个递增有序的双链表。功能是随机生成8个结点数据，每生成一个结点则申

5、请空间得到一个指针，将数据存放到指针所指的数据域中，然后将结点插入到已经排好序的双链表中。所以第一步工作是判断新结点的插入位置，第二演示插入过程中指针的变化，第三步显示插入后的链表结果。1.1.7公园导游图给出一张某公园的导游图，游客通过终端询问可知：从某一景点到另一景点的最短路径。游客从公园大门进入，选一条最佳路线，使游客可以不重复地游览各景点，最后回到出口（出口就在入口旁边）。要求用图示展示最佳路径。1.1.8 最小生成树算法演示随机生成一个网，并用图形展示，然后依据Prim算法或Kruskal算法求该图的最小生成树，并用图形展示相应的过程步骤。1.2 选题方案：所选题目根据学号确定，学号

6、模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. 测试数据

7、：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。b. 程序调试中遇到的问题以及解决问题的方法。c. 课程设计过程经验教训、心得体会。（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。 （6）书写格式a. 设计报告要求用A4纸打印成册：b. 一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。（7）附录a. 源程序清单（带注释）1.3.2 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设

8、计成绩。具体考核标准包含以下几个部分：（1）平时出勤 （占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。（5）独立完成情况（占10%）。1.3.3 课程验收要求（1）运行所设计的系统。（2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。2 进度安排第 17 周：星期一 8：0012：00上课 星期二14：00

9、18：00 上机 星期三14：0018：00上机 星期四 14：0018：00上机第 18 周：星期一14：0018：00上机 星期二 14：0018：00 上机 星期四 14：0018：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.附录.21课程设计报告1.需求分析1.1功能需求分析演示遍历二叉树的过程，所以首先建立二叉树，并用图

10、形显示出树的形状。建立的过程是采用前序便利的方法来创建，设计两种生成树的方式：一种是系统随机生成，另一种是人工输入。考虑到屏幕界面的有限性，限定二叉树不超过5层，最多26个字符，输入字符小数点“.”代表NULL。初始树为某种颜色的结点，三种情况的遍历采用填充另外一种醒目的颜色，来表示当前遍历的结点，同时显示该结点的访问序号。同时在遍历的过程中在遍历图形的下方显示出遍历序列。1.2输入输出要求 1.2.1输入要求 (1)人工输入二叉树的序列。 (2)随机产生二叉树的序列。 1.2.2输出要求用图形的方式演示二叉树的三种遍历：先序遍历，中序遍历，后序遍历。三种遍历采用不同的颜色来填充，同时显示该结

11、点的访问序号。2. 概要设计2.1数据结构类型typedef struct nodechar data;struct node *lchild;struct node *rchild;int x; int y;int num;BTNode;2.2抽象数据类型数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可惟一标识数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： struct node *CreatBT(BTNode *&t,char *str) 操作结果：创建二叉树。 PreOrder(BTNode *t,int m,int v) 初始条

12、件：二叉树存在； 操作结果：先序遍历二叉树。 InOrder(BTNode *t,int m,int v) 初始条件：二叉树存在； 操作结果：中序遍历二叉树。 PostOrder(BTNode *t,int w,int v) 初始条件：二叉树存在； 操作结果：后序遍历二叉树。 struct node *DrawBTree(BTNode *t,char *str,int x,int y) 初始条件：二叉树存在； 操作结果：将二叉树用图形表示出来。 RgCreate() 操作结果：人工输入二叉树序列。 SjCreate() 操作结果：随机生成二叉树序列。2.3功能模块图2.3.1程序模块：用户在主

13、界面中选择功能模块，根据用户的选择，继续执行小界面中的其他模块。 主界面 1、人工输入 3、退出 2、随机生成 用户提示界面3、后序遍历2、中序遍历1、先序遍历图2.1功能模块图2.3.2函数功能说明：主界面：main() 用户选择界面 人工输入模块：RgCreate() 用户手动输入二叉树序列 随机生成模块：SjCreate() 系统随机产生二叉树序列 先序遍历模块：PreOrder()二叉树的先序遍历 中序遍历模块：InOrder()二叉树的中序遍历 后序遍历模块：PostOrder()二叉树的后序遍历 菜单函数：menu()提示用户选择遍历的方式3. 详细设计3.1设计思路3.1.1创建

14、二叉树 创建二叉树时，用ch扫描str，有四种字符：1、ch='(':表示前面刚创建的节点*p存在孩子节点，需要将其进栈，以便建立它和其孩子节点的关系，然后开始处理左孩子，k=1，其后创建的节点作为它的左孩子节点。2、ch=')':表示创建完毕，将其退栈。3、ch=',':开始处理栈顶节点的右孩子结点。3.1.2先序遍历二叉树 先序遍历过程是先访问根节点，在访问左子树，最后才是右子树。因此，先将根节点进栈，在栈不空的情况下循环：出栈p,访问*p节点，若其右孩子结点不空将右孩子节点进栈，若其左孩子节点不空再将其左孩子节点进栈。3.1.3中序遍历二叉

15、树： 中序遍历过程是先访问二叉树的最左下方节点，其基本思路是先找到二叉树的开始节点，将其访问，再处理其右子树。用指针指向当前要处理的节点。先扫描根节点的所有左节点，并将它们一一进栈，当无左节点时表示栈顶节点无左子树，然后出栈这个节点，并访问，将p指向刚出栈节点的右孩子，对右子树进行同样的处理。如此重复操作，直到栈空为止。3.1.4后序遍历二叉树： 后序遍历过程是先访问左子树，然后访问右子树，最后访问根节点。采用一个栈保存需要返回的节点指针，先扫描根节点的所有左孩子节点并一一进栈，出栈一个节点*t作为当前节点,然后扫描该节点的右子树。当一个节点的左右子树节点均访问后再访问该节点，如此重复操作，直

16、到栈空为止。3.1.5人工输入二叉树的算法演示：void RgCreate() /人工输入char s100;char *str,tmp,ti100; InputBox(ti,100 ,"请输入节点表达式:");sscanf(ti,"%s",&s);str=s;BTNode *h,*t;h=CreatBT(h,str);initgraph(800,600);setcolor(RED);setbkcolor(BLACK);cleardevice();t=DrawBTree(h,str,400,20);loop:menu(h); InputBox(t

17、i,100,"-继续吗?n-继续请输入1n-退出请输入2");sscanf(ti,"%c",&tmp);if(tmp='1') goto loop; if(tmp='2')close();elseInputBox(ti,100,"输入错误,请重新输入n-继续吗?n-继续请输入1n-退出请输入2n");sscanf(ti,"%c",&tmp);if(tmp='1') goto loop; if(tmp='2')close();3.1.6随

18、机生成二叉树算法演示：void SjCreate() /随机生成int tem10;char a,b,c,d,e,f,g,h,i,j,I;char si100,tmp,ti100;char *str;BTNode *k,*t; srand(time(NULL);for(I=0;I<10;I+)temI=(rand()%26+65);a=tem0;b=tem1;c=tem2;d=tem3;e=tem4; f=tem5;g=tem6;h=tem7;i=tem8;j=tem9;si0=a;si1='('si2=b;si3='('si4=d;si5='(&

19、#39;si6=j;si7=','si8=h; si9=')'si10=','si11=e;si12='('si13=i;si14=','si15=')'si16=')'si17=','si18=c;si19='('si20=f;si21=','si22=g;si23=')'si24=')'str=si;k=CreatBT(k,str);initgraph(800,600);setcolor(RED);s

20、etbkcolor(BLACK);cleardevice();t=DrawBTree(k,str,400,20);loop:menu(k); InputBox(ti,100,"-继续吗?n-继续请输入1n-退出请输入2");sscanf(ti,"%c",&tmp);if(tmp='1') goto loop; if(tmp='2')close();elseInputBox(ti,100,"输入错误,请重新输入n-继续吗?n-继续请输入1n-退出请输入2n");sscanf(ti,"%c

21、",&tmp);if(tmp='1') goto loop; if(tmp='2')close();3.2流程图3.2.1创建二叉树流程图： 开始int top=-1,k,j=0;char ch;t=NULL;ch=*str; ch!='0' 结束 return t; str+;ch=*str;case1:sttop->lchild=p;case2:sttop->rchild=p;default:p=(BTNode*)malloc(sizeof(BTNode);p->lchild=p->rchild=NU

22、LL;p->data=chcase ',': k=2;case ')': top-; t=p;case(':top+;sttop=p;k=1;NOYES t=NULLYESNO 图3.1二叉树的创建流程图 3.2.2先序遍历流程图： 开始int i=0,x=90,x1,x2,y1,y2; char ch;int top=-1,c,w,d; t!=NULL NO YES top+; sttop=t; top>-1NO YES p=sttop;top-;ch=p->data;i+; p->rchild!=NULL top+; stto

23、p=p->rchild; p->lchild!=NULL top+;sttop=p->lchild; 结束 图3.2先序遍历流程图3.2.3中序遍历流程图： 开始 int top=-1; b!=NULL? NO top>-1 YEStop>-1|p!=NULLp=sttop;top-;p=p->rchild;printf("%c",p->data);p=p->rchild;printf("%c",p->data);p=p->rchild;top+;sttop=p;p=p->lchild;

24、结束 图3.3中序遍历流程图 开始 3.2.4后序遍历：int flag,top=-1;char ch; NO t!=NULL YES top+;sttop=t; YES NO t->lchild!=NULL YES t=t->lchild; p=NULL;flag=1; NO top!=-1&&flag flag t=sttop; t->rchild=p;p YES NO t->rchild!=NULL;ch=t->data;i+;top-;p=t; NO t=t->rchild;flag=0; top!=-1 YES 结束 图3.4后序遍

25、历流程图4.程序调试4.1调试分析 开始调试程序时，遇到的问题主要是不会用程序语言清楚的表达出自己的意思，而且思路也不是特别的清晰，虽然能了解二叉树的一些基本算法，但是对这些基本算法的图形的表示却不是很了解，所以导致编写的程序总是不能达到预期的效果，就比如说在中序遍历二叉树的序列演示时，所显示的界面位置就不是很准确，在源代码的中序遍历模块中通过调整其坐标将界面位置改了过来，而且最初在图形演示二叉树的遍历时，每进行完一次访问，程序会自动退出，因此程序的遍历的演示就不连贯，而且也不方便。于是，我就在人工输入和随机生成模块里设立了一个“继续/返回”提示，当输入“1”时，继续二叉树的遍历，当输入“2”

26、时，返回到主界面。虽然程序不是特别的完美，存在一些不尽如人意的小地方，比如：随机生成的二叉树的树形是固定的，人为控制产生的树形，并且有些算法是直接从课本里弄下来的，但是通过调整解决了一些问题，还是特别的有成就感。4.2测试结果分析首先运行程序，进入到主界面，如图4.1所示： 图4.1 系统主界面根据主界面的提示，输入序号1、人工输入，2、随机生成，3、退出；按序号1进入人工输入界面，根据提示，输入要创建的二叉树序列，并按Enter键进入图形输出界面，如图4.2，图4.3所示： 图4.2人工输入数据 4.3人工输入二叉树序列显示树形根据提示，输入序号1、先序遍历，2、中序遍历，3、后序遍历；按序

27、号1进入人工输入二叉树的先序遍历，按Enter键进入界面，如图4.4所示： 4.4人工输入的先序遍历 根据提示，继续则输入“1”,若退回主界面则按“2”,并按Enter键进入下一界面。继续输入“1”，返回到三种遍历提示界面，选择中序遍历，显示中序遍历的界面，如图4.5所示；选择后序遍历，显示后序遍历的界面如图4.6所示。 4.5人工输入的中序遍历 4.6人工输入的后序遍历根据提示，继续则输入“1”,若退回主界面则按“2”,并按Enter键进入下一界面。返回主界面时，选择主界面序号2、随机生成二叉树，如图4.7所示： 图4.7随机生成二叉树选择“1”，并按Enter键进入先序遍历二叉树界面，如图

28、4.8所示；选择“2”，并按Enter键进入中序遍历二叉树界面，如图4.9所示；选择“3”，并按Enter键进入后序遍历二叉树界面，如图4.10所示； 4.8随机生成树的先序遍历 4.9随机生成树的中序遍历 4.10随机生成树的后序遍历根据提示，继续则输入“1”,若退回主界面则按“2”,并按Enter键进入下一界面。返回主界面时，选择“3”，退出主界面，如图4.11所示： 图4.11退出程序 5. 总结本次课程设计我做的是二叉树遍历演示，这次的课程设计和以往的实验有很大的差别，无论是EasyX的使用,还是图形的表示方法，都是我们从来没有接触过的知识，对于C语言、数据结构算法的要求就更高了，像二

29、叉树的三种遍历，因为在课堂上都已经讲过，所以就不是那么的陌生，在编写程序的时候就比较顺手。但是，当二叉树的三种遍历加入了图形的演示的时候，很多地方就变得复杂，像需要设置树节点的坐标，填充树节点的颜色，画线，画圆,需要在遍历的同时输出该结点的访问序号等等一些比较复杂的问题。有时候可能思路是对的，但就是无法用程序语言表达出来。而有的时候，甚至连思路都没有，不知道从哪儿入手，让人很头痛。本次实验，对我来说是一个巨大的挑战，但又让我进一步了解了C的相关知识，甚至让我第一次感觉到程序是个特别好玩而且神奇的东西，可能是因为每次接触到的都是相对比较死板的东西，程序表达的功能性也没有那么的强，不是像这次一样的

30、程序的直观演示。而本次的实验，就比如课程设计中运用到的随机生成二叉树、图形的演示二叉树的遍历等等都让我觉得特别的新鲜，让我有想进一步了解的欲望。通过本次实验，使我更加意识到C语言的重要性与它强大的功能性，让我明白数据结构的知识博大而精深，懂得数据结构对我们很重要。从这次实验中，我意识到自己的不足，而我还需要更加努力的学习，进一步去了解数据结构，学习数据结构，以及掌握C语言与数据结构的相关知识，也许将会收获到更多意想不到的惊喜。我想，无论做什么事，只要用心了就一定能够做好，即使会遇到很多的困难，也一定可以突破。6. 使用说明1.首先运行该程序，进入主页面。页面提示用户有三种选择，根据用户的选择，

31、进入相应的页面。2.用户选择“1”，可以人工输入二叉树的表达式，再按Enter键，界面显示二叉树的图形，同时有提示框，供用户选择三种遍历方式，用户选择遍历的代号，在下面就会输出遍历的序列，同时会显示结点的遍历序号。如果输入错误，程序会弹出对话框，提示用户输入错误，可以继续输入。如果不想继续，可以选择代码，回到主界面，进行其他的操作。3.用户选择“2”，可以自动生成二叉树，再按Enter键，界面显示二叉树的图形，同时有提示框，供用户选择三种遍历方式，用户选择遍历的代号，在下面就会输出遍历的序列，同时会显示结点的遍历序号。如果输入错误，程序会弹出对话框，提示用户输入错误，可以继续输入。如果不想继续

32、，可以选择代码，回到主界面，进行其他的操作。4.用户选择“3”，退出该程序，运行结束。7.参考文献1.李春葆，数据结构教程（第四版）。北京：清华大学出版社，2013.2.严蔚敏，吴伟民，数据结构。北京：清华大学出版社，2002.3.晋良影，数据结构。北京：人民邮电出版社，2002.4.将清明，黄晓宇，C语言程序设计教程。湖南：湖南科学技术出版社，2004.5.陈天洲，C语言高级程序设计。北京：人民邮电出版社，2002.8.附录源程序：#include "stdio.h"#include "stdlib.h"#include "malloc.h&

33、quot;#include "conio.h"#include "time.h"#include "graphics.h"#define Maxsize 26int c,d,w,x1,x2,y1,y2,top=-1;char ch;typedef struct nodechar data;struct node *lchild;struct node *rchild;int x; int y;int num;BTNode;BTNode *stMaxsize,*p,*q;void close()/图形的关闭getch();closegr

34、aph();void Point()x1=q->x; y1=q->y;x2=x1-w; y2=y1+35;p->x=x2;p->y=y2; struct node *CreatBT(BTNode *&t,char *str) /创建二叉树BTNode *stMaxsize,*p=NULL;int k;t=NULL;ch=*str;while(ch!='0') switch(ch) case '(':top+; sttop=p; k=1; break; case ')':top-; break; case '

35、,':k=2; break; default:p=(BTNode*)malloc(sizeof(BTNode); p->data=ch; p->lchild=p->rchild=NULL; if(t=NULL) t=p; Else switch(k) case 1:sttop->lchild=p;break; case 2:sttop->rchild=p;break; str+;ch=*str;return t;void PreOrder(BTNode *t,int m,int v)/先序遍历int i=0,x=90;char aMaxsize; outt

36、extxy(0,360,"先序遍历是:");if(t!=NULL) top+; t->x=m; t->y=v; sttop=t; t->num=1; while(top>-1) /栈不为空 p=sttop; top-; ch=p->data; outtextxy(x+20*i,360,ch); c=p->x; d=p->y; setfillstyle(RED); fillcircle(c,d,15); setbkcolor(WHITE); outtextxy(c-3,d-7,ch); Sleep(800); sprintf(a,&q

37、uot;%d",i+1); outtextxy(c-3,d+15," "); outtextxy(c-5,d+15,a); Sleep(500); i+; if(p->rchild!=NULL) top+; sttop=p->rchild; if(p=t) sttop->num=t->num+1; w=160; else sttop->num=p->num+1; if(p->num=2) w=80; if(p->num=3) w=40; if(p->num=4) w=20; if(p->num=5) w=20; x1=p->x; y1=p->y; x2=x1+w; y2=y1+35; sttop->x=x2; sttop->y=y2; if(p->lchild!=NULL) top+; sttop=p->lchild; if(p=t) sttop->num=t->num+1; w=160; else sttop->num=p->num+1; if(p->num=2) w=80; if(p->num=3) w=40; if(p->num=4) w=2