두 갈래 트리 기본 조작, 비귀속 중순, 후순 두 갈래 트리 두루 훑어보기

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define STACK_INIT_SIZE 50
typedef struct BiTree{
    int data;
    int flag;
    struct BiTree *lchild,*rchild;
}BiTNode;
typedef struct Stack{
    BiTNode **base;
    BiTNode **top;
    int stacksize;
}SqStack; 
int InitStack(SqStack *s)
{
    s->base =(BiTNode **)malloc(STACK_INIT_SIZE*sizeof(BiTNode*));
    s->top =s->base ;
    s->stacksize =STACK_INIT_SIZE;
    return 0;
}
int IsEmpty(SqStack *s)
{
    if(s->base ==s->top )
    return 1;
    return 0;
}
int Push(SqStack *s,BiTNode *T)
{
    *(s->top)=T;
    s->top ++;
    return 0;
}
BiTNode *Pop(SqStack *s)
{
    if(s->base ==s->top )
    exit(0);
    s->top--;
    return *(s->top);
}
BiTNode *PreOrderCreate(BiTNode *T)//  
{   
    int datum;
    scanf("%d",&datum);
    if(datum==0)
    {
    T=NULL;
    return T;
    }

    T=(BiTNode *)malloc(sizeof(BiTNode));
    if(!T)
    exit(0);
    T->data =datum;
    T->lchild =PreOrderCreate(T->lchild);
    T->rchild =PreOrderCreate(T->rchild);

    return T;
}
void PreOrderPrint(BiTNode *T)//  
{

    if(T!=NULL)
    {
        printf("%d ",T->data );
        PreOrderPrint(T->lchild );
        PreOrderPrint(T->rchild );
    }
}
void InOrderPrint(BiTNode *T)//  
{
    BiTNode *t=T;
    SqStack *s=(SqStack *)malloc(sizeof(SqStack));
    InitStack(s);
    while(t||!IsEmpty(s))
    {
        while(t)
        {
            Push(s,t);
            t=t->lchild ;
        }
        if(!IsEmpty(s))
        {
            t=Pop(s);
            printf("%d ",t->data );
            t=t->rchild ;
        }
    }
}
void PostOrderPrint(BiTNode *T)//  
{
    BiTNode *t=T;
    SqStack *s=(SqStack *)malloc(sizeof(SqStack));
    InitStack(s);
    while(t||!IsEmpty(s))
    {
        if(t)
        {
            t->flag =1;
            Push(s,t);
            t=t->lchild ;
        }
        else
        {
            t=Pop(s);
            if(t->flag ==1)
            {
                t->flag =2;
                Push(s,t);
                t=t->rchild ;
            }
            else
            {
                printf("%d ",t->data );
                t=NULL;
            }
        }
    }
} 
int main(int argc,char *argv[])
{
    BiTNode *T;
    T=PreOrderCreate(T);
    PreOrderPrint(T);
    printf("
"); InOrderPrint(T); printf("
"); PostOrderPrint(T); return 0; }

좋은 웹페이지 즐겨찾기