二叉树的集合操作.c

二叉树的集合操作附代码

#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;
}