作者: tonysong
二叉树的集合操作
前段时间,我写了一个关于链表的集合操作,能够将链表、堆栈,队列多种数据类型进行可重复的多种基本操作将链表深入的剖析了一番,这次,我花了点时间写了一个关于二叉树的集合操作的程序,它的主要功能是能够创建一棵二叉树,并且能够将我们创建的这棵二叉树用多种方式遍历,例如:先根遍历、中根遍历、后跟遍历,并且能够随时显示我们的二叉树的直观构造,以及打印出我们的叶子结点,能够随时的释放掉我们为二叉树所开辟的结点空间,然后自动的提示我们构造一棵新的二叉树,能够随时的推出我们的当前程序,并且在结束当前程序的时候,能够自动得释放掉我们所有的节点空间。
同时,本程序的自动纠错功能也很不错的,能够纠出我们常见的容易忽视的错误,实现实时的检查功能。
本程序是经过本人的精心设计和调试通过了的,要是大家对于二叉树的概念和操作不是很熟悉的话,我想,通过仔细的揣摩本程序,定能够替你解除心中的片片疑云。
本人本着为大家阐释清楚,不留疑虑,不留问题的的原则,特地附上一份详细的实验分析报告,大家仔细对照着着这个报告,结合源程序,一定能够将二叉树的关键技术搞的一清二楚!
若是本程序有什么不到之处或是有什么好的建议,不妨和本人联系,我的联系方式是:
QQ: 37170732 E-mail: owenstone@sina.com.cn
欢迎各位爱好windows编程和MFC编程爱好者加我!
-------------------------------以下是程序的代码部分----------------------------------------
#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);
p