二叉树.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("请输入构建二叉树的字符(a-z,A-Z或@):\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 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("用字符a-z或者是A-Z构建二叉树,用字符@代表当前结点左或者右结点的字符，每输入一个字符回车确定:\n示范格式(A  B  C @  @  D  @  @  E  F  @  @  G  @  @)\n");
 pbtree = Create_BinTreeRoot();
 printf("树的图形为:\n");
 outputTree(*pbtree,totalSpace);
 printf("请选择操作:\n");
 printf("1.树的图形 2.先序遍历 3.层序遍历 4.释放空间 0 to exit:");
 scanf("%d",&i);
 while(i>4 || i<0)
     {
         printf("\n输入错误请重新输入:\n");
         printf("1.树的图形  2.先序遍历 3.层序遍历 4.释放空间 0 to exit:");
         scanf("%d",&i);
     }
 while(i!=0)
 {
     while(i > 4 || i<0)
     {
         printf("\n输入错误请重新输入:\n");
         printf("1.树的图形 2.先序遍历 3.层序遍历 4.释放空间 0 to exit:");
         scanf("%d",&i);
     }
     while(i !=0)
     {
         while(i > 4 || i<0)
         {
             printf("\n输入错误请重新输入:\n");
             printf("1.树的图形 2.先序遍历 3.层序遍历 4.释放空间 0 to exit:");
             scanf("%d",&i);
         }
         while(i !=6)
         {
             while(i > 6 || i<0)
             {
                 printf("\n输入错误请重新输入:\n");
                 printf("1.树的图形 2.先序遍历 3.层序遍历 4.释放空间 0 to exit:");
                 scanf("%d",&i);
             }
             switch(i)
             {
             case 0 :
                 printf("\n释放所有空间...\n");
                 freeAllNodes(*pbtree);
                 printf("空间释放完毕\n");
                 exit(1);
                 getch();
             case 1 :
                 printf("\n树的图形:\n");
                 outputTree(*pbtree,totalSpace);
                 break;
             case 2 :
                 printf("\n先序遍历:\n");
                 preOrder(*pbtree);
                 printf("\n\n");
                 break;
             case 3 :
                 printf("\n层序遍历:\n");
                 inOrder(*pbtree);
                 printf("\n\n");
                 break;
             }
             printf("请选择操作:\n");
             printf("1.树的图形 2.先序遍历 3.层序遍历 4.释放空间 0 to exit:");
             scanf("%d",&i);
         }
         if(i==4)
         {
             printf("\n释放空间:\n");
             freeAllNodes(*pbtree);
             printf("释放空间完.");
         }
         printf("\n\n现在建立新的二叉树...\n");
         printf("用字符a-z或者是A-Z构建二叉树,用字符@代表结束当前结点左或者右结点的字符，每输入一个字符回车确定:\n示范格式(A  B  C @  @  D  @  @  E  F  @  @  G  @  @)\n");
         pbtree = Create_BinTreeRoot();
         printf("树的图形为:\n");
         outputTree(*pbtree,totalSpace);
         printf("请选择操作:\n");
         printf("1.树的图形 2.先序遍历 3.层序遍历 4.释放空间 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;
}