end.txt

二叉树

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

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 k;
 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);
                 printf("level:%d",k);
                 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:\n");
         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;
}