데이터 구조 - 이 진 트 리 사례 분석

#include
#include
#include
#include 
#include 
/*                 ，    */
#define MAX 100

typedef struct BNode/*        */
{
    int data;
    struct BNode *l_child;
    struct BNode* r_child;
} BNode;
int e,z,i,j,k;//         。
BNode *t,*q,*p;
typedef struct//        
{
    BNode *a[MAX];
    int top;
}sqstack;
typedef struct//        ，           
{
    BNode *a[MAX];
    int front;
    int rear;
}squeue;
//          ，         x      ，      ，     ，               
BNode *Creat_One()//    scanf         
{
    BNode *p;
    int x;
    scanf("%d",&x);
    if((p=(BNode*)malloc(sizeof(BNode)))==NULL)//   p      ，      ，            
    {
        printf("       .
");
        return NULL;
    }
    else
    {
        p->data=x;
        p->l_child=NULL;
        p->r_child=NULL;
    }
    return p;//p             ，    。

}
void push(sqstack *s,BNode *x)//      ，         +1
{
    if(s->top==MAX)
    {
        printf("   .
");
    }
    else
    {
        s->top++;
        s->a[s->top]=x;// x  
    }
}
BNode * pop(sqstack *s)//    ，              
{
    BNode *x;
    if(s->top==0)
    {
        printf("    .
");
    }
    else
    {
        x=s->a[s->top];
        s->top--;
    }
    return x;//         
}
/*      *///       。        
void enqueue(squeue *Q,BNode *x)// x      
{
    if((Q->rear+1)%MAX==Q->front)//                ，         
    {
        printf("    ");
    }
    else
    {

        Q->a[Q->rear]=x; Q->rear=(Q->rear+1)%MAX;
    }
}
BNode *delqueue(squeue*Q)
{ BNode *x;
    if(Q->rear==Q->front)
    {
        printf("     .
");

    }
    else
    {
        x=Q->a[Q->front];
        Q->front=(Q->front+1)%MAX;//       return x;
    }
}/*              */
BNode *Creat_Bt1()//  Creat_One       
{ //  ，         ，           ，                0       
    //      2^0+2^1+...2^n ，    0           2^(n+1) 
    BNode *t; printf("
data=");
    scanf("%d",&e); if(e==0) t=NULL;
    else { t=(BNode*)malloc(sizeof(BNode));
        t->data=e; t->l_child=Creat_Bt1();/*       */
        t->r_child=Creat_Bt1(); } return t;}/*   *///             ，         
/*    N         ，                ，
          1               i     1.  i>1，
   i            /2 i=1           2.  2i<=n   i             2i,
  2*i  n       3.  2*i+1<=n   i          2*i+1,  i       */
BNode *Creat_Bt0()
{ BNode *t,*p,*v[20];
    printf("
 i data=?");
    scanf("%d %d",&i,&e);
    while(i!=0&&e!=0)
    {
        p=(BNode*)malloc(sizeof(BNode));
        p->data=e; p->r_child=NULL;
        p->l_child=NULL; v[i]=p;
        if(i==1)
        {
            t=p;
        }
        else { j=i/2; if(i%2==0)
            {
                v[j]->l_child=p;
            } else { v[j]->r_child=p; }
        }
        printf("
 i data=?");
        scanf("%d %d",&i,&e);
    } return t;}
/*     */
void preorder(BNode *p)
{ if(p)
    { printf("%3d",p->data);
        preorder(p->l_child);
        preorder(p->r_child);
    }
}
/*     ，  */
void inorder(BNode*p)
{ if(p)
    { inorder(p->l_child);
        printf("%3d",p->data);
        inorder(p->r_child);
    }}
/*        */
void inorder_2(BNode *t)
{ sqstack s; BNode *p;
    s.top=0; push(&s,t);
    while(s.top!=0)
    { while(s.a[s.top]!=NULL)
        {
            p=s.a[s.top];
            push(&s,p->l_child);
        } p=pop(&s); if(s.top!=0)
        { p=pop(&s);
            printf("%3d",p->data);
            push(&s,p->r_child);
        }
    }
}
void level(BNode *t)
{ squeue q; BNode *p;
    q.front=0; q.rear=0;
    enqueue(&q,t);
    while(q.rear!=q.front)
    { p=delqueue(&q);
        printf("%3d",p->data);
        if(p->l_child)enqueue(&q,p->l_child);
        if(p->r_child)enqueue(&q,p->r_child);
    }
    printf("
");}
int e,z,i,j,k;BNode *t,*q,*p;
void main()
{
    do {
        printf("

");
        printf("

 0.       0");
        printf("

 1.       1");
        printf("

 2.       ");
        printf("

 3.        ");
        printf("

 4.       ");
        printf("

 5.  ");
        printf("     ：
");
        scanf("%d",&k);
        switch(k)
        {   case 0:
            {
                printf("      
");
                t=Creat_Bt0(); preorder(t);
                break;
            }
            case 1:
            {
                printf("      ，       0");
                t=Creat_Bt1(); preorder(t); break;
            }
            case 2:
            { printf("      :
");
                inorder(t);
                break;
            }
            case 3:
            {
                printf("       :
");
                inorder_2(t);
                break;
            }
            case 4:
            { printf("     :
");
                level(t); break; }
            case 5:
                exit(0);
            }
    }
    while(k>=0&&k<=5); printf("  
");
}