北航计算机软件技术基础实验报告计软实验报告2——二叉树

北航计算机软件技术基础实验报告计软实验报告2——二叉树(正确详细版)

实验报告

实验名称二叉树

班级

学号

姓名

成绩

北航计算机软件技术基础实验报告计软实验报告2——二叉树(正确详细版)

概验述：实【验的目要及求】1. 实验目的掌握二叉树的储结存构

2.实验内 容1.给对定叉树用二式链式链储存结构；用利列与栈对队二叉进行运算。 树2.层次按输所出结有点。 3输.所出叶子结有点。4.将 有左右子所值交树。换3 实验.步和骤求1.分要编制实验别容中题内2 、34 的、个子三程。序15

986

2

010

45

0

43

600

70

2.上图以示的二所叉为树例制主程序编实，下现功能述，运并行个这序程。 1()输入二叉用树式链结存构储 (;2调用题) 的子2程序并输，结果出 (3;调用) 题3的 程序，并输出结子； (4)果用调 4题的子 序，并程输出果；结3.自 行设计棵二一叉，重树复骤步 2 4。整.理序清程与单所有结，并果写实验出告。

报4实.验原理()1叉二的链树式存储结构二叉 的每一树个结点i 有三个域：值 V域i) ,左(链 L(域i ,右链)域 Ri()。我 们分别用三个一维组表示它数，们并用头针指H B 指T二向叉的根树结点具体。 储存案由读者方行自考虑。

北航计算机软件技术基础实验报告计软实验报告2——二叉树(正确详细版)

(2按层次)出所输有点结 为达了到层次扫描结按的点目，的需要设一置个容量够足大的循队环(列可用 以个一尾首接相一维的组数模拟)。初 始，将时结根点序入号队。后然次每从队 中列出一个结退点号，序 此结点将的值及右链左指针输出且依次，此将结点的左 右指针链队。入个过这程直进行到队列空一为。设循环止队列组为 数cq(1:m), 其头尾 指分针为别f orn 与t erra,则按层次输所有出点的结法如算： 下I FBT =H0 THEN R ETUR “ NTIHS TERE IS METP”Y Frnot m, r aer m

ADD ( cq, HTB ,ront,f earr) W ILEH rfnot rearDO { DLE (c ,q ,i rofn ,trea )rOUT UT P( L i( ,)V( i ) ,R ( i ) )IFL i() THEN0 DAD(c q, L ( i, )rfno, tear) rFIR (i ) 0THEN A DD c(q ,R (i ,) frnot ,rer)a} RE UTR N这个算在法中的A D 和DDEL 分为别入和队队运退算两个的程,过其算法( 不考虑溢情出况)下如 ADD: c(,iq,roft,reanr )rare r era +1IF rar = e m 1+ HTNEre ar 1 c (qear) ri ERTRUND EL( cq, ,ifr no, terar ) rofn ftrotn +1 I fFont = r+ m 1THN Efno 1 t cqi( rfot ) REnTUN (R3输)出有所子结点叶 子结叶的点左右指针均为域。因零，为此了出输所有叶结子点需，要设一置个 容足够量的栈大S (可用一以个维数组一模拟，它栈在数底的第一组个元素)处。 体过具是：从根结点程始扫描开二叉树，果扫描如的当结前点左右均为零，的则 出输次叶结点子 ；否则将非零的右针指左和指值推针入栈。堆后然栈从退出一 中结个点序重新号行这个进过程，直栈至为空止。其法如下算： I HBFT 0=TH NE RETRUN“ HIST

TREE I EMSTY ” tPpo 0 PU HS( ,HSTBt,po)W ILE Htp o 0 D O

{P

北航计算机软件技术基础实验报告计软实验报告2——二叉树(正确详细版)

P(OS,i,tpo)I FL(i)=0) and (((Ri)0=T)ENH UTPUTO (i)VEL S E{IF R i( )0 HENT PUSH S,R(i() ,tpo) IFL () i0 TH N EPSH U(,SL(i), otp) }RE}TURN

中 其PUSH和 OP P分为别入和退栈的过程，栈其算法读者自行由虑。考 4)(所将有右子左值树交 换个这问的题处和输理所出叶子有结点的问很类似题， 只要将非子结叶的点 左指针右交换可即其，法算下如：I HFB =T 0 HETN ERTRU NT“HSI TEER SI MPTY”Eto p 0P SU (H,SHB,Topt) WIHE Lotp 0 OD { OP(SP,i,tpo)I FL(i)( 0)or (R i( ) 0 )HTNE {L ()i R (i )I F(i) L T0EH NUPSH (,L(i)S,t o) pI RFi( ) 0HEN PUTH S(,RSi() t,op)} }REUTRN 【实环境】 验使用(软硬的件)处 器理特尔 英Cre o5i-240M @ 20.50HG 双z 内存 4核 GB( 记忆 技科DDR3 L6001Hz M 操)作系 Win统dwos 10专 业版 6 位4 D(rictX e12) 编 译环 境ev-CD++5. 6. 1译语言 C

实编内验：容【验方案设计】 1.实 用一个一维利组 数dat[]来a存数放，用据两个维一组数l fteCildh和 r igtChhli 来d模二拟叉的左树右链。域建链创的方法表为结点地址左为2 *+1,i结点右地址为 2*i +。 22.用队结列构来实现按次输层各结点出。先建一个创包含据区域数、头针、尾 指针。指后然根结将加入点列。队每先弹出次头队素，判元左断子树右是否为空，如 果不空则为入队加列，直头到尾针指合。重3.用 栈结来构实现找并查出叶输子结。先点创一建个包数含区据域顶、部指的针

北航计算机软件技术基础实验报告计软实验报告2——二叉树(正确详细版)

栈，将根结点入栈。每次弹出栈顶元素，并判断左右子树的值。如果头元素中存放的结点的左/右子树不为空,则入栈，直到栈顶指针为空。

4.用栈结构来实现查找并交换子树的值。先创建一个包含数据区域、顶部指针的栈，将根结点入栈。每次弹出栈顶元素，并交换栈顶元素指向的结点的左右子树指针。如果头元素中存放的结点的左/右子树不为空,则入栈，

5.整理实验结果，写出实验报告

【实验过程】（实验步骤、记录、数据、分析）

实验一：

源代码：

/*

实验内容:

1:对给定二叉树用链式链式存储结构,利用队列与栈对二叉树进行运算。 2:按层次输出所有结点。

3:输出所有叶子结点。