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

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

课程设计

题 目 按层次遍历二叉树

学 院 计算机科学与技术

专 业 计算机科学与技术

班 级

姓 名

指导教师

2013 年 6 月 20 日

1问题描述及要求. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .错误未定义书签。

1 1问题描述错误未定义书签。

1.2任务要求. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .错误未定义书签。

2 开发平台及所使用软件. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .错误未定义书签。

3程序设计思路错误未定义书签。

3。 1二叉树存储结构设计错误未定义书签。

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

3 2题目算法设计错误未定义书签。

3。 2。 1 建立二叉树错误未定义书签。

 。 2.2遍历二叉树错误未定义书签。

3。 3 按要求格式输出已建立的二叉树错误未定义书签。

3。 3 测试程序6

调试报告. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .错误未定义书签。

5经验和体会. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .错误未定义书签。

6源程序清单及运行结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .错误未定义书签。

.1源程序清单. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .错误未定义书签。

6.2运行结果. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .错误未定义书签。

参考文献错误未定义书签。

本科生课程设计成绩评定表. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .错误未定义书签。

课程设计任务书

学生姓名 专业班级: 计科ZY1  0班

指导教师: 工作单位: 计算机科学系

题目 按层次遍历二叉树

初始条件

编写按层次顺序(同一层自左至右遍历二叉树的算法.

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

(1二叉树采用二叉链表作为存储结构。

(2)按严蔚敏《数据结构习题集(C语言版》 p4面题 。 69所指定的格式

输出建立的二叉树.

(3)输出层次遍历结果。

4 自行设计测试用例。

要求完成的主要任务 (包括课程设计工作量及其技术要求 以及说明书撰写等具体要求)

课程设计报告按学校规定格式用A4纸打印(书写并应包含如下内容:

1 问题描述

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

2 设计

存储结构设计、主要算法设计用类CC++语言或用框图描述)、测试用例设计;

3。 调试报告

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

4 经验和体会包括对算法改进的设想

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

说明:

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

 。 凡拷贝往年任务书或课程设计充数者,成绩一律无效 以分记.

时间安排:

1第17周完成,验收时间由指导教师指定

2验收地点实验中心

3验收内容可执行程序与源代码、课程设计报告书。

指导教师签名 2 13年月1日

系主任或责任教师)签名 年 月 日

数据结构课程设计

—-按层次遍历二叉树

1问题描述及要求

 。 1问题描述

编写按层次顺序(同一层自左至右)遍历二叉树的算法,并将二叉树按指定格式输出。 (题集 4面题6。 69所指定的格式指定格式如下

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

图一指定输出格式

 .2任务要求

编写按层次顺序同一层自左至右遍历二叉树的算法.

1二叉树采用二叉链表作为存储结构。

2按题集44面题6。 69所指定的格式输出建立的二叉树。

(3输出层次遍历结果。

4测试用例自己设计.

2开发平台及所使用软件

Wnos 7.   Visual Su o010

3 程序设计思路

 。 二叉树存储结构设计strc  inTreeNode //二叉树用二叉链表存储

{c har ata //二叉树结点值为字符型

B in eeNde le fthild; //左孩子指针

B T eeod   igh hi d; //右孩子指针

}

3。 2题目算法设计

3.2 1 建立二叉树void BinT ee  cr atB nTre      ream in BinT e Nod 

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

//通过输入流in建立二叉树

char  tmc in get(ite m);

if(i  em!=  

sure=new B inTreeNde   t

craB inr  in,subr >l tc hil 

retB inT e i ub Tee—r  htc hi d);

}

els

{

u ee=NULL



 ;

3。  。 2遍历二叉树vo i BiTr  e :le    rder Bi r  eode* sb Tr  e/按层次序遍历二叉树

que ue<B inre eN   q

inTreNo  *psub Tee;q.push(p

hile   q。 empty )) //若树非空{

 p=q。 ro nt   cut< 〈vis it(p) 〈" " /输出队头元素q pop )

i p—〉 le ftc hil  =N UL q.p us h p—〉  e ftc hil  ;} //左子树非空入队

ifp-〉  igtc h ld =NL) q。 p uh(p—〉 rig  c hi d ;





3。 3.3按要求格式输出已建立的二叉树

 oi  rin  _B inTr   ( iT   eN od   T   e,int  //按要求格式输出已建立的二叉树i表示结点所在层次。初始=



B inTreeNde*p=Tree

  f p> ihthild   int_  Te Tre e—〉  ightcild,i+1

/递归函数

fo int j=1;j<=  j+ cot 〈<” ” /打

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

印i个空格表示层次c o ut 〈p—>d aa<e l;

if —〉  e fthild PrintBnTree r e—〉   f h d i+1}

3.3 测试程序

测试二叉树

如图所示二叉树按先序遍历顺序输入,AB##CE###。其中””代表空格,二叉树是 A为根节点 A左孩子是B,右孩子是C B的左孩子为空,右孩子为D 的左孩子为右孩子为空 E的左孩子为空,右孩子为F.根据以下程序运行结果(见图4)可知,程序正确运行。

若输入AB#DCEF#则程序出现错误不能运行.(见图34调试报告

1、在建立二叉树时输入的格式一定要正确没有孩子的要用空格表示在测试用例中 F没有孩子,要用两个空格表示如果输入“BDE"则没有输出结果.

2、起初编写输出程序vid rint_inTee(B inreeN ode Tr e,in i))的时候,始终显示编译无错误,但是不能运行出现了一堆有关内存分配错误的问题.最后发现没有将指针指向结点。经改正,运行成功。

 经验和体会

