北航计算机软件技术基础实验报告计软实验报告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:输出所有叶子结点。

4:将所有左右子树值交换。

*/

#include<stdio.h>

#include<stdlib.h>

#defineMAXSIZE 31

//定义二叉树结构体,用一维数组模拟数据域,用两个一维数组模拟左、右链域 typedefstructBinaryTree

{

int data[MAXSIZE];

int leftChild[MAXSIZE];

int rightChild[MAXSIZE];

int head;

}BTree;

int main()

{

//声明及调用相关函数

structBinaryTree initBinaryTree(structBinaryTree);

structBinaryTree createBinaryTree(structBinaryTree); void levelOrder(structBinaryTree);

void leafNode(structBinaryTree);

void exchangeBranch(structBinaryTree);

printf("Exercise 1\n");

BTree bt;

bt = initBinaryTree(bt);

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

bt = createBinaryTree(bt);

printf("A binary tree has been created!\n\n\n");

printf("Exercise 2\n");

levelOrder(bt);

printf("Exercise 3\n");

leafNode(bt);

printf("Exercise 4\n");

exchangeBranch(bt);

return 0;

}

//实验1:初始化二叉树

structBinaryTree initBinaryTree(structBinaryTreebt)

{

int i;

//数据域认为0为空,左右链域认为-1为空

for (i = 0; i<MAXSIZE; i++)

{

bt.data[i] = 0;

bt.leftChild[i] = -1;

bt.rightChild[i] = -1;

}

bt.head = -1;

returnbt;

}

//创建含有数据的二叉树

structBinaryTree createBinaryTree(structBinaryTreebt)

