二叉树的先后中序遍历与层次遍历

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

typedef struct _bitree_
{
    int data;
    //char data; 鎵撳嵃瀛楁瘝锛?
    struct _bitree_ *lchild , *rchild;
}bitree;

bitree *CreatBittree(int i,int n)
{
    bitree *root;

    root = (bitree *)malloc(sizeof(bitree));
    root->data = i;

    if(2*i <= n)
    {
        root->lchild = CreatBittree(2*i,n);
    }else{
        root->lchild = NULL;
    }

    if(2*i + 1 <= n)
    {
        root->rchild = CreatBittree(2*i + 1 , n);
    }else{

        root->rchild = NULL;
    }

    return root;
}

void PreOrder(bitree *root)
{
    if(NULL==root)
        return;

    printf("%4d",root->data);

    PreOrder(root->lchild);
    PreOrder(root->rchild);

    return;
}

void InOrder(bitree *root)
{
    if(NULL == root)
    {
        return ;
    }

    InOrder(root ->lchild);
    printf("%4d",root->data);
    InOrder(root ->rchild);

    return ;
}
//
//灞傛閬嶅巻锛屽畾涔夐槦鍒楋紱
//
typedef bitree *datatype;

typedef struct _node_
{
    datatype data;
    struct _node_ *next;
}linknode, *linklist;

typedef struct
{
    linklist front ,rear;
}linkqueue;

linkqueue *Creatlinkqueue()
{
    linkqueue *lq;

    lq = (linkqueue *)malloc(sizeof(linkqueue));

    lq->front = lq->rear = (linklist)malloc(sizeof(linknode));
    lq->front->next =NULL;

    return lq;
}

int EmptyLinkqueue(linkqueue *lq)
{
    return (lq->front == lq->rear);
}

void Enlinkqueue(linkqueue *lq,datatype x)
{
    linklist p;

    p = (linklist)malloc(sizeof(linknode));
    p ->data = x;
    p ->next = NULL;
    lq->rear->next = p;
    lq ->rear = p;

    return ;
}

datatype Delinkqueue(linkqueue *lq)
{
    if(EmptyLinkqueue(lq))
        return ;

    linklist p = (linklist)malloc(sizeof(linklist));

    p = lq->front ; //绉诲姩涓娆ront鎸囬拡锛涗粠绗竴涓妭鐐瑰紑濮嬪幓鍑洪槦锛?
    lq->front = p->next;
    free(p);

    return lq->front->data;
}

//
//灞傛閬嶅巻锛?
//
void NoOrder(bitree *root)
{
    if(NULL == root)
        return;
    linkqueue *lq = Creatlinkqueue();

    Enlinkqueue(lq , root);//鍏堝叆闃熸牴锛?
    while(!EmptyLinkqueue(lq))
    {
        root = Delinkqueue(lq); //鏈夊簭鍑洪槦锛屽苟灏嗗叾瀛愬瀛愬叆闃燂紱閫掑綊锛?
        printf("%4d",root->data);

        if(root ->lchild != NULL)
            Enlinkqueue(lq ,root->lchild);
        if(root->rchild!=NULL)
            Enlinkqueue(lq ,root->rchild);
    }

    return ;
}

void PostOrder(bitree *root)
{
    if(NULL == root)
        return ;

    PostOrder(root->lchild);
    PostOrder(root->rchild);
    printf("%4d",root->data);
}

int main()
{
    bitree *root;

    root = CreatBittree(1 , 10);

    printf("PreOrder:\n");
    PreOrder(root);
    printf("\n");

    printf("InOrder:\n");
    InOrder(root);
    printf("\n");

    printf("PostOrder:\n");
    PostOrder(root);
    printf("\n");

    printf("NoOrder:\n");
    NoOrder(root);
    printf("\n");

    return 0;

}