www.pudn.com > datastructor.rar > BiTree.c

#include  
 
/*------------- 二叉树的二叉链表存储表示 -------------*/ 
typedef enum {OVERFLOW = -1, ERROR = 0, FALSE = 0, TRUE, OK} Status; 
typedef int TElemType; 
typedef struct BiTNode { 
    TElemType   data; 
    struct BiTNode *lchild, *rchild; 
}BiTNode, *BiTree; 
 
/*-------------------- 栈的存储表示 --------------------*/  
#define STACK_INIT_SIZE 10 
#define STACKINCREMENT  5 
//typedef enum {TURE, FAKSE} boolean 
typedef BiTree SElemType; 
typedef struct { 
    SElemType *base; 
    SElemType *top; 
    int stacksize; 
}SqStack; 
/*----------------栈的基本操作的实现 ------------------*/ 
void InitStack( SqStack *S ) { 
    S->base = (SElemType *)  
                malloc(STACK_INIT_SIZE * sizeof(SElemType)); 
    S->top = S->base; 
    S->stacksize = STACK_INIT_SIZE; 
} 
 
void Push(SqStack *S, SElemType e) { 
    if(S->top - S->base >= S->stacksize) { 
        S->base = (SElemType *) realloc(S->base, 
                (S->stacksize + STACKINCREMENT) * sizeof(SElemType));  
        S->top = S->base + S->stacksize;   
        S->stacksize += STACKINCREMENT; 
    } 
    *S->top++ = e; 
} 
 
void Pop(SqStack *S, SElemType *e) { 
    //if(S->top == S->base) eixt(-1); 
    *e = *--S->top; 
} 
 
int StackEmpty(SqStack *S) { 
    if(S->top == S->base) return 1; 
    return 0; 
} 
 
void GetTop(SqStack *S, SElemType *e) { 
    *e = *--S->top; 
}     
 
 
/*---------------- 二叉树的基本操作的实现 -----------------*/ 
Status CreateBiTree(BiTree *Tr){ 
    BiTree T; 
    TElemType   ch; 
     
    printf("Enter element:\n"); 
    scanf("%d", &ch); 
    if(ch == 0) T = NULL; 
    else{ 
        T = (BiTNode *)malloc(sizeof(BiTNode)); 
        if(!T) exit(OVERFLOW); 
        T->data = ch; 
        CreateBiTree( &(T->lchild) ); 
        CreateBiTree( &(T->rchild) ); 
    } 
    return OK; 
} 
 
Status PreOrderTraverse(BiTree T, Status (* Visit)(TElemType e) ){ 
    // 
    // 
} 
/* 
Status InOrderTraverse(BiTree T, Status (* Visit) (TElemType e) ){ 
    SqStack S; SElemType p; 
     
    InitStack(&S); Push(&S, T); 
    while(!StackEmpty(&S) ){ 
        while(GetTop(&S, &p) && p) Push(&S, p->lchild); 
        Pop(&S, &p); 
        if(!StackEmpty(&S) ){ 
            Pop(&S, &p); if(!Visit(p->data) ) return ERROR; 
            Push(&S, p->rchild); 
        } 
    } 
    return OK; 
} 
           
Status InOrderTraverse(BiTree T, Status (* Visit) (TElemType e) ){ 
    // 
    // 
    SqStack S; InitStack(&S); 
    BiTree p = T; 
     
    while(p || !StackEmpty(&S) ){ 
        if(p) { Push(&S, p); p = p->lchild; } 
        else{ 
            Pop(&S, &p); if(!Visit(p->data) ) return ERROR; 
            p = p->rchild; 
        } 
    } 
    return OK; 
} 
 
Status PostOrderTraverse(BiTree T, Status (* Visit)(TElemType e) ){ 
    // 
    // 
} 
 
Status LevelOrderTraverse(BiTree T, Status (* Visit)(TElemType e) ){ 
    // 
    // 
}  
*/ 
/*--------------------- main()函数 ---------------------*/ 
Status PrintElement(TElemType e){ 
    printf("%3d", e); 
    return OK; 
} 
     
int main() 
{ 
    BiTree tree; 
    
    CreateBiTree(&tree); 
    //printf("%d, %d, %d\n", tree->data, tree->lchild->data, tree->rchild->data); 
     
    //InOrderTraverse(tree, PrintElement); 
    system("pause"); 
    return 0; 
}