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

《数据结构》课程设计报告 题 目 二叉树的遍历 学生姓名 学 号 专业班级 指导老师 设计日期 指导老师评阅意见： 评阅成绩： 签名： 目录 题目及要求 ……………………………………………1 二、设计的作用目的 ……………………………………………3 三、具体设计 ……………………………………………7 问题及解决方法 ……………………………………………17 程序结果集分析 ……………………………………………19 心得体会 ……………………………………………20 参考文献 ……………………………………………20 一、问题定义 1．课题目的 通过本项课程设计，培养学生独立思考、综合运用所学有关相应知识的能力，使学生巩固《数据结构》课程学习的内容，掌握工程软件设计的基本方法，强化上机动手编程能力，闯过理论与实践相结合的难关； 为了培养学生综合运用所学知识、独立分析和解决实际问题的能力，培养创 意识和创新能力，使学生获得科学研究的基础训练。 为后续各门计算机课程的学习和毕业设计打下坚实基础二叉树的五种基本形态如下图所示。?? 【例】下图中(a)和(b)是两棵不同的二叉树，它们同右图中的普通树(作为有序树或无序树)很相似，但却不等同于这棵普通树。若将这三棵树均看做普通树，则它们就是相同的了。遍历二叉树的执行踪迹??? 三种递归遍历算法的有哪些信誉好的足球投注网站路线相同（如下图虚线所示）。 具体线路为：??? 从根结点出发，逆时针沿着二叉树外缘移动，对每个结点均途径三次，最后回到根结点。 D B A E C F ② 先序序列 先序遍历二叉树时，对结点的访问次序为先序序列 【例】先序遍历上图所示的二叉树时，得到的先序序列为： A B D C E F ③ 后序序列 　后序遍历二叉树时，对结点的访问次序为后序序列 　【例】后序遍历上图所示的二叉树时，得到的后序序列为： D B E F C A 层序序列 层序遍历二叉树时，对结点的访问次序为层序序列 　【例】层序遍历上图所示的二叉树时，得到的层序序列为： A B C D E F ⑸遍历算法 ： ①中序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： (1)遍历左子树； (2)访问根结点； (3)遍历右子树。 ②先序遍历的递归算法定义： 若二叉树非空，则依次执行如下操作： (1) 访问根结点； (2) 遍历左子树； (3) 遍历右子树。 ③后序遍历得递归算法定义： 若二叉树非空，则依次执行如下操作： (1)遍历左子树； (2)遍历右子树； (3)访问根结点。 二、可行性分析 NS流程图： 三、程序设计 对于file1.h文件 #include malloc.h #include stdio.h #include iostream.h #include stdlib.h #define STACK_INIT_SIZE 20 #define STACKINCREMENT 5 #define ERROR 0 #define OK 1 typedef int ElemType; //结点元素类型为整型！！ typedef int Status; #define TRUE 1 #define FALSE 0 #define OVERFLOW -1 #define MAXQSIZE 10 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef char TElemType; /* 二叉树的元素类型为字符型 */ //二叉树 typedef struct BinaryTree { ElemType data; struct BinaryTree *lchil