北航计算机软件技术基础实验报告计软实验报告2——二叉树
发布时间：2024-11-10
北航计算机软件技术基础实验报告计软实验报告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)进(分 配，行这样以灵可活地创遍历建、找查各等方法种 。指教导评师语及绩：成
成：绩导教师指名签：批 阅期：日
北航计算机软件技术基础实验报告计软实验报告2——二叉树.doc
将本文的Word文档下载到电脑
上一篇：小学奥数 等量代换
