数据结构课程设计

学号：课程设计题目按层次遍历二叉树学院计算机科学与技术专业计算机科学与技术班级姓名指导教师2013 年 6 月20 日1 问题描述及要求 (4)1.1问题描述 (4)1.2任务要求 (4)2 开发平台及所使用软件 (4)3 程序设计思路 (5)3.1 二叉树存储结构设计 (5)3.2 题目算法设计 (5)3.2.1 建立二叉树 (5)3.2.2 遍历二叉树 (5)3.3.3 按要求格式输出已建立的二叉树 (6)3.3 测试程序 (6)4 调试报告 (6)5 经验和体会 (6)6源程序清单及运行结果 (7)6.1源程序清单 (7)6.2 运行结果 (9)7 参考文献 (10)本科生课程设计成绩评定表 (11)课程设计任务书学生姓名：专业班级：计科ZY1102班指导教师：工作单位：计算机科学系题目: 按层次遍历二叉树初始条件：编写按层次顺序（同一层自左至右）遍历二叉树的算法。

（1）二叉树采用二叉链表作为存储结构。

（2）按严蔚敏《数据结构习题集(C语言版)》p44面题6.69所指定的格式输出建立的二叉树。

（3）输出层次遍历结果。

（4）自行设计测试用例。

要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容：1. 问题描述简述题目要解决的问题是什么。

2. 设计存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计；3. 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。

4. 经验和体会（包括对算法改进的设想）5. 附源程序清单和运行结果。

源程序要加注释。

如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。

说明：1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。

2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。

时间安排：1．第17周完成，验收时间由指导教师指定2．验收地点：实验中心3．验收内容：可执行程序与源代码、课程设计报告书。

指导教师签名： 2013年6月14日系主任（或责任教师）签名：年月日数据结构课程设计——按层次遍历二叉树1 问题描述及要求1.1问题描述编写按层次顺序（同一层自左至右）遍历二叉树的算法，并将二叉树按指定格式输出。

（题集p44面题6.69所指定的格式）指定格式如下：图一：指定输出格式1.2任务要求编写按层次顺序（同一层自左至右）遍历二叉树的算法。

（1）二叉树采用二叉链表作为存储结构。

（2）按题集p44面题6.69所指定的格式输出建立的二叉树。

（3）输出层次遍历结果。

（4）测试用例自己设计。

2 开发平台及所使用软件Windows 7.0 , Visual Studio2010 CFEADB3 程序设计思路3.1 二叉树存储结构设计struct BinTreeNode //二叉树用二叉链表存储{char data; //二叉树结点值为字符型BinTreeNode* leftchild; //左孩子指针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{subTree=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->rightchild!=NULL){q.push(p->rightchild);}} };3.3.3 按要求格式输出已建立的二叉树void Print_BinTree(BinTreeNode* Tree,int i) //按要求格式输出已建立的二叉树 i 表示结点所在层次。

初始i=0 { BinTreeNode*p=Tree; if(p->rightchild) Print_BinTree(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); };3.3测试程序如图所示二叉树,按先序遍历顺序输入，AB#D##CE#F###。

其中”#”代表空格，二叉树是：A 为根节点，A 左孩子是B ，右孩子是C,B 的左孩子为空，右孩子为D ，C 的左孩子为E ，右孩子为空，E 的左孩子为空，右孩子为F 。

根据以下程序运行结果（见图4）可知，程序正确运行。

若输入AB#D#CE#F###，则程序出现错误，不能运行。

（见图3）4 调试报告1、在建立二叉树时，输入的格式一定要正确，没有孩子的要用空格表示，在测试用例中， F 没有孩子，要用两个空格表示，如果输入“AB#D##CE#F ”则没有输出结果。

2、起初编写输出程序（void Print_BinTree(BinTreeNode* Tree,int i)）的时候，始终显示编译无错误，但是不能运行，出现了一堆有关内存分配错误的问题。

最后发现没有将指针指向结点。

经改正，运行成功。

5 经验和体会本程序的建立和遍历二叉树的程序都比较简单，关键在于按要求打印二叉树。

起初一直图2：测试二叉树找不到合适的方法按题目要求打印二叉树，在和同学讨论了很久之后终于有了思路。

在调试程序的时候也出现了问题，起初没有在意输入方式对程序运行结果的影响，导致程序无法运行，在检查了很久之后终于找到了问题的所在，对输入进行了改正，得到了正确的结果。

除此之外，编写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,BinTreeNode*l=NULL,BinTreeNode*r=NULL):data(x),leftchild(l),rightc hild(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 creatBinTree(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)//重载操作：输入并建立一棵二叉树。

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->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!=NULL){q.push(p->rightchild);} //右子女进队}};V oid 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(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>>Tree;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]《数据结构（用面向对象方法与C++语言描述）（第二版）》，殷人昆主编，清华大学出版社，出版或修订时间：2007年6月[3]《C++程序设计》，闵联营，何克右编写，清华大学出版社，2010年8月本科生课程设计成绩评定表班级姓名：学号：序号评分项目满分实得分1 学习态度认真、遵守纪律102 设计分析合理性103 设计方案正确性、可行性、创造性204 设计结果正确性405 设计报告的规范性106 设计验收10总得分/等级评语：注：最终成绩以五级分制记。