按层次遍历二叉树

武汉理工大学课程设计

课 程 设 计

题 目 按层次遍历二叉树 学 院 计算机科学与技术 专 业 计算机科学与技术

班 级 姓 名

指导教师

年

月

日

武汉理工大学课程设计

课程设计任务书

学生姓名： 专业班级： 指导教师： 工作单位：

题 目: 按层次遍历二叉树 初始条件：

编写按层次顺序（同一层自左至右）遍历二叉树的算法。 （1）二叉树采用二叉链表作为存储结构。

（2）按严蔚敏《数据结构习题集(C语言版)》p44面题6.69所指定的格式输出建立的二叉树。 （3）输出层次遍历结果。 （4）自行设计测试用例。

要求完成的主要任务: （包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）

课程设计报告按学校规定格式用A4纸打印（书写），并应包含如下内容： 1. 问题描述

简述题目要解决的问题是什么。 2. 设计

存储结构设计、主要算法设计（用类C/C++语言或用框图描述）、测试用例设计； 3. 调试报告

调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。 4. 经验和体会（包括对算法改进的设想）

5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，则运行结果要包含这些测试数据和运行输出。

说明：

1. 设计报告、程序不得相互抄袭和拷贝；若有雷同，则所有雷同者成绩均为0分。 2. 凡拷贝往届任务书或课程设计充数者，成绩一律无效，以0分记。

时间安排：

1、第18周完成。

2、7月2日8:30时到实验中心检查程序、交课程设计报告、源程序（U盘）。

指导教师签名： 2010年6月22日 系主任（或责任教师）签名： 年 月 日

武汉理工大学课程设计

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

1 问题描述及要求

1.1问题描述

编写按层次顺序（同一层自左至右）遍历二叉树的算法。

1.2任务要求

编写按层次顺序（同一层自左至右）遍历二叉树的算法。 （1）二叉树采用二叉链表作为存储结构。

（2）按题集p44面题6.69所指定的格式输出建立的二叉树。 （3）输出层次遍历结果。 （4）测试用例自己设计。

2 开发平台及所使用软件

Windows 7.0 , 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(); //输入函数。

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 测试程序

图1：测试二叉树

如图所示二叉树,按先序遍历顺序输入，AB#D##CE#F###。其中”#”代表空格，理论上按层次遍历的结

武汉理工大学课程设计

果应该是”CFEADB”,二叉树是：A为根节点，A左孩子是B，右孩子是C,B的左孩子为空，右孩子为D，C的左孩子为E，右孩子为空，E的左孩子为空，右孩子为F。根据以下程序运行结果（见图2）可知，程序正确运行

4 调试报告

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

5 经验和体会

本程序的建立和遍历二叉树的程序都比较简单，关键在于按要求打印二叉树。起初一直找不到合适的方法按题目要求打印二叉树，在和同学讨论了很久之后终于有了思路。打印的格式中，最上层的节点是右子树层次最高的，于是就可以用递归调用的方式实现。递归次数最高的就是输出最顶置的节点。在调试程序的时候也出现了问题，起初没有在意输入方式对程序运行结果的影响，导致程序无法运行，在检查了很久之后终于找到了问题的所在，对输入进行了改正，得到了正确的结果

6源程序清单及运行结果

6.1源程序清单

#include <stdio.h> #include <stdlib.h> #define max 100

typedef char ElemType; typedef struct BiTNode{ ElemType data;

struct BiTNode *lchild,*rchild; } BiTNode,*BinTree;

//建立二叉树

void CreateBinTree(BinTree &T){ char ch;

ch=getchar();

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; 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 运行结果

武汉理工大学课程设计

图2：运行结果

7 参考文献

[1]《数据结构(C语言版)》，严蔚敏，吴伟民编著，出版社：清华大学出版社，出版或修订时间：1997年4月

[2]《数据结构习题集(C语言版)》，严蔚敏，吴伟民，米宁编著，清华大学出版社，出版或修订时间：1999年2月

武汉理工大学课程设计

本科生课程设计成绩评定表

及格（60-69分）、60分以下为不及格

指导教师签名：

2010 年 月 日

本文来源：https://www.bwwdw.com/article/tlvj.html