二叉树的层次遍历也属于非递归遍历,和之前先序、中序、后序遍历的区别在于层次遍历需要借助队列来实现。
层次遍历的操作规则如下:
- 空树,什么都不做直接返回
- 从树的第一层开始访问,自上而下逐层遍历,在同一层中的树按照从左到右的顺序对结点逐个访问。
其实也就是拿到二叉树后先把根结点入队,打印出值后再判断一下有没子结点,有就先左后右入队,没有就下一个。
还以这个树为例好了:
二叉树
访问顺序为 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);
}
}
网友评论