树和二叉树实验报告

树和二叉树一、实验目的1掌握二叉树的结构特征，以及各种存储结构的特点及适用范围。2掌握用指针类型描述、访问和处理二叉树的运算。二、实验要求1认真阅读和掌握本实验的程序。2上机运行本程序。3保存和打印出程序的运行结果，并结合程序进行分析。4按照二叉树的操作需要，重新改写主程序并运行，打印出文件清单和运行结果。三、实验内容1输入字符序列，建立二叉链表。2按先序、中序和后序遍历二叉树（递归算法）。3按某种形式输出整棵二叉树。4求二叉树的高度。5求二叉树的叶节点个数。6交换二叉树的左右子树。7借助队列实现二叉树的层次遍历。8在主函数中设计一个简单的菜单，分别调试上述算法。为了实现对二叉树的有关操作，首先要在计算机中建立所需的二叉树。建立二叉树有各种不同的方法。一种方法是利用二叉树的性质5来建立二叉树，输入数据时要将节点的序号（按满二叉树编号）和数据同时给出（序号，数据元素0）。另一种方法是主教材中介绍的方法，这是一个递归方法，与先序遍历有点相似。数据的组织是先序的顺序，但是另有特点，当某结点的某孩子为空时以字符“”来充当，也要输入。若当前数据不为“”，则申请一个结点存入当前数据。递归调用建立函数，建立当前结点的左右子树。4、解题思路1、先序遍历访问根结点，先序遍历左子树，先序遍历右子树1232、中序遍历中序遍历左子树，访问根结点，中序遍历右子树1233、后序遍历后序遍历左子树，后序遍历右子树，访问根结点1234、层次遍历算法采用一个队列Q，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进后出，所以能够达到按层次遍历二叉树的目的。五、程序清单INCLUDEINCLUDEDEFINEM100TYPEDEFCHARETYPE/定义二叉树结点值的类型为字符型TYPEDEFSTRUCTBITNODE/树结点结构ETYPEDATASTRUCTBITNODELCH,RCHBITNODE,BITREEBITREEQUEMINTFRONT0,REAR0/函数原型声明BITNODECREAT_BT1BITNODECREAT_BT2VOIDPREORDERBITNODEPVOIDINORDERBITNODEPVOIDPOSTORDERBITNODEPVOIDENQUEUEBITREEBITREEDELQUEUEVOIDLEVORDERBITREEINTTREEDEPTHBITREEVOIDPRTBTREEBITREE,INTVOIDEXCHANGEBITREEINTLEAFCOUNTBITREEVOIDPAINTLEAFBITREEBITNODETINTCOUNT0/主函数VOIDMAINCHARCHINTKDOPRINTF“NNN“PRINTF“N主菜单“PRINTF“NN1建立二叉树方法1“PRINTF“NN2建立二叉树方法2“PRINTF“NN3先序递归遍历二叉树“PRINTF“NN4中序递归遍历二叉树“PRINTF“NN5后序递归遍历二叉树“PRINTF“NN6层次遍历二叉树“PRINTF“NN7计算二叉树的高度“PRINTF“NN8计算二叉树中叶结点个数“PRINTF“NN9交换二叉树的左右子树“PRINTF“NN10打印二叉树“PRINTF“NN0结束程序运行“PRINTF“N“PRINTF“N请输入您的选择0,1,2,3,4,5,6,7,8,9,10“SCANF“D“,SWITCHKCASE1TCREAT_BT1BREAK/调用性质5建立二叉树算法CASE2PRINTF“N请输入二叉树各结点值“FFLUSHSTDINTCREAT_BT2BREAK/调用递归建立二叉树算法CASE3IFTPRINTF“先序遍历二叉树“PREORDERTPRINTF“N“ELSEPRINTF“二叉树为空N“BREAKCASE4IFTPRINTF“中序遍历二叉树“INORDERTPRINTF“N“ELSEPRINTF“二叉树为空N“BREAKCASE5IFTPRINTF“后序遍历二叉树“POSTORDERTPRINTF“N“ELSEPRINTF“二叉树为空N“BREAKCASE6IFTPRINTF“层次遍历二叉树“LEVORDERTPRINTF“N“ELSEPRINTF“二叉树为空N“BREAKCASE7IFTPRINTF“二叉树的高度为D“,TREEDEPTHTPRINTF“N“ELSEPRINTF“二叉树为空N“BREAKCASE8IFTPRINTF“二叉树的叶子结点数为DN“,LEAFCOUNTTPRINTF“二叉树的叶结点为“PAINTLEAFTPRINTF“N“ELSEPRINTF“二叉树为空N“BREAKCASE9IFTPRINTF“交换二叉树的左右子树N“EXCHANGETPRTBTREET,0PRINTF“N“ELSEPRINTF“二叉树为空N“BREAKCASE10IFTPRINTF“逆时针旋转90度输出的二叉树N“PRTBTREET,0PRINTF“N“ELSEPRINTF“二叉树为空N“BREAKCASE0EXIT0/SWITCHWHILEK1PLCHNULLPRCHNULLVIPIFI1TP/序号为1的结点是根ELSEJI/2IFI20VJLCHP/序号为偶数，作为左孩子ELSEVJRCHP/序号为奇数，作为右孩子PRINTF“N请继续输入二叉树各结点的编号和对应的值“SCANF“D,C“,RETURNT/CREAT_BT1/模仿先序递归遍历方法，建立二叉树BITNODECREAT_BT2BITNODETETYPEESCANF“C“,IFETNULL/对于值，不分配新结点ELSETBITNODEMALLOCSIZEOFBITNODETDATAETLCHCREAT_BT2/左孩子获得新指针值TRCHCREAT_BT2/右孩子获得新指针值RETURNT/CREAT_BT2/先序递归遍历二叉树VOIDPREORDERBITNODEPIFPPRINTF“3C“,PDATAPREORDERPLCHPREORDERPRCH/PREORDER/中序递归遍历二叉树VOIDINORDERBITNODEPIFPINORDERPLCHPRINTF“3C“,PDATAINORDERPRCH/INORDER/后序递归遍历二叉树VOIDPOSTORDERBITNODEPIFPPOSTORDERPLCHPOSTORDERPRCHPRINTF“3C“,PDATA/POSTORDERVOIDENQUEUEBITREETIFFRONTREAR1MREARREAR1MQUEREARTBITREEDELQUEUEIFFRONTREARRETURNNULLFRONTFRONT1MRETURNQUEFRONTVOIDLEVORDERBITREET/层次遍历二叉树BITREEPIFTENQUEUETWHILEFRONTREARPDELQUEUEPRINTF“3D“,PDATAIFPLCHNULLENQUEUEPLCHIFPRCHNULLENQUEUEPRCHINTTREEDEPTHBITREEBT/计算二叉树的高度INTHL,HR,MAXIFBTNULLHLTREEDEPTHBTLCHHRTREEDEPTHBTRCHMAXHLHRHLHRRETURNMAX1ELSERETURN0VOIDPRTBTREEBITREEBT,INTLEVEL/逆时针旋转90度输出二叉树树形INTJIFBTPRTBTREEBTRCH,LEVEL1FORJ0JDATAPRTBTREEBTLCH,LEVEL1VOIDEXCHANGEBITREEBT/交换二叉树左右子树BITREEPIFBTPBTLCHBTLCHBTRCHBTRCHPEXCHANGEBTLCHEXCHANGEBTRCHINTLEAFCOUNTBITREEBT/计算叶结点数IFBTNULLLEAFCOUNTBTLCHLEAFCOUNTBTRCHIFBTLCHNULLRETURNCOUNTVOIDPAINTLEAFBITREEBT/输出叶结点IFBTNULLIFBTLCHNULLPAINTLEAFBTLCHPAINTLEAFBTRCH图112所示二叉树的输入数据顺序应该是ABDGCEHF。图112二叉树示意图运行结果主菜单1建立二叉树方法12建立二叉树方法23先序递归遍历二叉树4中序递归遍历二叉树5后序递归遍历二叉树6层次遍历二叉树7计算二叉树的高度8计算二叉树中叶结点个数9交换二叉树的左右子树10打印二叉树0结束程序运行请输入您的选择0,1,2,3,4,5,6,7,8,9,101请输入二叉树各结点的编号和对应的值（如1，A）1，A请继续输入二叉树各结点的编号和对应的值2，B请继续输入二叉树各结点的编号和对应的值3，C请继续输入二叉树各结点的编号和对应的值4，D请继续输入二叉树各结点的编号和对应的值6，E请继续输入二叉树各结点的编号和对应的值7，F请继续输入二叉树各结点的编号和对应的值9，G请继续输入二叉树各结点的编号和对应的值13，H请继续输入二叉树各结点的编号和对应的值0，主菜单“1建立二叉树方法12建立二叉树方法23先序递归遍历二叉树4中序递归遍历二叉树5后序递归遍历二叉树6层次遍历二叉树7计算二叉树的高度8计算二叉树中叶结点个数9交换二叉树的左右子树10打印二叉树0结束程序运行请输入您的选择0,1,2,3,4,5,6,7,8,9,103先序遍历二叉树ABDGCEHF主菜单“1建立二叉树方法12建立二叉树方法23先序递归遍历二叉树4中序递归遍历二叉树5后序递归遍历二叉树6层次遍历二叉树7计算二叉树的高度8计算二叉树中叶结点个数9交换二叉树的左右子树10打印二叉树0结束程序运行请输入您的选择0,1,2,3,4,5,6,7,8,9,104中序遍历二叉树DGBAEHCF主菜单“1建立二叉树方法12建立二叉树方法23先序递归遍历二叉树4中序递归遍历二叉树5后序递归遍历二叉树6层次遍历二叉树7计算二叉树的高度8计算二叉树中叶结点个数9交换二叉树的左右子树10打印二叉树0结束程序运行请输入您的选择0,1,2,3,4,5,6,7,8,9,105后序遍历二叉树GDBHEFCA主菜单“1建立二叉树方法12建立二叉树方法23先序递归遍历二叉树4中序递归遍历二叉树5后序递归遍历二叉树6层次遍历二叉树7计算二叉树的高度8计算二叉树中叶结点个数9交换二叉树的左右子树10打印二叉树0结束程序运行请输入您的选择0,1,2,3,4,5,6,7,8,9,106层次遍历二叉树979899100101102103104主菜单“1建立二叉树方法12建立二叉树方法23先序递归遍历二叉树4中序递归遍历二叉树5后序递归遍历二叉树6层次遍历二叉树7计算二叉树的高度8计算二叉树中叶结点个数9交换二叉树的左右子树10打印二叉树0结束程序运行请输入您的选择0,1,2,3,4,5,6,7,8,9,107二叉树的高度为4主菜单“1建立二叉树方法12建立二叉树方法23先序递归遍历二叉树4中序递归遍历二叉树5后序递归遍历二叉树6层次遍历二叉树7计算二叉树的高度8计算二叉树中叶结点个数9交换二叉树的左右子树10打印二叉树0结束程序运行请输入您的选择0,1,2,3,4,5,6,7,8,9,108二叉树的叶子结点数为3二叉树的叶结点为GHF主菜单“1建立二叉树方法12建立二叉树方法23先序递归遍历二叉树4中序递归遍历二叉树5后序递归遍历二叉树6层次遍历二叉树7计算二叉树的高度8计算二叉树中叶结点个数9交换二叉树的左右子树10打印二叉树0结束程序运行请输入您的选择0,1,2,3,4,5,6,7,8,9,109交换二叉树的左右子树DGBAEHCF主菜单“1建立二叉树方法12建立二叉树方法23先序递归遍历二叉树4中序递归遍历二叉树5后序递归遍历二叉树6层次遍历二叉树7计算二叉树的高度8计算二叉树中叶结点个数9交换二叉树的左右子树10打印二叉树0结束程序运行请输入您的选择0,1,2,3,4,5,6,7,8,9,1010逆时针旋转90度输出的二叉树DGBAEHCF主菜单“1建立二叉树方法12建立二叉树方法23先序递归遍历二叉树4中序递归遍历二叉树5后序递归遍历二叉树6层次遍历二叉树7计算二叉树的高度8计算二叉树中叶结点个数9交换二叉树的左右子树10打印二叉树0结束程序运行请输入您的选择0,1,2,3,4,5,6,7,8,9,102请输入二叉树各结点值ABDGCEHF主菜单“1建立二叉树方法12建立二叉树方法23先序递归遍历二叉树4中序递归遍历二