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

数据结构课程设计报告姓名班级学号指导老师一、课程设计目的培养学生用学到的书本知识解决实际问题的能力;培养实际工作所需要的动手能力;培养学生以科学理论和工程上能力的技术,规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用;通过课程设计的实践,学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。二、课程设计要求 1)学生必须仔细阅读《数据结构》课程设计方案,认真主动完成课程设计的要求。有问题及时主动通过各种方式与教师联系沟通。 2)学生要发挥自主学****能力,充分利用时间,安排好课程设计的时间计划, 并在课程设计过程中不断检测自己的计划完成情况,及时向教师汇报。 3)课程设计按照教学计划需要一周时间完成,一周中每天至少要上两小时的上机来调试 C或 C++ 语言设计的程序,总共至少要上机调试程序 10小时。属教师安排上机时间学生不得缺席。三、课程设计内容二叉树的中序、前序、后序的递归、非递归遍历算法,层次序的非递归遍历算法的实现,应包含建树的实现。四、课程设计原理 1. 设计思想以广义表格式输入一个二叉树,将其接收至一维数组中,利用栈结构建立二叉链表树;通过先、中、后访问根结点递归算法遍历二叉树;利用栈结构依次将结点入栈、出栈实现二叉树的非递归遍历算法;利用队列的入队、出队操作实现二叉树的层次遍历。例如: a(c(,d) , f(g,)) 建立如下图所示二叉树。 c ad fg 2. 数据结构 typedef BTREENODEPTR elemtype; 1) 队列数据类型定义 typedef struct{ elemtype *elem; int front,rear; int size; }SqQueue; 2) 栈数据类型定义 typedef struct stack_tag{ elemtype *elem; int top; int size; }SQSTACK; 3) 二叉树数据类型定义 typedef struct btreenode{ char data; struct btreenode *lchild,*rchild; }BTREENODE,*BTREENODEPTR,*BTREE; 3. 主要模块设计 BTREE CreateBtree1(char *str) ; //创建二叉树 void PreOrder(BTREE root) ; //先序递归遍历二叉树 void InOrder(BTREE root) ; //中序递归遍历二叉树 void PostOrder(BTREE root) ; //后序递归遍历二叉树 void PreOrder _1 (BTREE root) ; //先序非递归遍历二叉树 void InOrder _1 (BTREE root) ; //中序非递归遍历二叉树 void PostOrder _1 (BTREE root) ; //后序非递归遍历二叉树 void LayerOrder(BTREE root) ; //层次遍历其他模块包括栈的初始化及其基本操作和队列的初始化及基本操作。主菜单先序递归遍历中序递归遍历后序递归遍历先序非递归遍历中序非递归遍历后序非递归遍历层次遍历结束将以广义表形式输入的二叉树接收到数组 str[80] 中,成功建立二叉树 4. 详细设计 1)