数据结构 二叉树实验报告

一、需求分析：编写一段程序，对二叉树进行复合操作，包括创建一棵二叉树，显示二叉树的树型结构，对创建的二叉树进行先根、中根、后根三种方式进行遍历，并且打印出叶子结点，并且可以随时删除我们创建的二叉树，然后用循环语句将上述的操作封装起来，使之能够进行可重复、连续的操作。输入为a-z或者是A-Z之间的字符，用'@'字符作为结束当前结点的标识符。二、概要设计：本程序要用到的数据类型structBinTreeNode{DataTypeinfo;PBinTreeNodellink;PBinTreeNoderlink;};然后定义我们需要的指针类型typedefstructBinTreeNode*PBinTreeNode;/*定义指向二叉树结点的指针类型*/typedefPBinTreeNode*PBinTree; /*定义指向树型结点的指针类型*/程序需要用到的自定义函数.创建一个二叉树根节点PBinTreeCreate_BinTreeRoot(void).创建一个二叉树的节点PBinTreeNodeCreate_BinTreeNode(void).创建一棵二叉树PBinTreeNodeCreate_BinTree(void).用先根的方法遍历一棵二叉树voidpreOrder(PBinTreeNodepbnode).用中根的方法遍历一棵二叉树voidinOrder(PBinTreeNodepbnode).用后根的方法遍历一棵二叉树voidpostOrder(PBinTreeNodepbnode).打印出我们创建的二叉树的树型结构voidoutputTree(PBinTreeNodepbnode,inttotalSpace).打印出二叉树的叶子结点voidleaves(PBinTreeNodepbnode).释放我们所申请的所有结点空间voidfreeAIINodes(PBinTreeNodepbnode).判断我们输入的是否是合格的字符intisalphabet(chari)2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0to}if(i==6)(freeAIINodes(*pbtree);)pbtree=Create_BinTreeRoot();outputTree(*pbtree,totalSpace);})freeAIINodes(*pbtree);getch();return0;七.图形界面根据提示一步步进行操作。c<"C:\ProgramFiles\MicrosoftVisualStudio\MyProjects\66\Debug\66.exe"Pleaseinputachar：APleaseinputachar：BPleaseinputachar：CPleaseinputachar：(?Pleaseinputachar：ePleaseinputachar：DPleaseinputachar：ePleaseinputachar：(?Pleaseinputachar：EPleaseinputachar：FPleaseinputachar：(?Pleaseinputachar：(?Pleaseinputachar：GPleaseinputachar：ePleaseinputachar：eDisplaythebinatreedatadirectly：GEFADBCPleasechoosethenodeyouwanttooperatewiththebinatree：1.display2・pi*eOi*deT3・in0i*deT4-postONdeT5.leaves nodes0toexit：八MC:\ProgramFiles\MicrosoftVisualStudio\MyProjects\66\Debug\66.exeuBCPleasechoosethenodeyouwanttooperatewiththebinatree：1.display2.preOrder3.inOrder4.post0i*dei*5.leaues6.freenodes0toDisplaybinatree：GEFADBCPleasechoosethenodeyouwanttooperatewiththebinatree：exit：exit：2DatainpreOrder：A B C D E F GPleasechoosethemodeyouwanttooperatewiththebinatree：0toexit：0toexit：三、详细设计：.PBinTreeNodeCreate_BinTreeNode(void)我们定义一个指向二叉树结点类型的指针PBinTreeNode,然后，申请一个二叉树结点大小的空间，对摆布子结点赋为空。.创建一个二叉树根节点定义一个指向二叉树结点的指针的指针即：BinTreeNode**pbtree,或者是：PBinTreeNode*pbtree;用于存放树的根结点，同时，将我们创建的二叉树的地址传给它即：*pbtree=Create_BinTree();.创建一棵二叉树首先我们定义一个DataType类型的变量i,用于存放我们输入的字符(即作为缓冲区)，并用scanf函数去接收它，由于使用scanf函数时，会浮现吸收我们输入的回车字符，并将会车作为接收的字符的情况发生，为了避免这种情况，我们用函数fflush(stdin)将缓冲区的字符全部冲掉，然后再吸收我们输入的字符，就可以彻底避免此类问题的发生。我们定义我们输入的字符是从a-z或者是A-Z,用字符@为我们结束当前结点左或者右结点的字符，然后递归调用摆布子树，此时我们将一棵二叉树全整的创建出来了。.用先根的方法遍历一棵二叉树先访问根结点，打印出它里面的信息，然后递归调用左子树和右子树。.用中根的方法遍历一棵二叉树先递归调用左子树，打印出里面的信息，在打印出根结点信息，然后递归调用右子树，打印出里面的信息。.用后根的方法遍历一棵二叉树先递归调用左子树，打印出里面的内容，然后递归调用右子树，打印出里面的内容，然后是根结点的内容。.打印出我们创建的二叉树的树型结构先递归调用右子树，如果结点不为空的话，空格数加5,如果为空的话，就打印出右子树的内容，然后递归调用左子树。.打印出二叉树的叶子结点如果当前结点的摆布子树都为空的话，就打印出此结点的信息，如果左子树不为空的话，递归调用左子树，如果右子树不为空的话，递归调用右子树。.释放我们所申请的所有结点空间如果当前的左子树不为空，则遍历左子树，如果右子树不为空的话，则遍历右子树，如果都不位空的话，分别调用摆布子树，如果摆布都为空的话，就释放摆布结点空间，并将当前结点置为空。.主函数的安排：先创建好我们要的二叉树，之后，我们就可以对此而二树进行多种操作，我们定义了6种集合操作，并对用户输入的信息进行检测，正确的提示出错信息，如果选择的是我们定义的操作之一的话，对应的我们设置出不同的case语句。如果我们选择的是释放所有的结点空间的话，我们需要屏蔽掉所有的菜单信息，提示用户重新创建一棵二叉树，并对它进行重新操作。如果我们选择退出，但是没有选择释放掉所有的节点空间时，我们需要考虑到此类的情形，应调用voidfreeAIINodes(PBinTreeNodepbnode)自动的释放掉所有的结点空间，正常的退出。四、用户使用说明：当用户还没有创建二叉树时，提示用户输入数据：Pleaseinputchartothebinatree,@toexitcurrentnodePleaseinputachar:这时用户用键盘输入，每输入一个字符回车一次,输入为a-z或者是A-Z之间的字符，用字符作为结束当前结点的标识符当用户，创建了二叉树之后，浮现控制菜单：Pleasechoosethemodeyouwanttooperatewiththebinatree:1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:此时用户可以选择操作：1.自动的打印出树型结构2.先根遍历3.中根遍历4.后根遍历5.打印叶子结点6.释放所有结点空间0.退出五、测试结果：1.测试彻底二叉树的情形：输入（每输入一个字符回车一次）：ABC@@D@@EF@@G@@自动的打印出树型结构：Displaythebinatreedatadirectly:GEFADBC三种遍历方式和叶子结点，测试如下：先根：DatainpreOrder:ABCDEFG中根：DataininOrder:CBDAFEG后根：DatainpostOrder:CDBFGEA打印叶子结点：Leaves:CDFG释放所有结点空间:Freeallnodes:Allnodehavebeenfreedsuccessfully.自动提示创建一棵新的二叉树：Nowcreatinganewbinatree...Pleaseinputchartothebinatree,@toexitcurrentnode:Pleaseinputachar:2测试非彻底二叉树的情形输入（每输入一个字符回车一次）：ABCD@@@@@自动的打印出树型结构：ABCD三种遍历方式和叶子结点，测试如下：先根：DatainpreOrder:ABCD中根：DataininOrder:DCBA后根：DatainpostOrder:DCBA打印叶子结点：Leaves:D释放所有结点空间：Freeallnodes:Allnodehavebeenfreedsuccessfully.自动提示创建一棵新的二叉树：Nowcreatinganewbinatree...Pleaseinputchartothebinatree,@toexitcurrentnode:Pleaseinputachar:如果我们想结束此次的操作，退出本程序，就可以输入0,程序自动的释放所有的结点空间:Pleasechoosethemodeyouwanttooperatewiththebinatree:1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:0Dealingwiththelastjob,tofreeallnodesAllnodehavebeenfreedsuccessfully六、附录：include<stdio.h>#include<stdlib.h>#include<conio.h>#defineNULL0#defineDataTypechartypedefstructBinTreeNode*PBinTreeNode;typedefPBinTreeNode*PBinTree;structBinTreeNode{DataTypeinfo;PBinTreeNodellink;PBinTreeNoderlink;);PBinTreeNodeCreate_BinTree(void);PBinTreeCreate_BinTreeRoot(void){PBinTreepbtree;pbtree=(PBinTree)malloc(sizeof(structBinTreeNode));if(pbtree==NULL)pbtree=(PBinTree)realloc(pbtree,sizeof(structBinTreeNode));*pbtree=Create_BinTree();return(pbtree);)PBinTreeNodeCreate_BinTreeNode(void){PBinTreeNodepbnode;pbnode=(PBinTreeNode)malloc(sizeof(structBinTreeNode));if(pbnode==NULL)pbnode=(PBinTreeNode)realloc(pbnode,sizeof(structBinTreeNode));elsepbnode->llink=pbnode->rlink=(PBinTreeNode)NULL;return(pbnode);)intisalphabet(chari){if(i>=•a'&&i<=,z,||i>='N&&i<=T||i=='@')return1;elsereturn0;PBinTreeNodeCreate_BinTree(void){PBinTreeNodepbnode;DataTypei;fflush(stdin);fflush(stdin);while(!isalphabet(i))fflush(stdin);}if(i=='@')pbnode=NULL;else(pbnode=(PBinTreeNode)malloc(sizeof(structBinTreeNode));if(pbnode==NULL)(returnpbnode;}pbnode->info=i;pbnode->llink=Create_BinTree();pbnode->rlink=Create_BinTree();}returnpbnode;)voidoutputTree(PBinTreeNodepbnode,inttotalSpace){inti;if(pbnode!=NULL){totalSpace+=5;outputTree(pbnode->rlink,totalSpace);outputTree(pbnode->llink,totalSpace);)voidpreOrder(PBinTreeNodepbnode)if(pbnode==NULL)return;preOrder(pbnode->llink);preOrder(pbnode->rlink);)voidinOrder(PBinTreeNodepbnode){if(pbnode==NULL)return;inOrder(pbnode->llink);inOrder(pbnode->rlink);)voidpostOrder(PBinTreeNodepbnode){if(pbnode==NULL)return;postOrder(pbnode->llink);postOrder(pbnode->rlink);)voidleaves(PBinTreeNodepbnode)(if(pbnode->llink!=NULL&&pbnode->rlink==NULL)leaves(pbnode->llink);if(pbnode->rlink!=NULL&&pbnode->llink==NULL)leaves(pbnode->rlink);if(pbnode->llink!=NULL&&pbnode->rlink!=NULL)(leaves(pbnode->llink);leaves(pbnode->rlink);)if(pbnode->llink==NULL&&pbnode->rlink==NULL)(return;})voidfreeAIINodes(PBinTreeNodepbnode)(if(pbnode->llink!=NULL&&pbnode->rlink==NULL)freeAIINodes(pbnode->llink);if(pbn