数据结构实验报告3.docx
青岛理工大学数据结构课程实验报告课程名称数据结构班级计算121实验日期姓名容康宁学号201207026实验成绩实验名称实验三二叉树基本操作实验目的及要求实验目的：1 .熟悉二叉树结点的结构和对二叉树的基本操作。2 .掌握对二叉树每一种操作的具体实现。3 .学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。实验环境硬件平台：计算机软件平台：win7编程环境：vc6.0实验内容实验内容该程序的功能是实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。定义DataType为char类型typedefcharDataType;二叉树的结点类型typedefstructBitNode(DataTypedata;structBitNode*IchiId,*rchi1d;BitNoder*BitTree;初始化二叉树，即把树根指针置空voidBinTreeInit(BitTree*BT)按先序次序建立一个二叉树voidBinTreeCreat(BitTree*BT)检查二叉树是否为空intBinTreeEmpty(BitTree*BT)按任一种遍历次序(包括按先序、中序、后序、按层次)输出二叉树中的所有结点voidBinTraverse(BitTree*BT)求二叉树的深度intBinTreeDepth(BitTreeBT)求二叉树中所有结点数intBinTreeCount(BitTreeBT)清除二叉树，使之变为空树voidBinTreeC1ear(BitTree*BT)算法描述及实验步骤定义DataTyPe为char类型tyedefcharDataType;二叉树的结点类型typedefstructBitNode(DataTypedata;structBitNode*1chi1d,*rchi1d;JBitNodez*BitTree;基本操作的算法：初始化二叉树，即把树根指针置空voidBinTreeInit(BitTree&T)(T=NU11;按先序次序建立一个二叉树intBinTreeCreat(BitTree&T)charch;scanf(',%c"ch);+getchar();if(ch=,)T=NU11;e1se(if(!(T=(BitNode*)ma11oc(sizeof(BiNode)return(OVERF1OW);T->data=ch;BinTreeCreat(T->1chi1d);BinTreeCreat(T->rchi1d);returnOK;)检查二叉树是否为空intBinTreeEmpty(BitTree&T)(if(!T)return1;e1sereturnO;)先序输出二叉树中的所有结点intBinTraverse(BitTree&T)if(T)Printf(t4%c,T->data);if(BinTraverse(T->1chi1d)if(BinTraverse(T->rchi1d)returnOK;returnERROR;Ie1sereturnOK;求二叉树的深度inidepth(BitTree&T)inidepthva1,m,n;if(!T)(dethva1=O;e1se(m=deih(T->1chi1d);n=depth(T->rchi1d);dethva1=1+(m>n?m:n);returndepthva1;求二叉树中所有结点数intBinTreeCount(BitTree&T)(if(!T)return();e1seBinTreeCount(T->1chi1d);m+;BinTreeCount(T->rchi1d);Ireturnm;*T=NU11;清除二叉树，使之变为空树voidBinTreeC1ear(BitTree*T)(调试过程及实验结果r3c+目宪章氨二叉NDWbUg1exe1：A1：Bi：c1：D1：E:ABCDE;ocontinue造频入道腕入;造型人;-ijigiifwA;请雕卜非空1-rr、白除度为节点数如小:主2伊U彳月工JPress<JdJdIdJ、-/t点点点点点点点点点点点出y乡乡乡乡乡乡乡乡乡乡乡早kuh、Jvh、MVA1IJJ“vh、Vh、VrV5fII匕二1t二JJI】fII,/ifI1IfII-131a一、一、一、一、一、->、rTJX-T仪或成成双呼机引项成秋炉：a总结实验过程中，我们通过二叉树的创建，了解到在输入二叉树的结点值时该使用什么样的格式输入，在输入后要把最后一个空格去掉。在计算树的深度是，我们可以先计算出左子树和右子树的各自的深度，然后进行比较，其中最大值就是该树的深度。树的遍历有三种：先序遍历（先根后左再右），中序遍历（先左后根再右），后序遍历（先左后右在根）。在遍历的过程中可以对数的结点计数，每遍历个节点，节点数加，等遍历完成时就可以算出树的结点数。空树的创建只需要让树的根结点的指针为空，在进行树的销毁时同样清空树的根节点。实验中，我们可以通过程序的编写，熟悉树的基本操作。从错误中学会学习过程中的问题。附录inc1ude<stdio.h>inc1ude<ma11oc.h>WefineOK1WefineOVERF1OW-1WefineERROR0ypedefcharDataType;ypedefstructBitNodeDataTypedata;structBitNode*1chi1d,*rchi1d:BitNodet151BitTree;oidBinTreeInit(BitTree&T)(m=depth(T->Ichi1d);n=depth(T->rchi1d);depthva1=1+(m>n?m:n);)returndepthva1;)intm;intBinTreeCount(BitTree&T)(if(!T)return0;)e1serT=NU11;ntBinTreeCreat(BitTree&T)tBinTreeCount(T->1chi1d);m+;BinTreeCount(T->rchi1d);charch;PrinIf("请输入树的结点值:")；scanf("%c",&ch);getchar();)returnm;)voidBinTreeC1ear(BitTree*T)if(ch=',)T=NU11;e1se(if(!(T=(BitNode*)ma1IoC(SiZeof(BitNOde)return(OVERF1OW);T->data=ch;BinTreeCreat(T->1chi1d);BinTreeCreat(T->rchi1d);returnOK;intBinTreeEmpty(BitTree&T)(if(!T)return1;e1sereturnO;)intBinTraverseCBitTree&T)(if(T)printf(',%c",T->data);if(BinTraverse(T->1chi1d)if(BinTraverse(T->rchi1d)returnOK;returnERROR;e1sereturnOK;)intdepth(BitTree&T)intdepthva1,m,n;if(!T)depthva1=O;e1se(*T=NU11;voidmain()inta,b;m=0;BitTreet;BinTreeInit(t);PrinIf("输入树:n");BinTreeCreat(t);if(BinTreeEmpty(t)printf("t为空n");Ie1seprintf("t非空n");IPrinIf("先序遍历的输出为:")；BinTraverse(C);printf,("n');a=depth(t);PrinIfr深度为:%dn",a);b=BinTreeCount(t);PrinIf("节点数为:dn",b);BinTreeC1ear(At);if(BinTreeEmpty(t)PrinIf("树清空成功!n");Ie1sePrinIf("树清空失败!n");I)
