二叉树先序，中序，后序以及层序遍历

最新复习数据结构，看到课本上的一道关于二叉树遍历的问题，这里主要想记录的是层序遍历的算法，会使用

到队列，程序如下：

/*
 * Copyright (c) 2010-~ zhouyongfei
 *
 * The source code is released for free distribution under the terms of the GNU General Public License
 *
 *
 * Author: alen Chou
 * Created Time: 2010年05月25日 星期二 18时30分57秒
 * File Name: bitree.c
 * Description: 使用先序扩展建立二叉树，然后先序递归遍历，中序递归遍历，后序递归遍历，再利用队列层序遍历
 *
 */

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


typedef struct Node{
    char data;
    struct Node * Lchild;
    struct Node * Rchild;
}BiTNode,*BiTree;//二叉树节点，二叉链表


typedef struct QueueNode{
    BiTree data;
    struct QueueNode *next;
}LinkQueueNode;//队列中的每个节点


typedef struct
{
    LinkQueueNode *front;
    LinkQueueNode *rear;
}LinkQueue;//队列


/*
 * 队列的初始化
 *
 * */
void InitQueue(LinkQueue *Q)
{
    Q->front = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    if(Q->front != NULL){
        Q->rear = Q->front;
        Q->front->next = NULL;
    }else printf("分配空间失败!\n");
}
/*
 * 入队
 *
 * */
void EnterQueue(LinkQueue *Q,BiTree x)
{
    LinkQueueNode *NewNode;
    NewNode = (LinkQueueNode *)malloc(sizeof(LinkQueueNode));
    if(NewNode != NULL){
        NewNode->data = x;
        NewNode->next = NULL;
        Q->rear->next = NewNode;
        Q->rear = NewNode;
    }
}

/*
 *    队列判空
 *
 * */
int QueueIsEmpty(LinkQueue *Q)
{
    if(Q->front == Q->rear)
        return 1;
    else return 0;
}

/*
 * 出队
 *
 * */
void DeleteQueue(LinkQueue *Q,BiTree *x)
{
    LinkQueueNode *p;
    if(Q->front == Q->rear)
        return ;
    p = Q->front->next;
    Q->front->next = p->next;
    if(Q->rear == p)
        Q->rear = Q->front;
    *x = p->data;
    free(p);
}


/*
 * 利用扩展先序遍历序列
 * 创建二叉链表
 */
void CreateBiTree(BiTree *bt)
{
    char ch;
    ch = getchar();
    if(ch == '.') *bt = NULL;
    else
    {
        *bt = (BiTree)malloc (sizeof(BiTNode));
        (*bt)->data = ch;
        CreateBiTree(&((*bt)->Lchild));
        CreateBiTree(&((*bt)->Rchild));
    }
}

/*
 * 先序递归遍历二叉树
 *
 **/
void PreOrder(BiTree root)
{
    if(root != NULL){
        printf("%c ",root->data);
        PreOrder(root->Lchild);
        PreOrder(root->Rchild);
    }
}

/*
 * 后序递归遍历二叉树
 *
 * */
void PostOrder(BiTree root)
{
    if(root != NULL){
        PostOrder(root -> Lchild);
        PostOrder(root -> Rchild);
        printf("%c ",root->data);
    }
}

/*
 * 中序递归遍历二叉树
 *
 * */
void InOrder(BiTree root)
{
    if(root != NULL){
        InOrder(root->Lchild);
        printf("%c ",root->data);
        InOrder(root->Rchild);
    }
}

/*
 *    层序遍历
 *     对给定的二叉树进行层序遍历
 *
 * */
void LayerOrder(BiTree root)
{    
    BiTree *x;
    //这里要记得申请空间

    x = (BiTree *)malloc(sizeof(BiTree));
    if(x == NULL){
        printf("内存分配失败!\n");
    }
    LinkQueue *Q;
    Q = (LinkQueue *)malloc(sizeof(LinkQueue));
    InitQueue(Q);
    EnterQueue(Q,root);
    while(!QueueIsEmpty(Q)){
        DeleteQueue(Q,x);
        printf("%c ",(*x)->data);
        if((*x)->Lchild)EnterQueue(Q,(*x)->Lchild);
        if((*x)->Rchild)EnterQueue(Q,(*x)->Rchild);
    }
}

int main(int argc , char **argv)
{
    BiTree root;
    CreateBiTree(&root);
    printf("先序递归遍历:\n");
    PreOrder(root);
    printf("\n");
    printf("中序递归遍历:\n");
    InOrder(root);
    printf("\n");
    printf("后序递归遍历:\n");
    PostOrder(root);
    printf("\n");
    printf("层序遍历:\n");
    LayerOrder(root);
    printf("\n");
}

测试结果：

zhou@zhou:~/DataStructure/bitree$ ./main 

abd..e..cf..g..

先序递归遍历:

a b d e c f g 

中序递归遍历:

d b e a f c g 

后序递归遍历:

d e b f g c a 

层序遍历:

a b c d e f g 

zhou@zhou:~/DataStructure/bitree$