数据结构重学日记（二十二）二叉树的层次遍历

二叉树的层次遍历也属于非递归遍历，和之前先序、中序、后序遍历的区别在于层次遍历需要借助队列来实现。

层次遍历的操作规则如下：

• 空树，什么都不做直接返回
• 从树的第一层开始访问，自上而下逐层遍历，在同一层中的树按照从左到右的顺序对结点逐个访问。

其实也就是拿到二叉树后先把根结点入队，打印出值后再判断一下有没子结点，有就先左后右入队，没有就下一个。

还以这个树为例好了：

二叉树

访问顺序为 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("创建节点失败，无法分配可用内存...");
            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);

    }
}