数据结构课程设计二叉树的操作.doc

黑龙江工程学院数据结构课程设计题 目： 二叉树的操作 学生姓名： 学 号： 系部名称： 计算机科学与技术系 专业班级： 指导教师： SY-027课 程 设 计 任 务 书组内学生姓名人数1系部名称计算机科学与技术系专业软件工程班级、学号指导教师姓名职称从事专业软件工程题目名称 二叉树的操作一、 课程设计的目的、意义目的在于通过课程设计的综合训练，帮助学生深入系统地掌握数据结构课程的主要内容和基本方法，培养学生综合运用所学知识分析解决实际问题和编程等实际动手能力。熟练的掌握二叉树的基本操作。二、课程设计的主要内容、技术要求（包括原始数据、技术参数、设计要求、工作量要求等） 实现二叉树的先序、中序和后序遍历；求二叉树的结点总数、叶子结点个数及二叉树的深度。三、课程设计完成后应提交的成果 完整的论文和部分源代码四、课程设计的工作进度安排（1）复习与设计题目相关的数据结构知识，查阅文献资料 （1天）（2）确定设计方案，设计模块结构及各模块流程 （1天）（3）编码、调试与测试 （5天）（4）撰写课程设计报告 （2天）（5）设计演示 （1天） 五、主要参考资料1.严蔚敏、吴伟民，数据结构（C语言版），北京：清华大学出版社，2006.52.宁正元、易金聪，数据结构习题解析与上机实验指导，中国水利水电出版社、上海交通大学出版社、东南大学出版社，2002.6六、备注指导教师签字：年 月 日教研室主任签字： 年 月 日 - 第一章 程序要求1）完成二叉树的基本操作。2）建立以二叉链表为存储结构的二叉树；3）实现二叉树的先序、中序和后序遍历；4）求二叉树的结点总数、叶子结点个数及二叉树的深度。 第二章 算法分析建立以二叉链表为存储结构的二叉树，在次二叉树上进行操作；1先序遍历二叉树的操作定义为：若二叉树唯恐则为空操作；否则（1）访问根节点；（2）先序遍历做字数和；（3）先序遍历有子树；2中序遍历二叉树的操作定义为：若二叉树为空，则空操作;否则 （1）中序遍历做子树；（2）访问根节点；（3）中序遍历有子树；3后续遍历二叉树的操作定义为：若二叉树为空则为空操作；否则（1)后序遍历左子树 ;（2)后序遍历右子树;（3）访问根节点 ； 二叉树的结点总数、叶子结点个数及二叉树的深度。第三章 二叉树的基本操作和 算法实现 二叉树是一种重要的非线性数据结构，是另一种树形结构，它的特点是每个节点之多有两棵子树(即二叉树中不存在度大于2的结点)，并且二叉树的结点有左右之分，其次序不能随便颠倒。1.1 二叉树创建二叉树的很多操作都是基于遍历实现的。二叉树的遍历是采用某种策略使得采用树形结构组织的若干年借点对应于一个线性序列。二叉树的遍历策略有四种：先序遍历 中续遍历 后续遍历和层次遍历。基本要求1 从键盘接受输入数据（先序），以二叉链表作为存储结构，建立二叉树。2 输出二叉树。3 对二叉树进行遍历（先序，中序，后序和层次遍历）4 将二叉树的遍历打印出来。一问题描述二叉树的很多操作都是基于遍历实现的。二叉树的遍历是采用某种策略使得采用树型结构组织的若干结点对应于一个线性序列。二叉树的遍历策略有四种：先序遍历、中序遍历、后序遍历和层次遍历。二基本要求1从键盘接受输入数据（先序），以二叉链表作为存储结构，建立二叉树。2输出二叉树。3对二叉树进行遍历（先序、中序、后序和层次遍历）。4将二叉树的遍历结果打印输出。三提示与分析1主要数据类型 二叉链表 # define DataType char /*元素类型*/ typedef struct BiTNode DataType data; struct BiTNode *lchild, *rchild; BiTNode, *BiTree; 二叉树的遍历序列 DataType preordern;DataType inordern;DataType postordern;2基本功能分析 采用教材上类似于先序遍历的方法逐个输入结点，建立二叉链表存储的二叉树。 采用递归算法对二叉树分别进行先序、中序、后序遍历。 以队列为辅助结构实现二叉树的层次遍历。 结合先序遍历，以凹入表形式输出二叉树。/定义二叉树结点结构和操作的头文件btree1.h /定义二叉树结点值的类型为字符型typedef char ElemType; /定义二叉树结点类型struct BTreeNode ElemType data;BTreeNode* left;BTreeNode* right; /初始化二叉树，即把树根指针置空void InitBTree(BTreeNode*& BT);/判断二叉树是否为空bool BTreeEmpty(BTreeNode* BT);1.1.1 二叉树的遍历 二叉树的遍历即是如何按照某条路径寻访每一个结点，使得每个结点均被访问一次，而且仅被访问一次。“访问”的含义很广，可以是对结点做出各种处理，如输出结点的信息等。遍历对线性结构来说是一个容易解决的问题，而对于二叉树则不然，由于二叉树是一种非线性结构，每个结点都有可能有俩棵子树，因而需要寻找一种规律，以便使二叉树上的结点都能够排列在线性队列上，从而便于遍历。 二叉树室友三个基本单位组成的：根节点 左子树和右子树。因而遍历着三个部分，便是遍历了整个二叉树。void TraverseBTree(BTreeNode* BT, int mark)if(mark=1) /先序遍历if(BT!=NULL) coutdataleft,mark);TraverseBTree(BT-right,mark); else if(mark=2) /中序遍历 if(BT!=NULL) TraverseBTree(BT-left,mark);coutdataright,mark); else if(mark=3) /后序遍历if(BT!=NULL) TraverseBTree(BT-left,mark);TraverseBTree(BT-right,mark);coutdataleft);/计算右子树的深度int dep2=Depth(BT-right); /返回树的深度 if(dep1dep2) return dep1+1; else return dep2+1; /求二叉树中所有结点数int BinaryTree:BTreeCount() return Count(root);/用于求二叉树中所有结点数的递归函数int Count(BTreeNode* BT) if(BT=NULL) return 0;elsereturn Count(BT-left)+Count(BT-right)+1;/求二叉树中所有叶子结点数int BinaryTree:BTreeLeafCount()return LeafCount(root);/用于求二叉树中所有叶子结点数的递归函数int LeafCount(BTreeNode* BT) if(BT=NULL) return 0;else if(BT-left=NULL & BT-right=NULL) return 1;else return LeafCount(BT-left)+LeafCount(BT-right); 第四章 调试结果测试数据1输入：ABC+DE+G+F+（其中+表示空格字符）则输出结果为：先序：ABCDEGF中序：CBEGDFA后序：CGEFDBA2输入：AB+DG+CE+F+先序：ABDGCEF中序：BGDAECF后序：GDBEFCA3输入：ABDF+C+E+G+先序：ABDFCEG中序：FDBACEG后序：FDBGECA 第五章 实习体会数据结构的实习是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程. 回顾起此数据结构实习，至今我仍感慨颇多，的确，从选题到定稿，从理论到实践，在整整两星期的日子里，可以说得是苦多于甜，但是可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次实习使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固。经过两个星期的上机实践学习，使我对数据机构有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，通过实践，我也发现我的好多不足之处，首先是自己对知识点的掌握不够熟悉，通过学习也有所改进；再有对C语言的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。通过实践的学习，我认到学好计算机要重视实践操作，不仅仅是学习C语言，还是其它的语言，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注视实践操作，使自己便好地学好计算机。在今后的日子里，认真对待每意见事，争取做到最好，努力将知识与实践相结合，不断巩固，加深所学的知识，做到学以致用。参考文献：1.严蔚敏、吴伟民，数据结构（C语言版），北京：清华大学出版社，2006.52.宁正元、易金聪，数据结构习题解析与上机实验指导，