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

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

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

3、; 3. 调试报告调试过程中遇到的问题是如何解决的 ; 对设计和编码的讨论和分析。 4. 经验 和体会（包括对算法改进的设想 ）5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据， 则运行结果要包含这些测试数据和运行输出。说明：1. 设计报告、程序不得相互抄袭和拷贝 ; 若有雷同，则所有雷同者成绩均为 0 分。 2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以 0 分记。 时间 安排：1（第17周完成，验收时间由指导教师指定2（验收地点：实验中心3（验收内容:可执行程序与源代码、课程设计报告书。指导教师签名：2013年6月14日系主任（或责任教师）签名：年 月曰3数据

4、结构课程设计按层次遍历二叉树1问题描述及要求1.1问题描述编写按层次顺序（同一层自左至右）遍历二叉树的算法，并将二叉树按指定格式输出。（题集p44面题6.69所指定的格式）指定格式如下：FB图一: 指定输出格式1.2 任务要求编写按层次顺序 (同一层自左至右 ) 遍历二叉树的算法。(1) 二叉树采用二叉链表作为存储结构。(2) 按题集p44面题6.69所指定的格式输出建立的二叉树(3) 输出层次遍历结果。(4) 测试用例自己设计。2 开发平台及所使用软件Windows 7.0 , Visual Studio201043 程序设计思路3.1 二叉树存储结构设计struct BinTreeNode

5、 / 二叉树用二叉链表存储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

6、->leftchild);creatBinTree(in,subTree->rightchild);elsesubTree=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();按层次序遍历二叉树左子树非空

7、，入队if(p->leftchild!=NULL)q.push(p->leftchild); /if(p->rightchild!=NULL)q.push(p->rightchild);333按要求格式输出已建立的二叉树void Prin t_Bi nTree(Bi nTreeNode* Tree,i nt i) /按要求格式输出已建立的二叉树i表示结点所在层次。初始i=0 Bin TreeNode*p=Tree;if(p->rightchild) Prin t_Bi nTree(Tree->rightchild,i+1); /递归函数for(int j=1

8、;j<=i;j+) cout<<" " /打印 i 个空格表示层次cout<<p->data<<e ndl;if(p->leftchild) Prin t_Bi nTree(Tree->leftchild,i+1);图 2: 测试二叉树如图所示二叉树,按先序遍历顺序输入，AB#D#CE#F#其中” #”代表空 格，二叉树是:A为根节点，A左孩子是B,右孩子是C,B的左孩子为空，右孩子为 D, C的左孩子为E,右孩子为空，E的左孩子为空，右孩子为F。根据以下程序运 行结果 ( 见图 4) 可知，程序正确运行。若输入A

9、B#D#CE#F#则程序出现错误，不能运行。(见图3)4 调试报告1、在建立二叉树时，输入的格式一定要正确，没有孩子的要用空格表示，在 测试用例中，F没有孩子，要用两个空格表示，如果输入“ AB#D#CE#F则没有 输出结果。2、起初编写输出程序 (void Print_BinTree(BinTreeNode* Tree,int i)的时候，始终显示编译无错误，但是不能运行，出现了一堆有关内存分配错误的问题。 最后发现没有将指针指向结点。经改正，运行成功。5 经验和体会 本程序的建立和遍历二叉树的程序都比较简单，关键在于按要求打印二叉树。 起初一直6 找不到合适的方法按题目要求打印二叉树，在和

10、同学讨论了很久之后终于有了 思路。在调试程序的时候也出现了问题，起初没有在意输入方式对程序运行结果的 影响，导致程序无法运行，在检查了很久之后终于找到了问题的所在，对输入进行 了改正，得到了正确的结果。除此之外，编写C+程序的过程中，指针时钟是个难点也是个重点，今后要多 练习，多理解才行。6源程序清单及运行结果6.1 源程序清单#include<iostream> #include<queue> using namespace std;structBinTreeNode / 定义结构体 char data;BinTreeNode* leftchild;BinTreeNo

11、de*rightchild;BinTreeNode():leftchild(NULL),rightchild(NULL)/ 结构体可以有构造函数BinTreeNode(intx,BinTreeNode*l=NULL,BinTreeNode*r=NULL):data(x),left child(l),rightchild(r);class BinTreeprivate:BinTreeNode* root;public:BinTree():root(NULL); / 构造函数，构造一棵空的二叉树 BinTreeNode* getroot()return root;BinTree(const Bin

12、Tree&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)

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

14、;)subTree=new BinTreeNode(item);creatBinTree(in,subTree->leftchild);creatBinTree(in,subTree->rightchild);从文件读入建重载操作 :elsesubTree=NULL;void BinTree:levelOrder(BinTreeNode* subTree) queue<BinTreeNode *>q; BinTreeNode*p=subTree;q.push(p); while(!q.empty() /队列不空 p=q.front();cout<<visit

15、(p)<<" " q.pop();左子女进队右子女进队释放空间 if(p->leftchild!=NULL)q.push(p->leftchild); / if(p->rightchild!=NULL)q.push(p->rightchild); /;Void BinTree:destroy(BinTreeNode*subTree) / if(subTree!=NULL) destroy(subTree->leftchild); destroy(subTree->rightchild); delete subTree;void

16、 Print_BinTree(BinTreeNode* Tree,int i)/ 按要求输出二叉树， i 表示结点所在层次，初次调用为 0 8 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->

17、;leftchild,i+1);int main()BinTree Tree;int a;int i=0;<<endl;cout<<" 请按照前序遍历的方法，输入初始值，每段空格结束 cin>>Tree;BinTreeNode*p=Tree.getroot();cout<<endl;cout<<" 层序遍历为 :"<<endl;Tree.levelOrder(p);cout<<endl;cout<<" 按树形打印输出二叉树 "<<endl;Prin t_Bi nTree(p,i);cin>>a;return 0;6.2运行结果图三：输入错误的运行结果9图四：输入正确的运行结果7参考文献1 数据结构习题集（C语言版），严蔚敏，吴伟民，米宁编著，清华大学 出版社，出版或修订时间：1999年2月2 数据结构（用面向对象方法与C+h语言描述）（第二版），殷人昆主编，清 华大学出版社，出