层次遍历二叉树

层次遍历二叉树层次遍历二叉树课程名称数据结构设计题目按层次遍历二叉树学院计算机科学与技术专业计算机科学与技术班级学号姓名指导教师 2009 年 7 月 3 日课程设计任务书学生姓名: 专业班级: 计算机 0708 指导教师: 工作单位: 计算机科学系题目: 按层次遍历二叉树初始条件: 编写按层次顺序(同一层自左至右)遍历二叉树的算法。 (1)二叉树采用二叉链表作为存储结构。 (2)按题集p44面题6.69所指定的格式输出建立的二叉树。 (3)输出层次遍历结果。 ...

层次遍历二叉树课程名称数据结构设计题目按层次遍历二叉树学院计算机科学与技术专业计算机科学与技术班级学号姓名指导教师 2009 年 7 月 3 日课程设计任务书学生姓名: 专业班级: 计算机 0708 指导教师: 工作单位: 计算机科学系题目: 按层次遍历二叉树初始条件: 编写按层次顺序(同一层自左至右)遍历二叉树的算法。 (1)二叉树采用二叉链表作为存储结构。 (2)按题集p44面题6.69所指定的格式输出建立的二叉树。 (3)输出层次遍历结果。 (4)测试用例自己设计。要求完成的主要任务: (包括课程设计工作量及其技术要求，以及说明书撰写等具体要求) 课程设计报告按学校规定格式用A4纸打印(书写)，并应包含如下内容: 1、问题描述简述题目要解决的问题是什么。 2、设计存储结构设计、主要算法设计(用类C语言或用框图描述)、测试用例设计; 3、调试报告调试过程中遇到的问题是如何解决的;对设计和编码的讨论和分析。 4、经验和体会(包括对算法改进的设想) 5、附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出， 6、设计报告、程序不得相互抄袭和拷贝;若有雷同，则所有雷同者成绩均为0分。时间安排: 1、第19周完成。 2、7月3日8:30时到计算中心检查程序、交课程设计报告、源程序(CD光盘)。指导教师签名: 2009年07月26日系主任(或责任教师)签名: 年月日《按层次遍历二叉树》课程设计 1 问题描述和任务定义 1.1问题描述编写按层次顺序(同一层自左至右)遍历二叉树的算法。 1.2任务定义编写按层次顺序(同一层自左至右)遍历二叉树的算法。 (1)二叉树采用二叉链表作为存储结构。 (2)按题集p44面题6.69所指定的格式输出建立的二叉树。 (3)输出层次遍历结果。 (4)测试用例自己设计。 2 开发平台 Windows XP , Visual C++6.0 3 数据类型和系统设计 3.1存储结构设计 typedef char ElemType; //定义二叉树结点值的类型为字符型 typedef struct BiTNode{ //二叉树的二叉链表存储表示 ElemType date; struct BiTNode *lchild,*rchild; //左右孩子指针 } BiTNode，*BiTree; 3.2 主要算法设计 3.2.1 建立二叉树 void CreateBinTree(BinTree &T){ //按先序次序输入，构造二叉链表表示的二叉树T char ch; ch=getchar(); //不能用cin来输入，在cin中不能识别空格。 if(ch==’ ’) T=NULL; //输入空格时为空 else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) printf("%c" "结点建立失败!") ; T->data=ch; CreateBinTree(T->lchild); CreateBinTree(T->rchild); } } 3.2.2 按层次遍历已建立的二叉树并输出遍历结果 void LevleOrder(BinTree T){ //从第一层开始，从左到右 BinTree Queue[max],p; //用一维数组表示队列，front和rear分别表示队首和队尾指针 int front,rear; front=rear=0; if (T) //若树非空 { Queue[rear++]=T; //根结点入队列 while (front!=rear){ // 队列非空 p=Queue[front++]; // 队首元素出队列，并访问这个结点 printf("%c",p->data); if (p->lchild!=NULL) Queue[rear++]=p->lchild; //左子树非空，入队列 if (p->rchild!=NULL) Queue[rear++]=p->rchild; } } } 3.2.3 按树状打印输出已建立的二叉树 void Print_BinTree(BinTree T,int i ) // i表示结点所在层次,初次调用时i=0 { if(T->rchild) Print_BinTree(T->rchild,i+1); //函数递归 for(j=1;j<=i;j++) printf(" "); //打印i个空格以表示出层次 printf("%c\n",T->data); //打印T元素,换行 if(T->lchild) Print_BiTree(T->lchild,i+1); } 3.3 测试用例设计程序调试完毕后，输入一字符串来检测程序，按先序顺序输入字符串”asd#g###kl##i##”,其中”#”代表空格，理论上按层次遍历的结果应该是”askdlig”,二叉树是:a为根节点，a左孩子是s，右孩子是k,s只有一个左孩子d，d只有一个右孩子g，k的左右孩子分别为l、i，g、 l、i无孩子。根据以下程序运行结果(见6.2)可知，程序正确运行 4 调试报告只要问题是建立二叉树时，必须对每个节点的孩子进行输入，如果没有孩子也必须输入空格，所以在实验时我输入”asd#g###kl##i”然后回车怎是没有反应，只到将输入改成”asd#g###kl##i##”才输出6.2所示结果。 5 经验和体会本次课程设计的内容为二叉树的层序遍历，要想完成本次任务要求我对二叉树的结构和性质十分的了解，同时要能很好的运用已学的知识设计各类算法，最终得到完整的程序。通过此次课程设计，我发现我对很多东西了解的还不透彻，比如说算法设计中经常要要到的函数的递归调用我就不是很熟练。同时在二叉树的构造设计中还有个缺陷，就是对于任意一个结点，就算它没有孩子我都必须给他输入空格来代替，例如测试用例中必须输入”asd#g###kl##i##”，而”asd#g###kl##i”不行，这是急需改进的。 6源程序清单及运行结果 6.1源程序清单 #include #include #define max 18 //结点最大个数 typedef char ElemType; //定义二叉树结点值的类型为字符型 typedef struct BiTNode{ //二叉树的二叉链表存储表示 ElemType data; struct BiTNode *lchild,*rchild; //左右孩子指针 } BiTNode,*BinTree; //-------------创立二叉树---------------- void CreateBinTree(BinTree &T){ //按先序次序输入，构造二叉链表表示的二叉树T char ch; ch=getchar(); //不能用cin来输入，在cin中不能识别空格。 if(ch==' ') T=NULL; //输入空格时为空 else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) printf("%c" "结点建立失败!") ; T->data=ch; CreateBinTree(T->lchild); CreateBinTree(T->rchild); } } //----------按层次遍历二叉树------------------ void LevleOrder(BinTree T){ //从第一层开始，从左到右 BinTree Queue[max],p; //用一维数组表示队列，front和rear分别表示队首和队尾指针 int front,rear; front=rear=0; if (T) //若树非空 { Queue[rear++]=T; //根结点入队列 while (front!=rear){ // 队列非空 p=Queue[front++]; // 队首元素出队列，并访问这个结点 printf("%c",p->data); if (p->lchild!=NULL) Queue[rear++]=p->lchild; //左子树非空，入队列 if (p->rchild!=NULL) Queue[rear++]=p->rchild; } } } //-----------按树状打印二叉树---------------- void Print_BinTree(BinTree T,int i ) // i表示结点所在层次,初次调用时i=0 { if(T->rchild) Print_BinTree(T->rchild,i+1); //函数递归 for(int j=1;j<=i;j++) printf(" "); //打印i个空格以表示出层次 printf("%c\n",T->data); //打印T元素,换行 if(T->lchild) Print_BinTree(T->lchild,i+1); } int main() { BinTree T;int i=0; printf("\n创建二叉树\n"); CreateBinTree (T); printf("\n层次遍历二叉树并输出遍历结果\n"); LevleOrder(T); printf("\n按树形打印输出二叉树\n"); Print_BinTree(T, i); return 0; } 6.2 运行结果 7 参考文献 [1]《数据结构(C语言版)》，严蔚敏，吴伟民编著，出版社:清华大学出版社，出版或修订时间:1997年4月 [2]《数据结构习题集(C语言版)》，严蔚敏，吴伟民，米宁编著，清华大学出版社，出版或修订时间:1999年2月

                    本文档为【层次遍历二叉树】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

层次遍历二叉树

你可能还喜欢