数据结构课程设计--按层次遍历二叉树

1、精品文档学 号： 课 程 设 计题 目按层次遍历二叉树学 院计算机科学与技术专 业计算机科学与技术班 级姓 名指导教师2021年6月20日1 问题描述及要求41.1问题描述41.2任务要求42 开发平台及所使用软件43 程序设计思路53.1 二叉树存储结构设计53.2 题目算法设计53.2.1 建立二叉树53.2.2 遍历二叉树53.3.3 按要求格式输出已建立的二叉树63.3 测试程序64 调试报告65 经验和体会76源程序清单及运行结果76.1源程序清单76.2 运行结果97 参考文献10本科生课程设计成绩评定表11 课程设计任务书 学生姓名： 专业班级： 计科ZY1102班 指导教师：

2、工作单位： 计算机科学系 题目: 按层次遍历二叉树 初始条件：编写按层次顺序同一层自左至右遍历二叉树的算法。1二叉树采用二叉链表作为存储结构。2按严蔚敏?数据结构习题集(C语言版)?p44面题6.69所指定的格式输出建立的二叉树。3输出层次遍历结果。4自行设计测试用例。要求完成的主要任务: 包括课程设计工作量及其技术要求，以及说明书撰写等具体要求课程设计报告按学校规定格式用A4纸打印书写，并应包含如下内容： 1. 问题描述简述题目要解决的问题是什么。2. 设计存储结构设计、主要算法设计用类C/C+语言或用框图描述、测试用例设计；3. 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论

3、和分析。4. 经验和体会包括对算法改良的设想5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，那么运行结果要包含这些测试数据和运行输出。说明：1. 设计报告、程序不得相互抄袭和拷贝；假设有雷同，那么所有雷同者成绩均为0分。2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。时间安排：1第17周完成，验收时间由指导教师指定2验收地点：实验中心3验收内容：可执行程序与源代码、课程设计报告书。指导教师签名： 2021年6月14日系主任或责任教师签名： 年 月 日数据结构课程设计 按层次遍历二叉树1 问题描述及要求1.1问题描述编写按层次顺序同一层自左至右遍历二叉树的算

4、法，并将二叉树按指定格式输出。题集p44面题6.69所指定的格式指定格式如下： C F E A D B 图一：指定输出格式1.2任务要求编写按层次顺序同一层自左至右遍历二叉树的算法。1二叉树采用二叉链表作为存储结构。2按题集p44面题6.69所指定的格式输出建立的二叉树。3输出层次遍历结果。4测试用例自己设计。2 开发平台及所使用软件Windows 7.0 , Visual Studio20213 程序设计思路3.1 二叉树存储结构设计struct BinTreeNode /二叉树用二叉链表存储 char data; /二叉树结点值为字符型BinTreeNode* leftchild; /左孩

5、子指针BinTreeNode*rightchild; /右孩子指针 3.2 题目算法设计3.2.1 建立二叉树void BinTree:creatBinTree(istream& in,BinTreeNode*&subTree) /通过输入流in建立二叉树char item;cin.get(item);if(item!=' ')subTree=new BinTreeNode(item);creatBinTree(in,subTree->leftchild);creatBinTree(in,subTree->rightchild);else subTr

