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

实验报告实验名称 二叉树 班 级 学 号 姓 名 成 绩 实验概述： 【实验目的及要求】 1. 实验目的掌握二叉树的存储结构2. 实验内容1对给定二叉树用链式链式存储结构；利用队列与栈对二叉树进行运算。2按层次输出所有结点。3输出所有叶子结点。4将所有左右子树值交换。3. 实验步骤和要求1分别编制实验内容中题2、3、4的三个子程序。2以上图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序。（1）输入二叉树用链式结构存储；（2）调用题2的子程序，并输出结果；（3）调用题3的子程序，并输出结果；（4）调用题4的子程序，并输出结果；3自行设计一棵二叉树，重复步骤2。4整理程序清单与所有结果，并写出实验报告。4.实验原理（1）二叉树的链式存储结构 二叉树的每一个结点i有三个域：值域v（i），左链域l（i），右链域r（i）。我们分别用三个一维数组表示它们，并用头指针hbt指向二叉树的根结点。具体存储方案由读者自行考虑。（2）按层次输出所有结点为了达到按层次扫描结点的目的，需要设置一个容量足够大的循环队列（可以用一个首尾相接的一维数组模拟）。初始时，将根结点序号入队。然后每次从队列中退出一个结点序号，将此结点的值及左右链指针输出，且依次将此结点的左右链指针入队。这个过程一直进行到队列空为止。设循环队列数组为cq（1：m），其头尾指针分别为front与rear，则按层次输出所有结点的算法如下：if hbt = 0 then return “ this tree is empty”front m, rear madd ( cq, hbt, front, rear )while front rear dodel ( cq , i, front ,rear )output ( l( i ) , v( i ) ,r ( i )if l( i )0 then add (cq , l( i ), front, rear)if r( i )0 then add (cq , r( i ), front, rear)return在这个算法中的add和del分别为入队和退队运算的两个过程,其算法(不考虑溢出情况)如下：add （ cq，i，front，rear） rearrear + 1 if rear = m + 1 then rear 1 cq （rear） ireturndel (cq, i, front, rear ) front front + 1 if front = m+ 1 then font1 icq (front )return（3）输出所有叶子结点 叶子结点的左右指针域均为零。因此，为了输出所有叶子结点，需要设置一个容量足够大的栈s（ 可以用一个一维数组模拟它，栈底在数组的第一个元素处）。具体过程是：从根结点开始扫描二叉树，如果扫描的当前结点的左右均为零，则输出次叶子结点；否则将非零的右指针和左指针值推入堆栈。然后从栈中退出一个结点序号重新进行这个过程，直至栈空为止。其算法如下： if hbt = 0 then return “this tree is emtpy ” top 0 push （ s，hbt，top） while top 0 dopop（s，i，top）if （l（i）=0） and （r（i）=0）then output v（i）else if r（i）0 then push （s，r（i），top） if l（i）0 then push （s，l（i），top） return其中push 和pop分别为入栈和退栈的过程，其算法由读者自行考虑。（4）将所有左右子树值交换这个问题的处理和输出所有叶子结点的问题很类似，只要将非叶子结点的左右指针交换即可，其算法如下： if hbt = 0 then return “this tree is empty”top 0push （s，hbt，top）while top0 do pop（s，i，top）if （l（i）0）or （r（i）0） then l（i）r（i）if l（i）0 then push （s，l（i），top）if r（i）0 then push （s，r（i），top） return 【实验环境】（使用的软硬件） 处理器 英特尔 core i5-4200m 2.50ghz 双核 内存 4 gb ( 记忆科技 ddr3l 1600mhz )操作系统 windows 10 专业版 64位 ( directx 12 )编译环境 dev-c+ 5.6.1编译语言 c 实验内容：【实验方案设计】1. 利用一个一维数组data来存放数据，用两个一维数组leftchild和rightchild来模拟二叉树的左右链域。创建链表的方法为左结点地址为2*i+1，右结点地址为2*i+2。2.用队列结构来实现按层次输出各结点。先创建一个包含数据区域、头指针、尾指针。然后将根结点加入队列。每次先弹出队头元素，判断左右子树是否为空，如果不为空则加入队列，直到头尾指针重合。3.用栈结构来实现查找并输出叶子结点。先创建一个包含数据区域、顶部指针的栈，将根结点入栈。每次弹出栈顶元素，并判断左右子树的值。如果头元素中存放的结点的左/右子树不为空,则入栈，直到栈顶指针为空。4. 用栈结构来实现查找并交换子树的值。先创建一个包含数据区域、顶部指针的栈，将根结点入栈。每次弹出栈顶元素，并交换栈顶元素指向的结点的左右子树指针。如果头元素中存放的结点的左/右子树不为空,则入栈，直到栈顶指针为空。5.整理实验结果，写出实验报告【实验过程】（实验步骤、记录、数据、分析）实验一：源代码：/*实验内容:1:对给定二叉树用链式链式存储结构,利用队列与栈对二叉树进行运算。2:按层次输出所有结点。3:输出所有叶子结点。4:将所有左右子树值交换。*/#include#include#define maxsize 31/定义二叉树结构体,用一维数组模拟数据域,用两个一维数组模拟左、右链域typedef struct binarytreeint datamaxsize;int leftchildmaxsize;int rightchildmaxsize;int head;btree;int main()/声明及调用相关函数struct binarytree initbinarytree(struct binarytree);struct binarytree createbinarytree(struct binarytree);void levelorder(struct binarytree);void leafnode(struct binarytree);void exchangebranch(struct binarytree);printf(exercise 1n);btree bt;bt = initbinarytree(bt);bt = createbinarytree(bt);printf(a binary tree has been created!nnn);printf(exercise 2n);levelorder(bt);printf(exercise 3n);leafnode(bt);printf(exercise 4n);exchangebranch(bt);return 0;/实验1:初始化二叉树struct binarytree initbinarytree(struct binarytree bt)int i;/数据域认为0为空,左右链域认为-1为空for (i = 0; imaxsize; i+)bt.datai = 0;bt.leftchildi = -1;bt.rightchildi = -1;bt.head = -1;return bt;/创建含有数据的二叉树struct binarytree createbinarytree(struct binarytree bt)int i;printf(please enter all nodes:n);/将数据放入数据域for (i = 0; imaxsize; i+)scanf(%d, &bt.datai);/形成链式存储for (i = 0; i (maxsize - 1) / 2; i+)if (bt.data2 * i + 1 != 0)bt.leftchildi = 2 * i + 1;if (bt.data2 * i + 2 != 0)bt.rightchildi = 2 * i + 2;bt.head = 0;return bt;/实验2:按层次输出各节点void levelorder(struct binarytree bt)/创建一个空队列,包含存放二叉树结点地址的一维数组和头尾指针int queuemaxsize;int front = -1, rear = -1, i = bt.head;int addqueue(intmaxsize, 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)/头元素出队,并将其中地址值赋给ifront = delqueue(front);i = queuefront;printf(%d , bt.datai);/如果头元素中存放的结点的左/右子树不为空,则入队if (bt.leftchildi != -1)rear = addqueue(queue, bt.leftchildi, rear);if (bt.rightchildi != -1)rear = addqueue(queue, bt.rightchildi, rear);printf(nnn);/元素入队int addqueue(int queuemaxsize, int i, int rear)rear+;/循环队列指针处理方法if (rear = maxsize) rear = 0;queuerear = i;return rear;/元素出队int delqueue(int front)front+;/循环队列指针处理方法if (front = maxsize) front = 0;return front;/实验3:查找所有叶子结点void leafnode(struct binarytree bt)/新建一个空栈,包含存放二叉树结点地址的一维数组和栈顶指针int stackmaxsize;int top = -1, i = bt.head;int pushstack(struct binarytree, intmaxsize, 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 = stacktop + 1;/判断是否为叶子结点if (bt.leftchildi = -1 & bt.rightchildi = -1)printf(%d , bt.datai);/如果头元素中存放的结点的左/右子树不为空,则入栈elseif (bt.rightchildi != -1)top = pushstack(bt, stack, top, bt.rightchildi);if (bt.leftchildi != -1)top = pushstack(bt, stack, top, bt.leftchildi);printf(nnn);/入栈操作int pushstack(struct binarytree bt, int stackmaxsize, int top, int i)top+;stacktop = i;return top;/出栈操作int popstack(int top)top-;return top;/实验4:交换左右子树的值void exchangebranch(struct binarytree bt)/新建一个空栈,包含存放二叉树结点地址的一维数组和栈顶指针int stackmaxsize;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 = stacktop + 1;/判断存放的结点的左右子树是否均不为空,是则入栈if (bt.leftchildi != -1 & bt.rightchildi != -1)top = pushstack(bt, stack, top, bt.rightchildi);top = pushstack(bt, stack, top, bt.leftchildi);/将所有非叶子结点的左右子树指针交换temp = bt.leftchildi;bt.leftchildi = bt.rightchildi;bt.rightchildi = temp;/层次遍历输出交换后的二叉树levelorder(bt);运行结果：（从键盘输入 15 98 6 20 10 45 0 30 40 0 0 0 60 0 0 0 0 0 0 0 0 0 0 0 0 70 0 0 0 0 0）实验二：自行设计的二叉树如下运行结果：（从键盘输入 24 30 6 5 17 63 4 0 26 1 0 0 0 31 10 0 0 16 27 0 0 0 0 0 0 0 0 50 0 13 9）【结论】（结果）1.实验1中利用一个一维数组data来存放数据，用两个一维数组leftchild和rightchild来模拟二叉树的左右链域。经查阅资料后发现实际上创建二叉树结构多用指针形成链表的形式，用指针的好处在于使用灵活，不必事先指定大小2.实验2用队列结构来实现按层次输出各结点。这种做法可以充分利用队列的数据结构特点，即