二叉树层次遍历、先序、中序、后序遍历

根据二叉树的性质，实现先序，中序，后序的遍历不难，这里主要是层次遍历不好想一点。

对于层次遍历的实现，需要用到链式队列，把每一层的结点的左右指针入队列。判断其左右孩子是否存在，存在则出队列，并且打印出对节点元素的值。

层次遍历意思是指：每一层从左到右依次输出元素的值，就是显示输出第一层的所有元素值，然后是第二层的，依次类推。

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

#define  N 6

//二叉树的结点类型
typedef char TreeType;
typedef struct Treenode
{
    //记录二叉树结点编号
    int n;
    TreeType data;
    struct Treenode *lchild;
    struct Treenode *rchild;
}BiTree;


//链表结点数据类型
typedef BiTree * DataType;
struct node
{
    DataType data;
    struct node *next;
};

//队列头的数据类型
typedef struct
{
    struct node *front;
    struct node *rear;
}LinkQueue;

LinkQueue *create_empty_linkqueue()
{
    struct node *head = NULL;
    LinkQueue *q = NULL;

    //链式队列头结点
    head = (struct node *)malloc(sizeof(struct node));
    head->next = NULL;

    //链式队列的队列头
    q = (LinkQueue *)malloc(sizeof(LinkQueue));
    q->rear = q->front = head;

    return q;
}

int is_empty_linkqueue(LinkQueue *q)
{
    return q->rear == q->front;
}

int enter_linkqueue(LinkQueue *q,DataType data)
{
    struct node *temp = NULL;

    temp = (struct node *)malloc(sizeof(struct node));
    temp->data = data;

    //尾插法
    temp->next = NULL;
    q->rear->next = temp;

    //更新队列尾指针
    q->rear = temp;

    return 0;
}

DataType delete_linkqueue(LinkQueue *q)
{
    struct node *temp = NULL;

    temp = q->front;

    //更新头指针，记录新头结点位置
    q->front = temp->next;

    free(temp);
    temp = NULL;

    return q->front->data;
}

BiTree *alloc_node(int n)//分配空间
{
    BiTree *root = NULL;

    root = (BiTree *)malloc(sizeof(BiTree));
    root->n = n;
    root->lchild = root->rchild = NULL;

    printf("Input %d node data:",n);
    scanf("%c", &root->data);
    while(getchar() != '\n');

    return root;
}

BiTree *create_binary_tree(int n) //递归创建二叉数，先左后右
{
    BiTree *root = NULL;

    root = alloc_node(n);

    if(n * 2 <= N)
    {
        root->lchild = create_binary_tree(2 * n);
    }

    if(n * 2 + 1 <= N )
    {
        root->rchild = create_binary_tree(2 * n + 1);
    }

    return root;
}

//先序遍历   根 左 右
int pre_order(BiTree *root)//递归输出数据，先左后右
{
    if(root==NULL)
    {
        return -1 ;
    }

    printf("(%d:%c) ", root->n,root->data);

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

    return 0;

}

//中序遍历 左 根 右
int mid_order(BiTree *root)
{
    if(root==NULL)
    {
        return -1;
    }

    mid_order(root->lchild);

    printf("(%d:%c) ", root->n,root->data);

    mid_order(root->rchild);

    return 0 ;

}

//后续遍历 左 右 根
int post_order(BiTree *root)
{
    if(root==NULL)
    {
        return -1;
    }

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

    printf("(%d:%c) ", root->n,root->data);

    return 0;

}
void level_travel(BiTree *root)
{
    LinkQueue *q = NULL;
    BiTree *p = NULL;

    q = create_empty_linkqueue();

    //根结点首地址首先入队
    enter_linkqueue(q,root);

    //队列不为空，继续循环
    while(!is_empty_linkqueue(q))
    {
        //二叉树结点首地址出队
        p = delete_linkqueue(q);
        //访问出队元素
        printf("(%d:%c) ",p->n,p->data);

        //判断出队元素是否有左孩子,有则入队
        if(p->lchild != NULL)
        {
            enter_linkqueue(q,p->lchild);
        }

        //判断出队元素是否有右孩子,有则入队
        if(p->rchild != NULL)
        {
            enter_linkqueue(q,p->rchild);
        }
    }
    putchar('\n');

    return ;
}

int main()
{
    BiTree *root = NULL;

    root = create_binary_tree(1); //根结点编号为1

    pre_order(root);
    putchar('\n');

    mid_order(root);
    putchar('\n');

    post_order(root);
    putchar('\n');

    level_travel(root);

    return 0;
}

执行结果：