6、ee=NULL; 3.2.2 遍历二叉树void BinTree:levelOrder(BinTreeNode* subTree) /按层次序遍历二叉树queue<BinTreeNode *>q;BinTreeNode*p=subTree;q.push(p);while(!q.empty() /假设树非空p=q.front();cout<<visit(p)<<" " /输出队头元素q.pop();if(p->leftchild!=NULL)q.push(p->leftchild); /左子树非空，入队if(p->righ

7、tchild!=NULL)q.push(p->rightchild);3.3.3 按要求格式输出已建立的二叉树void Print_BinTree(BinTreeNode* Tree,int i) /按要求格式输出已建立的二叉树 i表示结点所在层次。初始i=0BinTreeNode*p=Tree;if(p->rightchild) Print_BinTree(Tree->rightchild,i+1); /递归函数for(int j=1;j<=i;j+) cout<<" " /打印i个空格表示层次cout<<p->dat

8、a<<endl;if(p->leftchild) Print_BinTree(Tree->leftchild,i+1);3.3 测试程序图2：测试二叉树 如下图二叉树,按先序遍历顺序输入，AB#D#CE#F#。其中#代表空格，二叉树是：A为根节点，A左孩子是B，右孩子是C,B的左孩子为空，右孩子为D，C的左孩子为E，右孩子为空，E的左孩子为空，右孩子为F。根据以下程序运行结果见图4可知，程序正确运行。 假设输入AB#D#CE#F#，那么程序出现错误，不能运行。见图34 调试报告 1、在建立二叉树时，输入的格式一定要正确，没有孩子的要用空格表示，在测试用例中， F没有孩子

9、，要用两个空格表示，如果输入“AB#D#CE#F那么没有输出结果。 2、起初编写输出程序void Print_BinTree(BinTreeNode* Tree,int i)的时候，始终显示编译无错误，但是不能运行，出现了一堆有关内存分配错误的问题。最后发现没有将指针指向结点。经改正，运行成功。5 经验和体会 本程序的建立和遍历二叉树的程序都比拟简单，关键在于按要求打印二叉树。起初一直找不到适宜的方法按题目要求打印二叉树，在和同学讨论了很久之后终于有了思路。在调试程序的时候也出现了问题，起初没有在意输入方式对程序运行结果的影响，导致程序无法运行，在检查了很久之后终于找到了问题的所在，对输入进行

10、了改正，得到了正确的结果。 除此之外，编写C+程序的过程中，指针时钟是个难点也是个重点，今后要多练习，多理解才行。6源程序清单及运行结果6.1源程序清单#include<iostream>#include<queue>using namespace std;structBinTreeNode /定义结构体char data;BinTreeNode* leftchild;BinTreeNode*rightchild;BinTreeNode():leftchild(NULL),rightchild(NULL) /结构体可以有构造函数BinTreeNode(intx,BinT

11、reeNode*l=NULL,BinTreeNode*r=NULL):data(x),leftchild(l),rightchild(r);class BinTree private:BinTreeNode* root;public:BinTree():root(NULL); /构造函数，构造一棵空的二叉树BinTreeNode* getroot()return root;BinTree(const BinTree&s); /复制构造函数BinTree()destroy(root); /析构函数void destroy(BinTreeNode* subTree); /删除void cr

12、eatBinTree(istream&in,BinTreeNode* &subTree); /从文件读入建树friend istream& operator>>(istream& in,BinTree & Tree); /重载操作：输入void levelOrder(BinTreeNode* subTree); /层次序遍历char visit(BinTreeNode*p)return p->data; /取值;istream& operator>>(istream& in,BinTree& Tree

13、) /重载操作：输入并建立一棵二叉树。in是输入流对象Tree.creatBinTree(in,Tree.root);return in;void BinTree:creatBinTree(istream& in,BinTreeNode*&subTree) /从输入流in输入二叉树表示建立对应的二叉链表char item;cin.get(item);if(item!=' ')subTree=new BinTreeNode(item);creatBinTree(in,subTree->leftchild);creatBinTree(in,subTree-&g

14、t;rightchild);else subTree=NULL;void BinTree:levelOrder(BinTreeNode* subTree)queue<BinTreeNode *>q;BinTreeNode*p=subTree;q.push(p);while(!q.empty() /队列不空p=q.front();cout<<visit(p)<<" "q.pop();if(p->leftchild!=NULL)q.push(p->leftchild); /左子女进队if(p->rightchild!=NUL

15、L)q.push(p->rightchild); /右子女进队;Void BinTree:destroy(BinTreeNode*subTree) /释放空间if(subTree!=NULL)destroy(subTree->leftchild);destroy(subTree->rightchild);delete subTree;void Print_BinTree(BinTreeNode* Tree,int i) /按要求输出二叉树，i表示结点所在层次，初次调用为0BinTreeNode*p=Tree;if(p->rightchild) Print_BinTree

16、(Tree->rightchild,i+1); for(int j=1;j<=i;j+) cout<<"" /打印i个空格表示层次cout<<p->data<<endl; /打印元素，换行if(p->leftchild) Print_BinTree(Tree->leftchild,i+1);int main()BinTree Tree;int a;int i=0;cout<<"请按照前序遍历的方法，输入初始值，每段空格结束："<<endl;cin>>Tr

17、ee;BinTreeNode*p=Tree.getroot();cout<<endl;cout<<"层序遍历为："<<endl;Tree.levelOrder(p);cout<<endl;cout<<"按树形打印输出二叉树"<<endl;Print_BinTree(p,i);cin>>a;return 0;6.2 运行结果图三：输入错误的运行结果图四：输入正确的运行结果7 参考文献 1 ?数据结构习题集(C语言版)?，严蔚敏，吴伟民，米宁编著，清华大学出版社，出版或修订时间：1999年2月 2?数据结构用面向对象方