二叉樹的層次遍歷也屬于非遞歸遍歷屡谐，和之前先序、中序蝌数、后序遍歷的區(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);
}
}