{

int i;

printf("Please enter all nodes:\n");

//将数据放入数据域

for (i = 0; i<MAXSIZE; i++)

scanf("%d", &bt.data[i]);

//形成链式存储

for (i = 0; i < (MAXSIZE - 1) / 2; i++)

{

if (bt.data[2 * i + 1] != 0)

bt.leftChild[i] = 2 * i + 1;

if (bt.data[2 * i + 2] != 0)

bt.rightChild[i] = 2 * i + 2;

}

bt.head = 0;

returnbt;

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

//实验2:按层次输出各节点

void levelOrder(structBinaryTreebt)

{

//创建一个空队列,包含存放二叉树结点地址的一维数组和头尾指针 int queue[MAXSIZE];

int front = -1, rear = -1, i = bt.head;

int addQueue(int[MAXSIZE], int, int);

int delQueue(int);

//判定二叉树是否为空

if (i == -1)

printf("This tree is empty!Please create one!"); //根结点入队

rear = addQueue(queue, i, rear);

printf("All existed nodes are as follows:\n");

//当队列不为空时(队列不满的前提下)

while (front != rear)

{

//头元素出队,并将其中地址值赋给i

front = delQueue(front);

i = queue[front];

printf("%d ", bt.data[i]);

//如果头元素中存放的结点的左/右子树不为空,则入队

if (bt.leftChild[i] != -1)

rear = addQueue(queue, bt.leftChild[i], rear); if (bt.rightChild[i] != -1)

rear = addQueue(queue, bt.rightChild[i], rear); }

printf("\n\n\n");

}

//元素入队

int addQueue(intqueue[MAXSIZE], inti, intrear)

{

rear++;

//循环队列指针处理方法

if (rear == MAXSIZE) rear = 0;

queue[rear] = i;

returnrear;

}

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

//元素出队

int delQueue(intfront)

{

front++;

//循环队列指针处理方法

if (front == MAXSIZE) front = 0;

returnfront;

}

//实验3:查找所有叶子结点

void leafNode(structBinaryTreebt)

{

//新建一个空栈,包含存放二叉树结点地址的一维数组和栈顶指针 int stack[MAXSIZE];

int top = -1, i = bt.head;

int pushStack(structBinaryTree, int[MAXSIZE], int, int); int popStack(int);

//判定二叉树是否为空

if (i == -1)

printf("This tree is empty!Please create one!"); //根结点入栈

top = pushStack(bt, stack, top, i);

printf("All leaf nodes are as follows:\n");

while (top != -1)

{

//栈顶元素出栈

top = popStack(top);

//取出存放的地址值

i = stack[top + 1];

//判断是否为叶子结点

if (bt.leftChild[i] == -1 &&bt.rightChild[i] == -1) printf("%d ", bt.data[i]);

//如果头元素中存放的结点的左/右子树不为空,则入栈

else

{

if (bt.rightChild[i] != -1)

top = pushStack(bt, stack, top, bt.rightChild[i]); if (bt.leftChild[i] != -1)

top = pushStack(bt, stack, top, bt.leftChild[i]); }

}

printf("\n\n\n");

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

//入栈操作

int pushStack(structBinaryTreebt, intstack[MAXSIZE], inttop, inti)

{

top++;

stack[top] = i;

returntop;

}

//出栈操作

int popStack(inttop)

{

top--;

returntop;

}

//实验4:交换左右子树的值

void exchangeBranch(structBinaryTreebt)

{

//新建一个空栈,包含存放二叉树结点地址的一维数组和栈顶指针 int stack[MAXSIZE];

int top = -1, i = bt.head, temp;

//判定二叉树是否为空

if (i == -1)

printf("This tree is empty!Please create one!"); //根结点入栈

top = pushStack(bt, stack, top, i);

printf("All branches have been changed!\n");

printf("The results are as follows:\n");

while (top != -1)

{

//栈顶元素出栈

top = popStack(top);

//取出存放的地址值

i = stack[top + 1];

//判断存放的结点的左右子树是否均不为空,是则入栈

if (bt.leftChild[i] != -1 &&bt.rightChild[i] != -1) {

top = pushStack(bt, stack, top, bt.rightChild[i]);

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

top = pusSthackb(t, sack,t otp bt.l,ftCeihd[il);] } //将有非所子结点的左叶右子指树针交换te pm =b.ltftChieldi][;b .teflChitl[di]= bt .rgithhiCl[i];db t.irgtChilhd[i]= te pm } /;/层次遍历输出换后的交叉二 l树evleOrer(btd;)} 运行结:果

从键盘(入1输 9586 02 1 0540 30 040 00 600 0 0 00 0 0 00 0 0 7000 0 00 )0实验：二

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

自行计的设叉树二下如

行结运果：

(从盘输键2入 4036 5 1 7634 02 160 0 03 101 00 612 7 00 0 0 00 0 0050 1 9)【3论结 (】结)果 1.实验 中1利一用一维个组数dat a[]存放数据，用来两一个维数 组eltChfldi和 rig tChhldi 来模二叉树拟的左右域。经链阅查料后发资现际上创实建叉树二结

构

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

多用针指成链形表形的式， 用针指的好在处使于用灵，活必事先指定大小 2不实. 验2用 列队结来构现按实次层出输结各点 这种。做法可以分利用充队的列 据数结特点，构即 FFOI 构结除。此以还可以利用外归等递方进法查询和检索行3. 实验 3 用中结栈来构现实找查并出叶子输点，结结果表明栈用实来此功能现是可 行，的的栈构结保确了点的结遍历(此在验实中是采用了中序遍历方法)的 4实验 . 中4样同是采了用栈构来实现交换结左子树右的值，实现方 法是采先用 栈行进结的遍历点，然后交 换eftlChid 和l rigtChhid 中l的值(即换交左右树子 指值) 针。实际数上的据物理储结构并存未变(改在即d tap[a]中的数顺序并 未改变据，变的改指是针的) 值【小】 结这第二是次上实验机，容是内二树叉和、栈列等队知识这。些知识大属多 数于结构范畴内据的容。 而我内之前未接触过并关相容，内此因一始看到开验报实告要求 时有点不知

所措。了为成完作业，在图书馆我借了相关阅书进籍学习，行 再结实验合求要中出的方法说给明最，终独完立代码成写编、调试输等出务，任 实验结果满四足实个验要的。 求在实验本中，二树叉主要的逻是存储结辑。在构个实这中验叉二树是以二叉 链表的式形存的，这储结构包种含三了分，数据域部左、、右孩子指针可以较 好地，刻画二叉出的树从辑逻构结，遍历在和找时查分十便。而方后面的在几实 验中个用，到了队(FIF列O和栈)(IFO)L构结在对这。种结构的运用中我两进一步熟 了悉这种两结的构特点 也，从上网和书找中并到结合二叉、树序顺等实 际练习表了这两种据数构结使的方用。法除 此之， 我外发现上网关资相多用料指针不是而维一数来模拟左组右孩指 子针用，针更灵活、更方便，指用事不先分配间，需空要再用时m allco)进(分 配，行这样以灵可活地创遍历建、找查各等方法种 。指教导评师语及绩：成

成：绩导教师指名签：批 阅期：日