二叉树的集合操作

以下程序源代码：

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#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<totalspace;i++) printf(" ");
printf("%c\n",pbnode->info);
outputtree(pbnode->llink,totalspace);
}
}

void preorder(pbintreenode pbnode)
{
if(pbnode==null) return ;
printf("%c\t",pbnode->info);
preorder(pbnode->llink);
preorder(pbnode->rlink);
}

void inorder(pbintreenode pbnode)
{
if(pbnode== null) return;
inorder(pbnode->llink);
printf("%c\t",pbnode->info);
inorder(pbnode->rlink);
}

void postorder(pbintreenode pbnode)
{
if(pbnode == null) return ;
postorder(pbnode->llink);
postorder(pbnode->rlink);
printf("%c\t", 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("%c\t",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("1.display 2.preorder 3.inorder 4.postorder 5.leaves 6.free nodes 0 to exit:");
scanf("%d",&i);
while(i>6 || i<0)
{
printf("\nyou choice is illegal please input again:\n");
printf("1.display 2.preorder 3.inorder 4.postorder 5.leaves 6.free 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("1.display 2.preorder 3.inorder 4.postorder 5.leaves 6.free 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("1.display 2.preorder 3.inorder 4.postorder 5.leaves 6.free 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("1.display 2.preorder 3.inorder 4.postorder 5.leaves 6.free nodes 0 to exit:");
scanf("%d",&i);
}
switch(i)
{
case 0 :
printf("\ndealing with the last job, to free all nodes...\n");
freeallnodes(*pbtree);
printf("all node have been freed successfully\n");
exit(1);
getch();
case 1 :
printf("\ndisplay binatree:\n");
outputtree(*pbtree,totalspace);
break;
case 2 :
printf("\ndata in preorder:\n");
preorder(*pbtree);
printf("\n\n");
break;
case 3 :
printf("\ndata in inorder:\n");
inorder(*pbtree);
printf("\n\n");
break;
case 4 :
printf("\ndata in postorder:\n");
postorder(*pbtree);
printf("\n\n");
break;
case 5:
printf("\nleaves:\n");
leaves(*pbtree);
printf("\n\n");
}
printf("please choose the mode you want to operate with the binatree:\n");
printf("1.display 2.preorder 3.inorder 4.postorder 5.leaves 6.free 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("\n\nnow creating a new binatree...\n");
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("1.display 2.preorder 3.inorder 4.postorder 5.leaves 6.free nodes 0 to exit:");
scanf("%d",&i);
}
}
printf("\ndealing with the last job, to free all nodes\n");
freeallnodes(*pbtree);
printf("all node have been freed successfully\n");
getch();
return 0;
}

 

----------------------------------以下是程序的详细分析过程-----------------------------------
二叉树的集合操作

一． 问题的描述和分析
编写一段程序，对二叉树进行复合操作，包括创建一棵二叉树，显示二叉树的树型结构，对创建的二叉树进行先根、中根、后根三种方式进行遍历，并且打印出叶子结点，并且可以随时删除我们创建的二叉树，然后用循环语句将上述的操作封装起来，使之能够进行可重复、连续的操作。

二．算法的设计
要实现上述的功能，我们首先要深刻的了解二叉树的数据结构，然后依据它的特点，着手如何去创建一棵二叉树，然后，用不同的方法对这棵二叉树进行不同的遍历，实现其它的功能，包括用户友好界面的实现等等一系列的后续操作。

三．数据结构的设计
本程序要用到的数据类型
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．判断我们输入的是否是合格的字符，我们把它们定义为a-z或者是a-z之间的字符，用‘@’字符作为结束当前结点的标识符
int isalphabet(char i)

五．具体程序的实现
1． pbintreenode create_bintreenode(void)
我们定义一个指向二叉树结点类型的指针pbintreenode，然后，申请一个二叉树结点大小的空间，
对左右子结点赋为空（鉴于visual c++类别的严格定义，我们这里把它赋值为(pbintreenode)null—-注解）
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:
当用户，创建了二叉树之后，出现控制菜单：
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． 测试完全二叉树的情形：
输入（每输入一个字符回车一次）：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 new binatree...
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 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:0

dealing with the last job, to free all nodes
all node have been freed successfully