本程序的建立和遍历二叉树的程序都比较简单,关键在于按要求打印二叉树。起初一直找不到合适的方法按题目要求打印二叉树在和同学讨论了很久之后终于有了思路。在调试程序的时候也出现了问题,起初没有在意输入方式对程序运行结果的影响导致程序无法运行在检查了很久之后终于找到了问题的所在对输入进行了改正得到了正确的结果.

除此之外,编写C+程序的过程中指针时钟是个难点也是个重点今后要多练习多理解才行。

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

6源程序清单及运行结果

6 1源程序清单

inc lude 〈ios  ram〉

in lud 〈qeu>

s in nasp ae  td;s  ructinTeeNo  /定义结构体

char  ta;

  reN oe*  etcild;

B inTreeoe*rihtc hild

B inTreeNode(  :  e   c hi  d(NULL  rightc hild NULL  

/结构体可以有构造函数

BinT  ode i x BnreeNoe*lULL,B re erNULL : ta( ,letc  l    rightc hil(r  



  a s inTree



  iva te

B inTreeNde*r   pub ic

B ire ( ro o (ULL { /构造函数,构造一棵空的二叉树

BnTreeNode*gtrot(){rtun rot 

BnTree const  nTr s //复制构造函数

~B inTre e    es tro yroot);} //析构函数  o    estr     inT  eeNod    u  Tre   

/删除

o i c  eatB iTree is  rei  nTre eNode &uTree ;

/从文件读入建树

riend istramoperatr〉 (  strem   BinTre Tr  

//重载操作输入

  id l  ve    de    inTreeod   subTree);

/层次序遍历char visit iTreeN  ep {  e  u n p—〉 d  ta  

//取值

istr  a m& p er ato >〉  i   r  m&  n inT e  Tre  )

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

/重载操作:输入并建立一棵二叉树.in是输入流对象



Tre e c ret B in   e in re 。 ro o 

retur n n

vo id inT e :cre Binreeist  mi,BinTreeNodsub Tree) /从输入流in输入二叉树表示建立对应的二叉链表

c r item

c   get(item)

  f  te m =’ ')

sub Tree=nw BinTeeNo  it ;

 reaB ir   n,sb Tree—〉  e ftch ld

 rea  nTre in s ub Tre—〉 rightc hil 

els

 suTreeNUL



}

o  iTee :leve Order inTeeNode ub Tree)

qu e 〈Bin eede *

inreo dp=ub Tre eq push p

while( q epty    队列不空

 p=q frn   o  〈<v si  p)<<” ”

q。 pp  if p->le f ch  ld!=NUL){q ps(p-> e  tch     ; 

 左子女进队

if(p—〉 r  gtc hi d!=UL){q.ps hp—>rightc hil)  右子女进队

}

};

V id BinT  e      stroy(B    reeNode   ub  ree 

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

/释放空间

if(subTre  NUL

 

 s  r (s Tree ef chi  )

de   roy sub Tre e〉 rig  c h ld

delete ub Tre e;



}voi  P  int_BinTree     Tre     e Tree    t i 

//按要求输出二叉树,i表示结点所在层次初次调用为0{

 nre eoe*p=re if(-> ightc hild ri _i ee Tr rigthild,i+1 ;for it =  j 〈=i j++ cou< ” //打印i个空格表示层次cut 〈 〈p-〉 d ataed l /打印元素,换行

ifp->l f chi    P in_B inTree Tee〉 le ftc hil,i+ )

}int min(

{

BinTree Tree;int a;in =0cout 〈<”请按照前序遍历的方法,输入初始值每段空格结束  〈 〈e nd lc  〉 〉  ee

B inreeN   *p=Tre e。 e ro ot  

cou 〈endl;

 out< 〈"层序遍历为” 〈ed ;

Tee l elOder(  ;

coted 

 ut 〈”按树形打印输出二叉树”<<edl

rininTree(,i)

cin>a;ret n 0;

