order是什么意思按层次遍历二叉树

2021年1月20日发(作者：screwed)






课

程

设

计

题




目

按层次遍历二叉树

学




院

计算机科学与技术

专




业

计算机科学与技术

班




级


姓




名


指导教师




年


月


日

学

号：






武汉理工大学《数据结构》课程设计

课程设计任务书


学生姓名：

专业班级：

指导教师：

工作单位：

题

目
:
按层次遍历二叉树

初始条件：

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

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

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

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

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

要求完成的主要任务
:

（包括课程设计工作量及其技术要求，以及说明书撰写等具体要求）

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


1.
问题描述

简述题目要解决的问题是什么。

2.
设计

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

3.
调试报告

调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。

4.
经验和体会（包括对算法改进的设想）

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

说明：

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

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


时间安排：

1
、第
18
周完成。

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

指导教师签名：
2010
年
6
月
22
日

系主任（或责任教师）签名：

年

月

日



1

武汉理工大学《数据结构》课程设计

数据结构课程设计


一按层次遍历二叉树


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(
结点建立失败
!
T->data=ch;

2

武汉理工大学《数据结构》课程设计

CreateBinTree(T->lchild);

CreateBinTree(T->rchild);

}

}

3.2.2

遍历二叉树

void LevleOrder(BinTree T){


//
从第一层开始，从左到右


BinTree Queue[max],p; //
用一维数组表示队列，
front
和
re ar
分别表示队首和队尾指针

int front,rear;




front=rear=0;




if (T)


//
若树非空








{
Queue[rear++]=T; //
根结点入队列









while (front!=rear){


//
队列非空




p=Queue[front++];


//
队首元素出队列，并访问这个结点









printf(








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(
打印
T
元素
,
换行

if(T->lchild) Print_BiTree(T->lchild,i+1);
}
3.3

测试程序

图
1
：测试二叉树



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