按层次遍历二叉树

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

2、设计存储结构设计、主要算法设计（用类C/C+语言或用框图描述）、测试用例设计;3.调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4.经验和体会（包括对算法改进的设想）5.附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。说明:1.设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。2.凡拷贝往届任务书或课程设计充数者，成绩一律无效，以0分记。时间安排:1、第18周完成。2、7月2日8:30时到实验中心检查程序、交课程设计报告、源程序（U盘）。指导教师签名:2010年6月22日系主任（或责任教师）签名:

3、数据结构课程设计按层次遍历二叉树1问题描述及要求1.1问题描述编写按层次顺序(同一层自左至右)遍历二叉树的算法。1.2任务要求编写按层次顺序(同一层自左至右)遍历二叉树的算法。(1) 二叉树采用二叉链表作为存储结构。(2) 按题集p44面题6.69所指定的格式输出建立的二叉树。(3) 输出层次遍历结果。(4) 测试用例自己设计。2开发平台及所使用软件Win dows 7.0, Visual C+6.03程序设计思路3.1二叉树存储结构设计typ edef char ElemT ype;/二叉树结点值的类型为字符型typ edef struct BiTNode/二叉树的二叉链表存储表示ElemT

4、 ypedate;struct BiTNode*lchild,*rchild;/左右孩子指针 BiTNode ，*BiTree;3.2 题目算法设计3.2.1建立二叉树void CreateBi nTree(B in Tree &T)/按先序次序输入，构造二叉链表表示的二叉树char ch;ch=getchar(); II输入函数。if(ch=)T=NULL; /输入空格时为空结点建立失败!)；elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode) prin tf(%cT-data=ch;CreateBi nTree(T-lchild);CreateBi nT

5、ree(T-rchild);3.2.2 遍历二叉树void LevleOrder(Bi nTree T)/从第一层开始，从左到右Bin Tree Queuemax, p; /用一维数组表示队列，front和rear分别表示队首和队尾指针int fron t,rear;fron t=rear=0;if (T)/若树非空Queuerear+=T; /根结点入队列while (fron t!=rear)/队列非空P=Queuefr on t+;/队首元素出队列，并访问这个结点左子树非空，入队列prin tf(%c, p-data);if (p-lchild!=NULL) Queuerear+=p-l

6、child; / if (p-rchild!=NULL) Queuerear+=p-rchild; 要用两个空格表示，如果输入“AB#D#CE#F ”则没有输出结果。3.2.3按要求格式输出已建立的二叉树void PrintBin Tree(B in Tree T,i nt i ) i表示结点所在层次，初次调用时i=0if(T-rchild) Print_Bin Tree(T-rchild,i+1);/函数递归for( j=1;jdata); /打印T元素，换行if(T-lchild) Prin t_BiTree(T-lchild,i+1);3.3测试程序图1 ：测试二叉树如图所示二叉树，按先

7、序遍历顺序输入,AB#D#CE#F# 。其中” # ”代表空格，理论上按层次遍历的结果应该是” CFEADB ”，二叉树是：A为根节点，A左孩子是B，右孩子是C,B的左孩子为空, 右孩子为D，C的左孩子为E,右孩子为空，E的左孩子为空，右孩子为 F。根据以下程序运行结果（见图2）可知，程序正确运行4调试报告F没有孩子,在建立二叉树时，输入的格式一定要正确，没有孩子的要用空格表示，在测试用例中,5经验和体会本程序的建立和遍历二叉树的程序都比较简单，关键在于按要求打印二叉树。起初一直找不到合适的方法按题目要求打印二叉树，在和同学讨论了很久之后终于有了思路。打印的格式中，最上层的节点是右子树层次最高

8、的，于是就可以用递归调用的方式实现。递归次数最高的就是输出最顶置的节点。导致程序无法运行,在调试程序的时候也出现了问题，起初没有在意输入方式对程序运行结果的影响,在检查了很久之后终于找到了问题的所在，对输入进行了改正，得到了正确的结果6源程序清单及运行结果6.1源程序清单#in elude #in elude #defi ne max 100typ edef char ElemT ype;typ edef struct BiTNodeElemT ypedata;struct BiTNode*lchild,*rchild; BiTNode,*B in Tree;/建立二叉树void Create

9、Bi nTree(B in Tree &T)char ch;ch=getchar();if(ch= ) T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode) prin tf(%c结点建立失败!）；T-data=ch;CreateBi nTree(T-lchild);CreateBi nTree(T-rchild);/遍历二叉树void LevleOrder(Bi nTree T)Bi nTree Queuemax, p;int fron t,rear;fron t=rear=0;if (T)Queuerear+=T;while (fron t!

10、=rear)p=Queuefr on t+;prin tf(%c, p-data);if (p-lchild!=NULL) Queuerear+=p-lchild;if (p-rchild!=NULL) Queuerear+=p-rchild; /按要求输出二叉树i=0void Print_Bin Tree(B in Tree T,i nt i )II本题的关键所在,i表示结点所在层次 ，初次调用时if(T-rchild) Prin t_Bi nTree(T-rchild,i+1);II本题的难点，函数递归来建立层次。);II打印i个空格以表示出层次打印T元素，换行for(i nt j=1;j

11、data); IIif(T-lchild) Prin t_Bi nTree(T-lchild,i+1);int mai n()Bin Tree T;i nt i=0;prin tf(n创建二叉树n);CreateB in Tree (T);printf（n 层次遍历二叉树并输出遍历结果n）;LevleOrder(T);prin tf（n按树形打印输出二叉树n）;Prin t_Bi nTree(T, i);return 0;6.2运行结果图2:运行结果7参考文献1数据结构（C语言版），严蔚敏，吴伟民编著，出版社：清华大学出版社，出版或修 订时间：1997年4月 2数据结构习题集（C语言版），严蔚敏，吴伟民，米宁编著，清华大学出版社，出版 或修订时间：1999年2月本科生课程设计成绩评定表