数据结构二叉树实验报告.docx
一、需求分析：编写一段程序，对二叉树进行复合操作，包括创建一棵二叉树，显示二叉树的树型结构， 对创建的二叉树进行先根、中根、后根三种方式进行遍历，并且打印出叶子结点，并且可以 随时删除我们创建的二叉树，然后用循环语句将上述的操作封装起来，使之能够进行可重复、 连续的操作。输入为a-z或者是A-Z之间的字符，用''字符作为结束当前结点的标识符。二、概要设计：本程序要用到的数据类型struct BinTreeNodeDataType info;PBinTreeNode llink;PBinTreeNode rlink;然后定义我们需要的指针类型typedef struct BinTreeNode *PBinTreeNode; /* 定义指向二叉树结点的指针类型*/typedef PBinTreeNode *PBinTree;/*定义指向树型结点的指针类型*/程序需要用到的自定义函数1 .创建一个二叉树根节点PBinTree Create_BinT reeRoot(void)2 .创建一个二叉树的节点PBinTreeNode Create_BinT reeNode(void)3 .创建一棵二叉树PBinTreeNode Create_BinT ree(void)4 .用先根的方法遍历一棵二叉树void preOrder(PBinT reeNode pbnode)5 .用中根的方法遍历一棵二叉树void inOrder(PBinTreeNode pbnode)6 .用后根的方法遍历一棵二叉树void postOrder(PBinT reeNode pbnode)7 .打印出我们创建的二叉树的树型结构void outputT ree(PBinT reeNode pbnode,int totalSpace)8 .打印出二叉树的叶子结点void leaves(PBinT reeNode pbnode)9 .释放我们所申请的所有结点空间void freeAIINodes(PBinT reeNode pbnode)10 .判断我们输入的是否是合格的字符int isalphabet(char i)2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to if(i=6) (freeAIINodes(*pbtree);)pbtree = Create_BinT reeRoot();outputT ree(*pbtree,totalSpace);)freeAIINodes(*pbtree);getch();return 0;七.图形界面根据提示一步步进行操作。c < "C:Program FilesMicrosoft Visual StudioMyProjects66Debug66.exe"Pleaseinputachar：APleaseinputachar：BPleaseinputachar：CPleaseinputachar：(?Pleaseinputachar：ePleaseinputachar：DPleaseinputachar：ePleaseinputachar：(?Pleaseinputachar：EPleaseinputachar：FPleaseinputachar：(?Pleaseinputachar：(?Pleaseinputachar：GPleaseinputachar：ePleaseinputachar：eDisplay the binatree data directly： G E F A D B CPlease choose the node you want to operate with the binatree：1 .display 2 pi*eOi*deT 3in0i*deT 4-postONdeT 5 .leavesnodes 0 to exit：八 MC:Program FilesMicrosoft Visual StudioMyProjects66Debug66.exeuBCPlease choose the node you want to operate with the binatree：1 .display 2 .preOrder 3 . inOrder 4.post0i*dei* 5 . leaues 6 .free nodes 0 toDisplay binatree：GEFADBCPlease choose the node you want to operate with the binatree：exit：21 .display 2 .preOrder 3 . inOrder 4.post0i*dei* 5 . leaues 6 .f ree nodes 0 toData in preOrder：ABCDEFGPlease choose the mode you want to operate with the binatree：0 toexit ：1 .display 2 .preOrder 3 . inOrdei* 4.post0i*dei* 5. leaues 6 .free nodes三、详细设计：1 . PBinTreeNode Create_BinTreeNode(void)我们定义一个指向二叉树结点类型的指针PBinTreeNode,然后，申请一个二叉树结点 大小的空间，对摆布子结点赋为空。2 .创建一个二叉树根节点定义一个指向二叉树结点的指针的指针即：BinTreeNode * pbtree,或者是： PBinTreeNode *pbtree;用于存放树的根结点，同时，将我们创建的二叉树的地址传给它即： *pbtree=Create_BinT ree();3 .创建一棵二叉树首先我们定义一个DataType类型的变量i,用于存放我们输入的字符(即作为缓冲区)， 并用scanf函数去接收它，由于使用scanf函数时，会浮现吸收我们输入的回车字符，并将 会车作为接收的字符的情况发生，为了避免这种情况，我们用函数fflush(stdin)将缓冲区的 字符全部冲掉，然后再吸收我们输入的字符，就可以彻底避免此类问题的发生。我们定义我 们输入的字符是从a-z或者是A-Z,用字符为我们结束当前结点左或者右结点的字符，然 后递归调用摆布子树，此时我们将一棵二叉树全整的创建出来了。4 .用先根的方法遍历一棵二叉树先访问根结点，打印出它里面的信息，然后递归调用左子树和右子树。5 .用中根的方法遍历一棵二叉树先递归调用左子树，打印出里面的信息，在打印出根结点信息，然后递归调用右子树， 打印出里面的信息。6 .用后根的方法遍历一棵二叉树先递归调用左子树，打印出里面的内容，然后递归调用右子树，打印出里面的内容，然 后是根结点的内容。7 .打印出我们创建的二叉树的树型结构先递归调用右子树，如果结点不为空的话，空格数加5,如果为空的话，就打印出右子 树的内容，然后递归调用左子树。8 .打印出二叉树的叶子结点如果当前结点的摆布子树都为空的话，就打印出此结点的信息，如果左子树不为空的话， 递归调用左子树，如果右子树不为空的话，递归调用右子树。9 .释放我们所申请的所有结点空间如果当前的左子树不为空，则遍历左子树，如果右子树不为空的话，则遍历右子树，如 果都不位空的话，分别调用摆布子树，如果摆布都为空的话，就释放摆布结点空间，并将当 前结点置为空。10 .主函数的安排：先创建好我们要的二叉树，之后，我们就可以对此而二树进行多种操作，我们定义了 6 种集合操作，并对用户输入的信息进行检测，正确的提示出错信息，如果选择的是我们定义 的操作之一的话，对应的我们设置出不同的case语句。如果我们选择的是释放所有的结点 空间的话，我们需要屏蔽掉所有的菜单信息，提示用户重新创建一棵二叉树，并对它进行重 新操作。如果我们选择退出，但是没有选择释放掉所有的节点空间时，我们需要考虑到此类的情 形，应调用voidfreeAIINodes(PBinTreeNodepbnode)自动的释放掉所有的结点空间，正常的 退出。四、用户使用说明：当用户还没有创建二叉树时，提示用户输入数据：Please input char to the binatree, to exit current node Please input a char:这时用户用键盘输入，每输入一个字符回车一次,输入为a-z或者是A-Z之间的字符， 用字符作为结束当前结点的标识符当用户，创建了二叉树之后，浮现控制菜单：Please choose the mode you want to operate with the binatree:1 .display 2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to exit:此时用户可以选择操作：1.自动的打印出树型结构2.先根遍历3.中根遍历4.后根遍历 5.打印叶子结点6.释放所有结点空间0.退出五、测试结果：1 .测试彻底二叉树的情形：输入（每输入一个字符回车一次）：ABCDEFG 自动的打印出树型结构：Display the binatree data directly:GEFADBC三种遍历方式和叶子结点，测试如下：先根：Data in preOrder:ABCDEFG中根：Data in inOrder:CBDAFEG后根：Data in postOrder:CDBFGEA打印叶子结点：Leaves:CDFG释放所有结点空间:Free all nodes:All node have been freed successfully.自动提示创建一棵新的二叉树：Now creating a new binatree.Please input char to the binatree, to exit current node:Please input a char:2测试非彻底二叉树的情形输入（每输入一个字符回车一次）：ABCD自动的打印出树型结构：ABCD三种遍历方式和叶子结点，测试如下：先根：Data in preOrder:ABCD中根：Data in inOrder:DCB A后根：Data in postOrder:DCBA打印叶子结点：Leaves:D释放所有结点空间：Free all nodes:All node have been freed successfully.自动提示创建一棵新的二叉树：Now creating a new binatree.Please input char to the binatree, to exit current node:Please input a char:如果我们想结束此次的操作，退出本程序，就可以输入0,程序自动的释放所有的结点 空间:Please choose the mode you want to operate with the binatree:1 .display 2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 to exit:0Dealing with the last job, to free all nodesAll node have been freed successfully六、附录：include <stdio.h>#include <stdlib.h>#include <conio.h>#define NULL 0#define DataType chartypedef struct BinTreeNode *PBinTreeNode;typedef PBinTreeNode *PBinTree;struct BinTreeNodeDataType info;PBinTreeNode llink;PBinTreeNode rlink;);PBinTreeNode Create_BinT ree(void);PBinTree Create_BinT reeRoot(void)PBinTree pbtree;pbtree=(PBinTree)malloc(sizeof(struct BinTreeNode);if(pbtree=NULL) pbtree=(PBinTree)realloc(pbtree,sizeof(struct BinTreeNode);*pbtree=Create_BinT ree();return (pbtree);)PBinTreeNode Create_BinT reeNode(void)PBinTreeNode pbnode;pbnode=(PBinTreeNode)malloc(sizeof(struct BinTreeNode);if(pbnode=NULL) pbnode=(PBinTreeNode)realloc(pbnode,sizeof(struct BinTreeNode); else pbnode->llink=pbnode->rlink=(PBinTreeNode)NULL;return (pbnode);)int isalphabet(char i)if (i >= a' && i<=,z,|i>= 'N && i <=T | i='') return 1;else return 0;PBinTreeNode Create_BinT ree(void) PBinTreeNode pbnode;DataType i;fflush(stdin);fflush(stdin);while(!isalphabet(i)fflush(stdin);if(i='') pbnode= NULL;else(pbnode = (PBinTreeNode)malloc(sizeof(struct BinTreeNode); if(pbnode = NULL) (return pbnode;pbnode->info=i;pbnode->llink=Create_BinTree();pbnode->rlink=Create_BinTree(); return pbnode;)void outputT ree(PBinT reeNode pbnode,int totalSpace)int i;if(pbnode!=NULL)totalSpace+=5;outputTree(pbnode->rlink,totalSpace);outputTree(pbnode->llink,totalSpace);) void preOrder(PBinT reeNode pbnode)if(pbnode=NULL) return ;preOrder(pbnode->llink);preOrder(pbnode->rlink);)void inOrder(PBinTreeNode pbnode) if(pbnode= NULL) return;inOrder(pbnode->llink);inOrder(pbnode->rlink);)void postOrder(PBinT reeNode pbnode) if(pbnode = NULL) return ;postOrder(pbnode->llink);postOrder(pbnode->rlink);)void leaves(PBinT reeNode pbnode)(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;)void freeAIINodes(PBinT reeNode pbnode)(if(pbnode->llink != NULL && pbnode->rlink = NULL) freeAIINodes(pbnode->llink);if(pbnode->rlink != NULL && pbnode->llink = NULL) freeAIINodes(pbnode->rlink);if(pbnode->llink != NULL && pbnode->rlink != NULL)(freeAIINodes(pbnode->llink);freeAIINodes(pbnode->rlink);if(pbnode->llink = NULL && pbnode->rlink = NULL) (free(pbnode->llink);free(pbnode->rlink);pbnode = NULL;return ;)int main()PBinTree pbtree;int i;int totalSpace = 0;pbtree = Create_BinT reeRoot();outputT ree(*pbtree,totalSpace);while(i>6 | i<0)(while(i!=0)(while(i>6|i<0)()while(i !=0)while(i>6|i<0)2.preOrder 3.inOrder 4.postOrder 5.leaves 6.free nodes 0 towhile(i !=6)(while(i>6|i<0)switch(i)(caseO:freeAIINodes(*pbtree);exit(1);getch();case 1: :outputT ree(*pbtree,totalSpace); break;preOrder(*pbtree);break;inOrder(*pbtree);break;postOrder(*pbtree);break;leaves(*pbtree);
