2023年数据结构二叉树操作实验报告

数据结构一实验报告指导教师xX实验时间：指23年1月L日学院计算机学院专业信息安全班级XXXXXX学号XXXXX姓名XX实验室S331实验题目:二叉树操作实验规定：采用二叉树链表作为存储结构，完毕二叉树的建立,先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。示例程序：include"stdio.h〃include〃string.h〃defineMax20〃结点的最大个数typedefstructnode{chardata;structnode*lchild,child;}BinTNode；〃自定义二叉树的结点类型typedefBinTNode*BinTree;〃定义二叉树的指针intNodeNum,leaf;〃NodeNum为结点数，leaf为叶子数〃=======基于先序遍历算法仓ij建二叉树二=========//二二=二=规定输入先序序列，其中加入虚结点以示空指针的位置=======BinTreeCreatBinTree(void)if(p->lchild!=NULL){rear=(rear+1)%NodeNum;cq[rear]=p->lchild;//左子树入队°}^if(p—>rchi1d!=NULL){。rear=(rear+1)%NodeNum；ocq[rear]=p—>rchild;//右子树入队))}I/==========主函数================voidmain()(BinTreeroot;inti,depth;printf("\n")；printf(nCreatBin_Tree；Inputpreorder:")；〃输入完全二叉树的先序序列,〃用#代表虚结点，如ABD###CE##F##root=CreatBinTree();〃创建二叉树，返回根结点do{〃从菜单中选择遍历方式，输入序号。ooprintf(M\t**********select************\n")；printf(n\t1：PreorderTraversal\nn)；oprintf(n\t2:lorderTraversa1\nH);。printf(H\t3：Postordertraversa1\n”);^printf(n\t4:PostTreeDepth,Nodenumber,Leafnumber\nn);oprintfC'\t5:Leve1Depth\n”);//按层次遍历之前，先选择4,求出该树的结点数。oprintf(n\tO：Exit\nH)；°6printf(、*******************************\n")•scanfC%dn,&i);//输入菜单序号(0—5)switch(i){。。case1:printf(nPrintBin_treePreorder：")；reorder(root)；//先序遍历3break;case2:printf(nPrintBin_TreeInorder:n);Inorder(root);〃中序遍历^break;。case3：printf(nPrintBin_TreePostorder:");。Postorder(root);〃后序遍历?break;case4:depth=TreeDepth(root)；//求树的深度及叶子数。printf(nBinTreeDepth=%dBinTreeNodenumber=%d”，depth,NodeNum);printf(nBinTreeLeafnumber=%cT,leaf)；obreak;case5:printf(nLevePrintBin_Tree:")；Ievelorder(root);//按层次遍历。break;adefau1t:exit(l);printf(n\nn)；}while(i!=0);

