还剩9页未读,继续阅读
本资源只提供10页预览,全部文档请下载后查看!喜欢就下载吧,查找使用更方便
文本内容:
一、需求分析编写一段程序,对二叉树进行复合操作,包括创建一棵二叉树,显示二叉树的树型结构,对创建的二叉树进行先根、中根、后根三种方式进行遍历,并且打印出叶子结点,并且可以随时删除我们创建的二叉树,然后用循环语句将上述的操作封装起来,使之能够进行可重复、连续的操作输入为或者是之间的字符,用@字符作为结束当前结点的标识符a-z A-Z
二、概要设计本程序要用到的数据类型struct BinTreeNode{DataType info;PBinTreeNode llink;PBinTreeNode rlink;};然后定义我们需要的指针类型定义指向二叉树结点的指针类型*/typedef struct BinTreeNode*PBinTreeNode;/*/*定义指向树型结点的指针类型*/typedef PBinTreeNode*PBinTree;程序需要用到的自定义函数创建一个二叉树根节点
1.PBinTree Create_BinT reeRootvoid创建一个二叉树的节点
2.PBinTreeNode Create_BinT reeNodevoid创建一棵二叉树
3.PBinTreeNode Create_BinT reevoid用先根的方法遍历一棵二叉树
4.void preOrderPBinT reeNode pbnode用中根的方法遍历一棵二叉树
5.void inOrderPBinTreeNode pbnode用后根的方法遍历一棵二叉树
6.void postOrderPBinT reeNode pbnode打印出我们创建的二叉树的树型结构
7.void outputT reePBinT reeNode pbnode,int totalSpace打印出二叉树的叶子结点
8.void leavesPBinTreeNode pbnode释放我们所申请的所有结点空间
9.void freeAIINodesPBinTreeNodepbnode判断我们输入的是否是合格的字符
10.int isalphabetchari
2.preOrder
3.inOrder
4.postOrder
5.leaves
6.free nodes0to}ifi==6freeAIINodes*pbtree;pbtree=Create_BinT reeRoot;outputT ree*pbtree,totalSpace;}freeAIINodes*pbtree;getch;return0;七.图形界面根据提示一步步进行操作cC:\Program Files\Microsoft VisualStudio\MyProjects\66\Debug\
66.exePlease inputa charAPlease inputa charBPlease inputa charCPlease inputa charPlease inputa charePlease inputa charDPlease inputa charePlease inputa charPlease inputa charEPlease inputa charFPlease inputa charPlease inputa charPlease inputa charGPlease inputa charePlease inputa chareDisplay the binatree datadirectlyG EF AD B CPlease choose the nodeyou want to operate with the binatree
1.display2・pi*eOi*deT3・in0i*deT4-postONdeT
5.leaves nodes0to exitMC:\Program Files\Microsoft VisualStudio\MyProjects\66\Debug\
66.exeu八BCPlease choosethe nodeyou wantto operatewith the binatree
1.display
2.preOrder
3.inOrder
4.post0i*dei*
5.leaues
6.free nodes0toDisplay binatreeGEFADBCPlease choosethe nodeyou wantto operatewith the binatree
1.display
2.preOrder
3.inOrder
4.post0i*dei*
5.leaues
6.f reenodes0to exit2Data inpreOrder ABCD EF GPlease choosethe mode you wantto operatewith thebinatree
1.display
2.preOrder
3.inOrdei*
4.post0i*dei*
5.leaues
6.free nodes0to exit
三、详细设计
1.PBinTreeNode Create_BinTreeNodevoid我们定义一个指向二叉树结点类型的指针然后,申请一个二叉树结点大小的空PBinTreeNode,间,对摆布子结点赋为空创建一个二叉树根节点
2.定义一个指向二叉树结点的指针的指针即或者是BinTreeNode**pbtree,PBinTreeNode用于存放树的根结点,同时,将我们创建的二叉树的地址传给它即*pbtree;*pbtree=Create_BinTree;创建一棵二叉树
3.首先我们定义一个类型的变量用于存放我们输入的字符即作为缓冲区,并用DataType i,scanf函数去接收它,由于使用函数时,会浮现吸收我们输入的回车字符,并将会车作为接收的字scanf符的情况发生,为了避免这种情况,我们用函数将缓冲区的字符全部冲掉,然后再吸收fflushstdin我们输入的字符,就可以彻底避免此类问题的发生我们定义我们输入的字符是从或者是a-z A-Z,用字符@为我们结束当前结点左或者右结点的字符,然后递归调用摆布子树,此时我们将一棵二叉树全整的创建出来了用先根的方法遍历一棵二叉树
4.先访问根结点,打印出它里面的信息,然后递归调用左子树和右子树用中根的方法遍历一棵二叉树
5.先递归调用左子树,打印出里面的信息,在打印出根结点信息,然后递归调用右子树,打印出里面的信息用后根的方法遍历一棵二叉树
6.先递归调用左子树,打印出里面的内容,然后递归调用右子树,打印出里面的内容,然后是根结点的内容.打印出我们创建的二叉树的树型结构7先递归调用右子树,如果结点不为空的话,空格数加如果为空的话,就打印出右子树的内容,5,然后递归调用左子树打印出二叉树的叶子结点
8.如果当前结点的摆布子树都为空的话,就打印出此结点的信息,如果左子树不为空的话,递归调用左子树,如果右子树不为空的话,递归调用右子树释放我们所申请的所有结点空间
9.如果当前的左子树不为空,则遍历左子树,如果右子树不为空的话,则遍历右子树,如果都不位空的话,分别调用摆布子树,如果摆布都为空的话,就释放摆布结点空间,并将当前结点置为空主函数的安排
10.先创建好我们要的二叉树,之后,我们就可以对此而二树进行多种操作,我们定义了种集合6操作,并对用户输入的信息进行检测,正确的提示出错信息,如果选择的是我们定义的操作之一的话,对应的我们设置出不同的语句如果我们选择的是释放所有的结点空间的话,我们需要屏case蔽掉所有的菜单信息,提示用户重新创建一棵二叉树,并对它进行重新操作如果我们选择退出,但是没有选择释放掉所有的节点空间时,我们需要考虑到此类的情形,应调用自动的释放掉所有的结点空间,正常的退出voidfreeAIINodesPBinTreeNodepbnode
四、用户使用说明当用户还没有创建二叉树时,提示用户输入数据Please inputchar tothebinatree,@to exitcurrent nodePlease inputa char:这时用户用键盘输入,每输入一个字符回车一次,输入为或者是之间的字符,用字符作a-z A-Z为结束当前结点的标识符当用户,创建了二叉树之后,浮现控制菜单Please choosethe modeyou wantto operatewith thebinatree:
1.display
2.preOrder
3.inOrder
4.postOrder
5.leaves
6.free nodes0to exit:此时用户可以选择操作自动的打印出树型结构.先根遍历.中根遍历.后根遍历.打印
1.2345叶子结点.释放所有结点空间.退出60
五、测试结果测试彻底二叉树的情形
1.输入(每输入一个字符回车一次)ABC@@D@@EF@@G@@自动的打印出树型结构Display thebinatree datadirectly:GEFADBC三种遍历方式和叶子结点,测试如下先根Data inpreOrder:ABCDEFG中根Data ininOrder:CBDAFEG后根Data inpostOrder:CDBFGEA打印叶子结点Leaves:CDFG释放所有结点空间:Free allnodes:All node have been freed successfully.自动提示创建一棵新的二叉树Now creatinga newbinatree...Please inputchar tothebinatree,@to exitcurrent node:Please inputa char:测试非彻底二叉树的情形2输入(每输入一个字符回车一次)ABCD@@@@@自动的打印出树型结构ABCD三种遍历方式和叶子结点,测试如下先根Data inpreOrder:ABCD中根Data ininOrder:DCB A后根Data inpostOrder:DCBA打印叶子结点Leaves:D释放所有结点空间Free allnodes:All nodehave beenfreed successfully.自动提示创建一棵新的二叉树Now creatinga newbinatree...Please inputchar tothebinatree,@to exitcurrent node:Please inputa char:如果我们想结束此次的操作,退出本程序,就可以输入程序自动的释放所有的结点空间:0,Pleasechoosethemodeyouwanttooperatewiththebinatree:
1.display
2.preOrder
3.inOrder
4.postOrder
5.leaves
6.free nodes0to exit:0Dealing withthe lastjob,to freeall nodesAllnodehavebeenfreedsuccessfully
六、附录include stdio.h#include stdlib.h#include conio.h#define NULL0#define DataTypechartypedef structBinTreeNode*PBinTreeNode;typedef PBinTreeNode*PBinTree;structBinTreeNode{DataType info;PBinTreeNode llink;PBinTreeNode rlink;;PBinTreeNode Create_BinT reevoid;PBinTree Create_BinT reeRootvoid{PBinTree pbtree;pbtree=PBinTreemallocsizeofstruct BinTreeNode;ifpbtree==NULL pbtree=PBinTreereallocpbtree,sizeofstruct BinTreeNode;*pbtree=Create_BinTree;return pbtree;PBinTreeNode Create_BinT reeNodevoid{PBinTreeNode pbnode;pbnode=PBinTreeNodemallocsizeofstruct BinTreeNode;ifpbnode==NULL pbnode=PBinTreeNodereallocpbnode,sizeofstruct BinTreeNode;elsepbnode-llink=pbnode-rlink=PBinTreeNodeNULL;return pbnode;int isalphabetchari{if i=•ai=,z,||i=Ni=T||i==@return1;else return0;PBinTreeNode Create_BinT reevoid{PBinTreeNode pbnode;DataType i;fflushstdin;fflushstdin;while!isalphabetifflushstdin;}ifi==@pbnode=NULL;elsepbnode=PBinTreeNodemallocsizeofstruct BinTreeNode;ifpbnode==NULL return pbnode;}pbnode-info=i;pbnode-llink=Create_BinTree;pbnode-rlink=Create_BinTree;}returnpbnode;void outputT reePBinT reeNodepbnode,int totalSpace{int i;ifpbnode!=NULL{totalSpace+=5;outputTreepbnode-rlink,totalSpace;outputTreepbnode-llink,totalSpace;void preOrderPBinTreeNode pbnodeifpbnode==NULL return;preOrderpbnode-llink;preOrderpbnode-rlink;void inOrderPBinTreeNodepbnode{ifpbnode==NULL return;inOrderpbnode-llink;inOrderpbnode-rlink;void postOrderPBinTreeNodepbnode{ifpbnode==NULL return;postOrderpbnode-llink;postOrderpbnode-rlink;void leavesPBinTreeNode pbnodeifpbnode-llink!=NULLpbnode-rlink==NULL leavespbnode-llink;ifpbnode-rlink!=NULLpbnode-llink==NULL leavespbnode-rlink;ifpbnode-llink!=NULLpbnode-rlink!=NULL leavespbnode-llink;leavespbnode-rlink;ifpbnode-llink==NULLpbnode-rlink==NULL return;}void freeAIINodesPBinTreeNode pbnodeifpbnode-llink!=NULLpbnode-rlink==NULL freeAIINodespbnode-llink;ifpbnode-rlink!=NULLpbnode-llink==NULL freeAIINodespbnode-rlink;ifpbnode-llink!=NULLpbnode-rlink!=NULLfreeAIINodespbnode-llink;freeAIINodespbnode-rlink;}ifpbnode-llink==NULLpbnode-rlink==NULL freepbnode-llink;freepbnode-rlink;pbnode=NULL;return;}int main{PBinTree pbtree;int i;int totalSpace=0;pbtree=Create_BinT reeRoot;outputTree*pbtree,totalSpace;whilei6||i0}whilei!=0whilei6||i0whilei!=0whilei6||i
02.preOrder
3.inOrder
4.postOrder
5.leaves
6.free nodes0towhilei!=6whilei6||i0switchicaseO:freeAIINodes*pbtree;exit1;getch;case1::outputTree*pbtree,totalSpace;break;preOrder*pbtree;break;inOrder*pbtree;break;postOrder*pbtree;break;leaves*pbtree;。