C 언어 는 이 진 트 리 데이터 구 조 를 만 들 고 여러 가지 사 이 를 옮 겨 다 닙 니 다.

RT, 데이터 구조 수업 을 들 을 때 쓴 것, 주석 뒤에 덧 붙 였 습 니 다. 수업 을 들 을 때 진지 하 게 듣 지 못 했 습 니 다. 먼저 여기에 두 었 다가 나중에 천천히 이해 하 겠 습 니 다. 사용 할 때 먼저 뿌리 결점 을 만 들 고 왼쪽 아이, 왼쪽 아 이 를 차례대로 만 듭 니 다. 0 을 입력 하면 이 결점 이 비어 있 음 을 표시 합 니 다. 왼쪽 / 오른쪽 아 이 를 만 들 때 왼쪽 / 오른쪽 아 이 를 뿌리 결점 으로 생각 합 니 다.그들 에 게 속 하 는 좌우 아 이 를 재 귀적 으로 만들다.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

typedef struct BiTree{
    int data;
    struct BiTree* lchild;
    struct BiTree* rchild;
}BiTree, *PBiTree;

typedef struct Stack{
    BiTree* data[128];
    int top;
}Stack;

void stack_init(Stack* pStack)
{
    memset(pStack, 0, sizeof(Stack));
    pStack->top = -1;
}

BiTree* stack_pop(Stack* pStack)
{
    if(pStack->top == -1)
        return NULL;
    return pStack->data[pStack->top--];
}

BiTree* stack_get_top(Stack* pStack)
{
    if(pStack->top == -1)
        return NULL;
    else
        return pStack->data[pStack->top];
}

int stack_push(Stack* pStack, BiTree* pBiTree)
{
    if(pStack->top == 127)
        return 0;
    pStack->data[++pStack->top] = pBiTree;
    return 1;
}

int stack_is_empty(Stack* pStack)
{
    return pStack->top == -1;
}

int bitree_create(BiTree** ppBiTree)
{
    int data;
    for(;;){
        printf("      :");
        if(scanf("%d", &data) == 1)
            break;
        fflush(stdin);
    }
    if(data == 0){
        (*ppBiTree) = NULL;
        return 1;
    }else{
        (*ppBiTree) = (PBiTree)malloc(sizeof(BiTree));
        if(!*ppBiTree){
            perror("      ");
            return 0;
        }else{
            memset(*ppBiTree, 0, sizeof(BiTree));
            (*ppBiTree)->data = data;
            bitree_create(&(*ppBiTree)->lchild);
            bitree_create(&(*ppBiTree)->rchild);
        }
    }
    return 1;
}

//     
void bitree_free(BiTree* pBiTree)
{
    if(pBiTree){
        bitree_free(pBiTree->lchild);
        bitree_free(pBiTree->rchild);
        free(pBiTree);
        pBiTree = NULL;
    }
}

/*         */
void PreOrderTraverse(BiTree* pBiTree)
{
    Stack stk;
    BiTree* pb = pBiTree;
    stack_init(&stk);
    while(pb || !stack_is_empty(&stk)){
        while(pb){
            printf("%d ", pb->data);
            stack_push(&stk, pb);
            pb = pb->lchild;
        }
        pb = stack_pop(&stk);   
        pb = pb->rchild;
    }
}
/*        */
void PreOrderTraverse2(BiTree* pBiTree)
{
    if(pBiTree){
        printf("%d ", pBiTree->data);//    
        PreOrderTraverse2(pBiTree->lchild);//     
        PreOrderTraverse2(pBiTree->rchild);//     
    }
}

/*          */
void InOrderTraverse2(BiTree* pBiTree)
{
    if(pBiTree){
        InOrderTraverse2(pBiTree->lchild);
        printf("%d ", pBiTree->data);
        InOrderTraverse2(pBiTree->rchild);
    }
}

/*         2 */
void InOrderTraverse3(BiTree* pBiTree)
{
    Stack stk;
    BiTree* pb = NULL;
    stack_init(&stk);
    pb = pBiTree;
    while(pb || !stack_is_empty(&stk)){
        if(pb){
            stack_push(&stk, pb);//     
            pb = pb->lchild;//     
        }else{
            //     ,      ,      
            pb = stack_pop(&stk);
            printf("%d ", pb->data);
            pb = pb->rchild;
        }
    }
}

/*           */
void InOrderTraverse(BiTree* pBiTree)
{
    Stack stk;
    BiTree* pb = NULL;
    stack_init(&stk);//      
    stack_push(&stk, pBiTree);//     
    while(!stack_is_empty(&stk)){
        while((pb=stack_get_top(&stk)))
            stack_push(&stk, pb->lchild);//      
        pb = stack_pop(&stk);//         
        if(!stack_is_empty(&stk)){
            pb = stack_pop(&stk);//        /   
            printf("%d ", pb->data);
            stack_push(&stk, pb->rchild);//     
        }
    }
}

/*           */
void PostOrderTraverse(BiTree* pBiTree)
{
    Stack stk;
    BiTree* pb = NULL;
    BiTree* pre = NULL;
    stack_init(&stk);
    while(pBiTree || !stack_is_empty(&stk)){
        while(pBiTree){
            stack_push(&stk, pBiTree);
            pBiTree = pBiTree->lchild;
        }
        pBiTree = stack_get_top(&stk);
        if(!pBiTree->rchild || pBiTree->rchild == pre){
            printf("%d ", pBiTree->data);
            stack_pop(&stk);
            pre = pBiTree;
            pBiTree = NULL;
        }else{
            pBiTree = pBiTree->rchild;
        }
    }
}

/*          */
void PostOrderTraverse2(BiTree* pBiTree)
{
    if(pBiTree){
        PostOrderTraverse(pBiTree->lchild);
        PostOrderTraverse(pBiTree->rchild);
        printf("%d ", pBiTree->data);
    }
}


int main(void)
{
    BiTree* pbt = NULL;
    bitree_create(&pbt);
    printf("
");
    printf("         :\t");
    PreOrderTraverse(pbt);
    printf("
");
    printf("        :\t");
    PreOrderTraverse2(pbt);
    printf("
");
    printf("         :\t");
    InOrderTraverse(pbt);
    printf("
");
    printf("        :\t");
    InOrderTraverse2(pbt);
    printf("
");
    //printf("        2:\t");
    //InOrderTraverse3(pbt);
    //printf("
");
    printf("         :\t");
    PostOrderTraverse(pbt);
    printf("
");
    printf("        :\t");
    PostOrderTraverse2(pbt);
    printf("
");
    printf("
");
    bitree_free(pbt);
    system("pause");
    return 0;
}