二叉樹的層次遍歷也屬于非遞歸遍歷，和之前先序、中序、后序遍歷的區(qū)別在于層次遍歷需要借助隊列來實現(xiàn)。

層次遍歷的操作規(guī)則如下：

• 空樹，什么都不做直接返回
• 從樹的第一層開始訪問，自上而下逐層遍歷，在同一層中的樹按照從左到右的順序?qū)Y(jié)點逐個訪問。

其實也就是拿到二叉樹后先把根結(jié)點入隊，打印出值后再判斷一下有沒子結(jié)點，有就先左后右入隊，沒有就下一個。

還以這個樹為例好了：

二叉樹

訪問順序為 A B C D E F G 。

代碼

//
// Created by wu on 19-1-26.
//

#include <stdlib.h>
#include <stdbool.h>

#define MaxSize 100

typedef struct BiNode {
    char data;
    struct BiNode *lchild, *rchild;
} BiNode, *BiTree;

typedef BiTree ElemType;
typedef struct {
    ElemType data[MaxSize];
    int front, rear;
} SqQueue;

void queue_init(SqQueue *SQ) {
    SQ->front = SQ->rear = 0;
}

bool en_queue(SqQueue *SQ, ElemType x) {
    if ((SQ->rear + 1) % MaxSize == SQ->front) return false; // 隊滿
    SQ->data[SQ->rear] = x;
    SQ->rear = (SQ->rear + 1) % MaxSize;
    return true;
}

ElemType de_queue(SqQueue *SQ, ElemType x) {
    if (SQ->rear == SQ->front) return false; // 隊空
    x = SQ->data[SQ->front];
    SQ->front = (SQ->front + 1) % MaxSize;
    return x;
}

bool is_empty(SqQueue *SQ) {
    if (SQ->front == SQ->rear) return true;
    else return false;

}

bool created_tree(BiTree *T) {
    char ch;
    scanf("%c", &ch);
    if (ch == '#') {
        *T = NULL;
    } else {
        BiTree p = (BiTree) malloc(sizeof(BiNode));
        if (T == NULL) {
            printf("創(chuàng)建節(jié)點失敗，無法分配可用內(nèi)存...");
            exit(-1);
        } else {
            p->data = ch;
            *T = p;
            created_tree(&p->lchild);
            created_tree(&p->rchild);
        }
    }
    return true;
}
void level_foreach_tree(SqQueue *SQ, BiTree T) {
    queue_init(SQ);
    BiTree p;
    en_queue(SQ, T);
    while (!is_empty(SQ)) {
        p = de_queue(SQ, p);
        printf("%c ", p->data);
        if(p->lchild != NULL)
            en_queue(SQ, p->lchild);
        if(p->rchild != NULL)
            en_queue(SQ, p->rchild);

    }
}