数据结构课程设计二叉树的遍历报告

1、数据结构课程设计报告姓名班级学号指导老师一、课程设计目的培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用；通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、课程设计要求1)学生必须仔细阅读数据结构课程设计方案，认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。2)学生要发挥自主学习能力，充分利用时间，安排好课程设计的时间计划，并在课程设计过程中不断检测自己的计划完成情况，及时向教师汇报。3)课程

2、设计按照教学计划需要一周时间完成，一周中每天至少要上两小时的上机来调试C或C+语言设计的程序，总共至少要上机调试程序10小时。属教师安排上机时间学生不得缺席。三、课程设计内容二叉树的中序、前序、后序的递归、非递归遍历算法，层次序的非递归遍历算法的实现，应包含建树的实现。四、课程设计原理1 .设计思想以广义表格式输入一个二叉树，将其接收至一维数组中，利用栈结构建立二叉链表树；通过先、中、后访问根结点递归算法遍历二叉树；利用栈结构依次将结点入栈、出栈实现二叉树的非递归遍历算法；利用队列的入队、出队操作实现二叉树的层次遍历。例如：a(c(,d),f(g,)建立如下图所示二叉树。2 .数据结构type

3、defBTREENODEPTRelemtype;1)队列数据类型定义typedefstructelemtype*elem;intfront,rear;intsize;SqQueue;2)栈数据类型定义typedefstructstack_tagelemtype*elem;inttop;intsize;SQSTACK;3)二叉树数据类型定义typedefstructbtreenodechardata;structbtreenode*lchild,*rchild;BTREENODE,*BTREENODEPTR,*BTREE;3 .主要模块设计BTREECreateBtree1(char*str);

4、创建二叉树voidPreOrder(BTREEroot);/先序递归遍历二叉树voidInOrder(BTREEroot);中序递归遍历二叉树voidPostOrder(BTREEroot);后序递归遍历二叉树voidPreOrder_1(BTREEroot);/先序非递归遍历"二叉树voidInOrder_1(BTREEroot);/中序非递归遍历"二叉树voidPostOrder_1(BTREEroot);/后序非递归遍历"二叉树voidLayerOrder(BTREEroot);/层次遍历其他模块包括栈的初始化及其基本操作和队列的初始化及基本操作4 .详细设

5、计1）二叉树的建立其中mark的值1、2、3、4分别指stri为字母、（、，'、'）'tag为左、右孩子的标志；root=nullNstr0是否为子母returnnull2）二叉树的递归遍历（以先序遍历为例）3）二叉树的非递归遍历（以先序遍历为例）4）二叉树的层次遍历则该元素所指访问元素所指结点，若该元素所指结点的左右孩子结点非空,结点的左孩子指针和右孩子指针顺序入队。五、运行结果1 .建立二叉树人少请输入一棵二叉树二a<c<,d>,£<«,>>2 .先序遍历历历历一历历历遍遍遍"ffir什嘱遍遍rnR日

6、.百好归归归通膏历一繇递递递翦"先中后先中后层样-人请选择;iacdfg、,请选择4acdfg请选择:3.中序遍历二二“历历历“一一历历历遍遍遍"一却遍遍遍归归归七臂归®S速递历一转速递递一一先中觐一=123456?请选择:2Gdagf请选择:cdasrF"J请选函4.后序遍历"二二历历历"一评:历历历遍遍遍一一4之牖遍遍归归归一一配襦归归归递递递历即钙递递递藏一一先中后先中后屈瑾1234567-1文人-,请选择:3dcgfa请选择:6dcsrfa请选择:5.层次遍历二二历历历一一一历历历遍遍遍"一什遍遍遍归归归VE归归®8递递历J速递递"柏名加中后层«,L=1234567.，人请选择:?acfdg内宿选择：6.退由程序"=.先序醐遍历2.中住递归遍历="口巨凌;旬口推下="=3.先与韭递归遍历=5.中层瓒归遍历=6.后序三三递归遍历1=7.层次调历”取按任意键退出程序改正在退出程序*-“7.由错信息请输入一棵二叉树;a,d<a9输入有误.一接任意便退出程序.六、设计总结二叉树是数