资源描述：
《北航计算机软件技术基础实验报告计软实验报告2——二叉树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、实验报告实验名称二叉树班级学号姓名成绩实验概述：【实验目的及要求】1.实验目的掌握二叉树的存储结构2.实验内容1．对给定二叉树用链式链式存储结构；利用队列与栈对二叉树进行运算。2．按层次输出所有结点。3．输出所有叶子结点。4．将所有左右子树值交换。3.实验步骤和要求1．分别编制实验内容中题2、3、4的三个子程序。2．以上图所示的二叉树为例编制主程序，实现下述功能，并运行这个程序。（1）输入二叉树用链式结构存储；（2）调用题2的子程序，并输出结果；（3）调用题3的子程序，并输出结果；（4）调用题4的子程序，并输出结果；3．自行设计一棵二叉树，重复步骤2。4．整理程序清单与所有结果，并
2、写出实验报告。4.实验原理（1）二叉树的链式存储结构二叉树的每一个结点i有三个域：值域V（i），左链域L（i），右链域R（i）。我们分别用三个一维数组表示它们，并用头指针HBT指向二叉树的根结点。具体存储方案由读者自行考虑。（2）按层次输出所有结点为了达到按层次扫描结点的目的，需要设置一个容量足够大的循环队列（可以用一个首尾相接的一维数组模拟）。初始时，将根结点序号入队。然后每次从队列中退出一个结点序号，将此结点的值及左右链指针输出，且依次将此结点的左右链指针入队。这个过程一直进行到队列空为止。设循环队列数组为cq（1：m），其头尾指针分别为front与rear，则按层次输出所有结
3、点的算法如下：IFHBT=0THENRETURN“THISTREEISEMPTY”Frontßm,rearßmADD(cq,HBT,front,rear)WHILEfrontrearDO{DEL(cq,i,front,rear)OUTPUT(L(i),V(i),R(i))IFL(i)0THENADD(cq,L(i),front,rear)IFR(i)0THENADD(cq,R(i),front,rear)}RETURN在这个算法中的ADD和DEL分别为入队和退队运算的两个过程,其算法(不考虑溢出情况)如下：ADD（cq，i，front，rear）rearrear+1IFrear=m
4、+1THENrear1cq（rear）iRETURNDEL(cq,i,front,rear)frontfront+1IFfront=m+1THENfont1icq(front)RETURN（3）输出所有叶子结点叶子结点的左右指针域均为零。因此，为了输出所有叶子结点，需要设置一个容量足够大的栈S（可以用一个一维数组模拟它，栈底在数组的第一个元素处）。具体过程是：从根结点开始扫描二叉树，如果扫描的当前结点的左右均为零，则输出次叶子结点；否则将非零的右指针和左指针值推入堆栈。然后从栈中退出一个结点序号重新进行这个过程，直至栈空为止。其算法如下：IFHBT=0THENRETURN“THIS
5、TREEISEMTPY”top0PUSH（S，HBT，top）WHILEtop0DO{POP（S，i，top）IF（L（i）=0）and（R（i）=0）THENOUTPUTV（i）ELSE{IFR（i）0THENPUSH（S，R（i），top）IFL（i）0THENPUSH（S，L（i），top）}}RETURN其中PUSH和POP分别为入栈和退栈的过程，其算法由读者自行考虑。（4）将所有左右子树值交换这个问题的处理和输出所有叶子结点的问题很类似，只要将非叶子结点的左右指针交换即可，其算法如下：IFHBT=0THENRETURN“THISTREEISEMPTY”top0PUSH（S
6、，HBT，top）WHILEtop0DO{POP（S，i，top）IF（L（i）0）or（R（i）0）THEN{L（i）R（i）IFL（i）0THENPUSH（S，L（i），top）IFR（i）0THENPUSH（S，R（i），top）}}RETURN【实验环境】（使用的软硬件）处理器英特尔Corei5-4200M@2.50GHz双核内存4GB(记忆科技DDR3L1600MHz)操作系统Windows10专业版64位(DirectX12)编译环境Dev-C++5.6.1编译语言C实验内容：【实验方案设计】1.利用一个一维数组data[]来存放数据，用两个一维数组leftChild和
7、rightChild来模拟二叉树的左右链域。创建链表的方法为左结点地址为2*i+1，右结点地址为2*i+2。2.用队列结构来实现按层次输出各结点。先创建一个包含数据区域、头指针、尾指针。然后将根结点加入队列。每次先弹出队头元素，判断左右子树是否为空，如果不为空则加入队列，直到头尾指针重合。3.用栈结构来实现查找并输出叶子结点。先创建一个包含数据区域、顶部指针的栈，将根结点入栈。每次弹出栈顶元素，并判断左右子树的值。如果头元素中存放的结点的左/右子树不为空,则入栈，直到
