2023年6月22日发(作者：)
一、需求分析：
编写一段程序，对二叉树进行复合操作，包括创建一棵二叉树，显示二叉树的树型结构，对创建的二叉树进行先根、中根、后根三种方式进行遍历，并且打印出叶子结点，并且可以随时删除我们创建的二叉树，然后用循环语句将上述的操作封装起来，使之能够进行可重复、连续的操作。输入为a-z或者是A-Z之间的字符，用‘@’字符作为结束当前结点的标识符。
二、概要设计：
本程序要用到的数据类型
struct BinTreeNode
{ DataType info;
PBinTreeNode llink;
PBinTreeNode rlink;
};
然后定义我们需要的指针类型
typedef struct BinTreeNode *PBinTreeNode; /* 定义指向二叉树结点的指针类型*/
typedef PBinTreeNode *PBinTree; /*定义指向树型结点的指针类型*/
程序需要用到的自定义函数
1．创建一个二叉树根节点
PBinTree Create_BinTreeRoot(void)
2．创建一个二叉树的节点
PBinTreeNode Create_BinTreeNode(void)
3．创建一棵二叉树
PBinTreeNode Create_BinTree(void)
4．用先根的方法遍历一棵二叉树
void preOrder(PBinTreeNode pbnode)
5．用中根的方法遍历一棵二叉树
void inOrder(PBinTreeNode pbnode)
6．用后根的方法遍历一棵二叉树
void postOrder(PBinTreeNode pbnode)
7．打印出我们创建的二叉树的树型结构
void outputTree(PBinTreeNode pbnode,int totalSpace)
8．打印出二叉树的叶子结点
void leaves(PBinTreeNode pbnode)
9．释放我们所申请的所有结点空间
void freeAllNodes(PBinTreeNode pbnode)
10．判断我们输入的是否是合格的字符
int isalphabet(char i)
三、详细设计：
1． PBinTreeNode Create_BinTreeNode(void)
我们定义一个指向二叉树结点类型的指针PBinTreeNode，然后，申请一个二叉树结点大小的空间，对左右子结点赋为空。
2．创建一个二叉树根节点
定义一个指向二叉树结点的指针的指针即：BinTreeNode ** pbtree, 或者是：PBinTreeNode *pbtree;用于存放树的根结点，同时，将我们创建的二叉树的地址传给它即：*pbtree=Create_BinTree();
3． 创建一棵二叉树
首先我们定义一个DataType类型的变量i,用于存放我们输入的字符（即作为缓冲区），并用scanf函数去接收它，由于使用scanf函数时，会出现吸收我们输入的回车字符，并将会车作为接收的字符的情况发生，为了避免这种情况，我们用函数fflush(stdin)将缓冲区的字符全部冲掉，然后再吸收我们输入的字符，就可以完全避免此类问题的发生。我们定义我们输入的字符是从a-z或者是A-Z，用字符@为我们结束当前结点左或者右结点的字符，然后递归调用左右子树，此时我们将一棵二叉树全整的创建出来了。
4．用先根的方法遍历一棵二叉树
先访问根结点，打印出它里面的信息，然后递归调用左子树和右子树。
5．用中根的方法遍历一棵二叉树
先递归调用左子树，打印出里面的信息，在打印出根结点信息，然后递归调用右子树，打印出里面的信息。
6．用后根的方法遍历一棵二叉树
先递归调用左子树，打印出里面的内容，然后递归调用右子树，打印出里面的内容，然后是根结点的内容。
7. 打印出我们创建的二叉树的树型结构
先递归调用右子树，如果结点不为空的话，空格数加5，如果为空的话，就打印出右子树的内容，然后递归调用左子树。
8．打印出二叉树的叶子结点
如果当前结点的左右子树都为空的话，就打印出此结点的信息，如果左子树不为空的话，递归调用左子树，如果右子树不为空的话，递归调用右子树。
9．释放我们所申请的所有结点空间
如果当前的左子树不为空，则遍历左子树，如果右子树不为空的话，则遍历右子树，如果都不位空的话，分别调用左右子树，如果左右都为空的话，就释放左右结点空间，并将当前结点置为空。
10．主函数的安排：
先创建好我们要的二叉树，之后，我们就可以对此而二树进行多种操作，我们定义了6种集合操作，并对用户输入的信息进行检测，正确的提示出错信息，如果选择的是我们定义的操作之一的话，对应的我们设置出不同的case语句。如果我们选择的是释放所有的结点空间的话，我们需要屏蔽掉所有的菜单信息，提示用户重新创建一棵二叉树，并对它进行重新操作。
如果我们选择退出，但是没有选择释放掉所有的节点空间时，我们需要考虑到此类的情形，应调用void freeAllNodes(PBinTreeNode pbnode)自动的释放掉所有的结点空间，正常的退出。
四、用户使用说明：
当用户还没有创建二叉树时，提示用户输入数据：
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:
y er r der nodes 0 to exit:
此时用户可以选择操作：1. 自动的打印出树型结构 2.先根遍历 3.中根遍历 4.后根遍历
5. 打印叶子结点 6. 释放所有结点空间 0.退出
五、测试结果：
1． 测试完全二叉树的情形：
输入（每输入一个字符回车一次）：A B C @ @ D @ @ E F @ @ G
@ @
自动的打印出树型结构：
Display the binatree data directly:
G
E
F
A
D
B
C
三种遍历方式和叶子结点，测试如下：
先根：
Data in preOrder:
A B C D E F G
中根：
Data in inOrder:
C B D A F E G
后根：
Data in postOrder:
C D B F G E A
打印叶子结点：
Leaves:
C D F G
释放所有结点空间： Free all nodes:
All node have been freed successfully.
自动提示创建一棵新的二叉树：
Now creating a
Please input char to the binatree, @ to exit current node:
Please input a char:
2测试非完全二叉树的情形
输入（每输入一个字符回车一次）：A B C D @ @ @ @ @
自动的打印出树型结构：
A
B
C
D
三种遍历方式和叶子结点，测试如下：
先根：
Data in preOrder:
A B C D
中根：
Data in inOrder:
D C B A
后根：
Data in postOrder:
D C B A
打印叶子结点：
Leaves:
D
释放所有结点空间：
Free all nodes:
All node have been freed successfully.
自动提示创建一棵新的二叉树：
Now creating a
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:
y er r der nodes 0 to exit:0
Dealing with the last job, to free all nodes
All node have been freed successfully
六、附录：
#include
#include
#include
#define NULL 0
#define DataType char
typedef struct BinTreeNode *PBinTreeNode;
typedef PBinTreeNode *PBinTree;
struct BinTreeNode
{ DataType info;
PBinTreeNode llink;
PBinTreeNode rlink;
};
PBinTreeNode Create_BinTree(void);
PBinTree Create_BinTreeRoot(void)
{PBinTree pbtree;
pbtree=(PBinTree)malloc(sizeof(struct BinTreeNode));
if(pbtree==NULL) pbtree=(PBinTree)realloc(pbtree,sizeof(struct BinTreeNode));
*pbtree=Create_BinTree();
return (pbtree);
}
PBinTreeNode Create_BinTreeNode(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 >= 'A' && i <='Z' || i=='@')
return 1;
else return 0;
} PBinTreeNode Create_BinTree(void)
{PBinTreeNode pbnode ;
DataType i;
printf("Please input a char:t");
fflush(stdin);
scanf("%c",&i);
fflush(stdin);
while(!isalphabet(i))
{
printf("Sorry, your input char is not in alphabet, please input again:");
scanf("%c",&i);
fflush(stdin);
}
if(i=='@') pbnode= NULL;
else
{
pbnode = (PBinTreeNode)malloc(sizeof(struct BinTreeNode));
if(pbnode == NULL)
{
printf("Out of space!n");
return pbnode ;
}
pbnode->info=i;
pbnode->llink=Create_BinTree();
pbnode->rlink=Create_BinTree();
}
return pbnode;
}
void outputTree(PBinTreeNode pbnode,int totalSpace)
{int i;
if(pbnode!=NULL)
{
totalSpace+=5;
outputTree(pbnode->rlink,totalSpace);
for(i=0;i printf("%cn",pbnode->info); outputTree(pbnode->llink,totalSpace); } } void preOrder(PBinTreeNode pbnode) { if(pbnode==NULL) return ; printf("%ct",pbnode->info); preOrder(pbnode->llink); preOrder(pbnode->rlink); } void inOrder(PBinTreeNode pbnode) { if(pbnode== NULL) return; inOrder(pbnode->llink); printf("%ct",pbnode->info); inOrder(pbnode->rlink); } void postOrder(PBinTreeNode pbnode) { if(pbnode == NULL) return ; postOrder(pbnode->llink); postOrder(pbnode->rlink); printf("%ct", pbnode->info); } void leaves(PBinTreeNode 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) { printf("%ct",pbnode->info); return; } } void freeAllNodes(PBinTreeNode pbnode) { if(pbnode->llink != NULL && pbnode->rlink == NULL) freeAllNodes(pbnode->llink); if(pbnode->rlink != NULL && pbnode->llink == NULL) freeAllNodes(pbnode->rlink); if(pbnode->llink != NULL && pbnode->rlink != NULL) { freeAllNodes(pbnode->llink); freeAllNodes(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; printf("Please input char to the binatree,@ to exit current node:n"); pbtree = Create_BinTreeRoot(); printf("Display the binatree data directly:n"); outputTree(*pbtree,totalSpace); printf("Please choose the mode you want to operate with the binatree:n"); printf("y er r der nodes 0 to exit:"); scanf("%d",&i); while(i>6 || i<0) { printf("nYou choice is illegal please input again:n"); printf("y er r der nodes 0 to exit:"); scanf("%d",&i); } while(i!=0) { while(i > 6 || i<0) { printf("nYou choice is illegal please input again:n"); printf("y er r der nodes 0 to exit:"); scanf("%d",&i); } while(i !=0) { while(i > 6 || i<0) { printf("nYou choice is illegal please input again:n"); printf("y er r der nodes 0 to exit:"); scanf("%d",&i); } while(i !=6) { while(i > 6 || i<0) { printf("nYou choice is illegal please input again:n"); printf("y er r der nodes 0 to exit:"); scanf("%d",&i); } switch(i) { case 0 : printf("nDealing with the last job, to free "); freeAllNodes(*pbtree); printf("All node have been freed successfullyn"); exit(1); getch(); case 1 : printf("nDisplay binatree:n"); outputTree(*pbtree,totalSpace); break; case 2 : printf("nData in preOrder:n"); preOrder(*pbtree); printf("nn"); break; case 3 : printf("nData in inOrder:n"); inOrder(*pbtree); printf("nn"); break; case 4 : printf("nData in postOrder:n"); postOrder(*pbtree); printf("nn"); break; case 5: printf("nLeaves:n"); leaves(*pbtree); printf("nn"); } printf("Please choose the mode you want to operate with the binatree:n"); printf("y er r der nodes 0 to exit:"); scanf("%d",&i); } if(i==6) { printf("nFree all nodes:n"); freeAllNodes(*pbtree); printf("All node have been freed successfully."); } printf("nnNow creating a "); printf("Please input char to the binatree,@ to exit current node:n"); pbtree = Create_BinTreeRoot(); printf("Display the binatree data directly:n"); outputTree(*pbtree,totalSpace); printf("Please choose the mode you want to operate with the binatree:n"); printf("y er r der nodes 0 to exit:"); scanf("%d",&i); } } printf("nDealing with the last job, to free all nodesn"); freeAllNodes(*pbtree); printf("All node have been freed successfullyn"); getch(); return 0; } 七．图形界面 根据提示一步步进行操作。
发布者：admin，转转请注明出处：http://www.yc00.com/web/1687385237a6119.html
评论列表（0条）