程序结果:・D:\C语言编的程序\Debug\Cppl.exe”CreatBin_Tree；Inputpreorder：ABDttttttCEItttFttttxxxxxxxxxxselectxxxxxxxxxxxx1：PreorderTraversal2：IorderTraversal3：Postordertraversal4：PostTreeDepth,Nodenumber..Leafnumber5：LeuelDepth0：Exit1PrintBin_treePreorder：ABDCEFxxxxxxxxxxselectxxxxxxxxwx1：PreorderTraversal2：IorderTraversal3：Postordertrauersal4：PostTreeDepthj.Nodenumber,Leafnumber5：LeuelDepth0：ExitrintBin_TreeInorder：DBAECF**********selectx—射射射射射射射射22Print2Print3c语言编的程序\Debug\Cppl.exe”2Print1:2：4：0：PreorderTrauersalIorderTrauersalPostordertrauersalPostTreeDepth,Nodenumber..LeafnunberLeuelDepthExit3PrintBin_TreePostorder：DBEFCAxxxxxxxxxxselectxxxxxxxxxxxx1：1:2：4：0：PreorderTrauersalIorderTrauersalPostordertrauersalPostTreeDepth,Nodenumber..LeafnunberLeuelDepthExit3PrintBin_TreePostorder：DBEFCAxxxxxxxxxxselectxxxxxxxxxxxx1：2：3：4：0：PreorderTrauersalIorderTrauersalPostordertrauersalPostTreeDepthj-Nodenumber..LeafnumberLeuelDepthExitXXXXXXXMXXXX-XXXXXXXXXXXXXMMX4BinTreeDepth=3BinTreeNodenunber=6BinTreeLeafnumber=3MMXMXXXMMMSClectMXMXXXXMMXMM1：PreorderTrauersal,D:\CiBB^K®?\Debug\Cppl.exeHBinTreeDepth=3BinTreeNodenumber=6BinTreeLeafnunber=3xxxxxxxxxxselectxxxxxxxxxxxx1：2：3：4：0：PreorderTrauersalIorderTraversalPostordertraversalPostTreeDepth,NodenumberLeafnumberLeuelDepthExitMXMXXMXXMXXMXMMXMXXMMMXXMXXMXXX5,D:\CiBB^K®?\Debug\Cppl.exeHBinTreeDepth=3BinTreeNodenumber=6BinTreeLeafnunber=3xxxxxxxxxxselectxxxxxxxxxxxx1：2：3：4：0：PreorderTrauersalIorderTraversalPostordertraversalPostTreeDepth,NodenumberLeafnumberLeuelDepthExitMXMXXMXXMXXMXMMXMXXMMMXXMXXMXXX5LeuePrintBin_Tree：ABCDEF**********select************1：2：3：4：0：PreorderTraversalIorderTraversalPostordertrauersalPostTreeDepth,Nodenumber..LeafnumberLeuelDepthExitMXMMXMX-XXMMMXXXM-XXXMXMXXM6Pressanykeytocontinue二叉树及后序遍历（虚线途径）心得体会:通过本次实验，我纯熟了二叉树先序、中序和后序三种遍历，不仅是程序的编写，尚有二叉树的绘制。BinTreeT;charch;if((ch=getchar())=='#')return(NULL)；〃读入#，返回空指针else{°T二(BinTNode*)malloc(sizeof(BinTNode))；生成结点^T->data=ch;qT—>1child=CreatBinTree()；//构造左子树oT-〉rchi1d=CreatBinTree();〃构造右子树return(T);})//========NLR先序遍历==========voidPreorder(BinTreeT)(if⑴{8Printf(〃％c〃，T—>data);〃访问结点oPreorder(T->lchi1d);〃先序遍历左子树Preorder(T->rchild);//先序遍历右子树})LNR中序遍历==========//==========LRN后序遍历==========采用后序遍历求二叉树的深度、结点数及叶子数的递归算法==intTreeDepth(BinTreeT)inth1,hr,max；if(T){hl=TreeDepth(T->1chi1d);“/求左深度。hr=TreeDepth(T->rchild);//求右深度max=hl>hr?hl:hr;〃取左右深度的最大值NodeNum=NodeNu1；〃求结点数if(hl==0&&hr==0)leaf=leaf+1;//若左右深度为0,即为叶子。return(max+l);)elsereturn(0)；)〃====运用"先进先出"(FIFO)队列，按层次遍历二叉树========voidLevelorder(BinTreeT)(intfront=0,rear=l;BinTNode*cq[Max],*p;//定义结点的指针数组cqcqL1]=T;//根入队while(front!=rear){gfront=(front+l)%NodeNum;。p=cq[front]；〃出队。printf(”％c〃，p->data);//出队，输出结点的值sif(p->lchi1d!=NULL){3rear=(rear+1)%NodeNum;////左子树入队//左子树入队cq[rear]=p->lchild；//左子树入队。if(p->rchiId!=NULL){rear二(rear+1)%NodeNum;]=p—>rchi1d;〃右子树入队voidmain()]=p—>rchi1d;〃右子树入队BinTreeroot；inti,depth；printf(〃\n〃)；printf(〃CreatBinTree;Inputpreorder:〃)；〃输入完全二叉树的先序序列，//用#代表虚结点，如ABD###CE##F##root=CreatBinTree();〃创建二叉树，返回根结点do{//从菜单中选择遍历方式,输入序号。oprintf(〃\t**********seiect************\nn);printf(〃\tl:PreorderTraversa1\n〃);mprinIorderTraversa1\n〃)；oprintf(”\t3:Postordertraversal\n〃)；叩rintf(n\t4:PostTreeDePth,Nodenumber,Leafnumber\n〃)；printfC\t5:LevelDepth\n〃);〃按层次遍历之前,先选择4,求出该树的结点数。叩rintf(n\t0:Exit\n");printf(〃\t*******************************\n〃);scanfC%dn,&i);//输入菜单序号(0-5)switch(i){case1:printf(〃PrintBin_treePreorder:z，);oPreorder(root);//先序遍历obreak；3case2:printf("PrintBinTreeInorder：〃)；g^Inorder(root);〃中序遍历obreak;。case3：printf("PrintBin_TreePostorder：〃)；gPostorder(root);〃后序遍历break;case4:depthsTreeDepth(root);〃求树的深度及叶子数sprintf(〃BinTreeDepth=%dBinTreeNodenumber=%d，/,depth,NodeNum);。6printf(〃BinTreeLeafnumber-%dz，,leaf)；gbreak;wcase5:printf(〃LevePrintBin_Tree：〃)；Levelorder(root);//按层次遍历gbreak;defau1t:exit(l)；gprintf(”\n〃)；}while(i!=0);实验内容及环节：1、分析、理解程序。2、添加中序和后序遍历算法.3、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点(空指针),如ABD###CE##F##,建立二叉树，求出先序、中序和后序以及按层次遍历序列,求所有叶子及结点总数。4、画出所设计的二叉树，以后序遍历算法为例，画出执行踪迹示意图。给出实验结果。5、给出实验结果。改正后的完整程序：#includeHstdio.hn#includenstring.hn#include<malloc.h>include<stdlib.h>defineMax20//结点的最大个数typedefstructnode{chardata；structnode*Ichiid,*rchi1d；JBinTNode；//自定义二叉树的结点类型typedefBinTNode*BinTree;//定义二叉树的指针intNodeNum,leaf；//NodeNum为结点数，leaf为叶子数//=========基于先序遍历算法创建二叉树==============〃=====规定输入先序序列，其中加入虚结点"#”以示空指针的位置==========BinTreeCreatBinTree(void)BinTreeT;charch;if((ch=getchar())=='#f)return(NULL);〃读入#，返回空指针else{oT=(BinTNode*)malloc(sizeof(BinTNode));//生成结点。T->data=ch;T->1chi1d=CreatBinTree();〃构造左子树^T—>rchild=CreatBinTree();〃构造右子树6return(T);))〃========NLR先序遍历=============voidPreorder(BinTreeT){if(T){叩rintf(n%cn,T->data);〃访问结点oPreorder(T->lchiId);〃先序遍历左子树3Preorder(T->rchi1d);〃先序遍历右子树))//========LNR中序遍历=============voidInorder(BinTreeT)(if(T){gInorder(T—>lchiId);〃先序遍历左子树

printf(n%c”，T->data);〃访问结点〃访问结点〃访问结点Inorder(T—>rchi1d);〃先序遍历右子树〃访问结点))/*voidInorder(BinTreeT)。whi1e(pI|!StackEmpty(BinTreeT)){oif(T)(Push(BinTreeT,T);T=T->1child；}//根指针进栈，遍历左子树°else{〃根指针退栈，访问根节点，遍历右