二叉树的层序遍历

顾名思义，是按照树的每一层在进行遍历：

先创建二叉树：

typedef struct TreeNode {
  char element;
  struct TreeNode* right;
  struct TreeNode* left;
}* TNode;

int main() {
  TNode a = malloc(sizeof(struct TreeNode));
  TNode b = malloc(sizeof(struct TreeNode));
  TNode c = malloc(sizeof(struct TreeNode));
  TNode d = malloc(sizeof(struct TreeNode));
  TNode e = malloc(sizeof(struct TreeNode));
  TNode f = malloc(sizeof(struct TreeNode));
  a->elememt = 'A';
  b->element = 'B';
  c->element = 'C';
  d->element = 'D';
  e->element = 'E';
  f->element = 'F';
  
  a->left = b;a->right = c;
  b->left = d;b->right = NULL;
  c->left = e;c->right = f;
  d->left = d->right = NULL;
  e->left = e->right = NULL;
  f->left = f->right = NULL;
}

按照从上到下、每层从左到右的顺序打印每一个结点即可完成层序遍历，最后遍历的结果就是：ABCDEF。

可以利用队列来实现层序遍历，首先将根结点入队，接着循环执行以下步骤：

• 进行出队操作，得到一个结点，并打印结点的值。
• 将此结点的左右孩子结点依次入队。

不断重复以上步骤，直到队列为空。

我们来用链表创建一个链式队列：

typedef struct LinkedQueue {
  TNode element;  //注意这里队列元素是二叉树的结点
  struct LinkedQueue* next;
}* QNode;

typedef struct LinkedQueue {
  QNode rear;
  QNode front;
}* Queue;

_Bool initQueue(Queue queue) {
  QNode node = malloc(sizeof(struct LinkedQueue));
  if (node == NULL) return 0;
  node->next = NULL;
  queue->rear = queue->front = node;
  return 1;
}

_Bool offerQueue(Queue queue, TNode element) {
  QNode node = malloc(sizeof(struct LinkedQueue));
  if (node == NULL) return 0;
  node->element = element;
  node->next = NULL;
  queue->rear->next = node;
  que ue->rear = node;
  return 1;
}

_Bool qisEmpty(Queue queue) {
  return queue->rear == queue->front;
}

TNode pollQueue(Queue queue) {
  TNode e = queue->front->next->element;
  QNode tmp = queue->front->next;
  queue->front->next = queue->front->next->next;
  if (queue->rear == tmp) queue->rear = queue->front;
  free(tmp);
  return e;
}

来分析一下每次循环，栈的情况，

A入队：

接着出队，打印出队元素A，再将A的左右孩子B、C结点入队：

B出队，打印B，再将B的左右孩子结点D入队：

C出队，打印C，再将C的左右孩子结点E、F入队：

继续循环这个出队、打印、入队的操作，若出队结点无左右孩子结点，那么就在打印后继续出队，直到队列为空，跳出这个循环。

现在终于可以实现层序遍历了：

void levelOrder(TNode root) {
  struct Queue queue;
  initQueue(&queue);
  offerQueue(&queue, root);  //先让根节点入队
  while (!qisEmpty(&queue)) {  //维持条件为栈非空
    TNode node = pollQueue(&queue);
    printf("%c ", node->element);
    if(node->left) offerQueue(&queue, node->left);  //有左孩子结点，将此结点入队
    if(node->right) offerQueue(&queue, node->right);  //有右孩子结点，将此结点入队
  }
}

以下附上完整代码：

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

typedef struct TreeNode {
  char element;
  struct TreeNode* right;
  struct TreeNode* left;
}* TNode;

//-----------队列--------------
typedef struct LinkedQueue {
  TNode element;  //注意这里队列元素是二叉树的结点
  struct LinkedQueue* next;
}* QNode;

typedef struct Queue {
  QNode rear;
  QNode front;
}* Queue;

_Bool initQueue(Queue queue);
_Bool offerQueue(Queue queue, TNode element);
_Bool qisEmpty(Queue queue);
TNode pollQueue(Queue queue);
//-----------------------------
void levelOrder(TNode root);  //实现层序遍历

int main() {
  TNode a = malloc(sizeof(struct TreeNode));
  TNode b = malloc(sizeof(struct TreeNode));
  TNode c = malloc(sizeof(struct TreeNode));
  TNode d = malloc(sizeof(struct TreeNode));
  TNode e = malloc(sizeof(struct TreeNode));
  TNode f = malloc(sizeof(struct TreeNode));
  a->element = 'A';
  b->element = 'B';
  c->element = 'C';
  d->element = 'D';
  e->element = 'E';
  f->element = 'F';
  
  a->left = b;a->right = c;
  b->left = d;b->right = NULL;
  c->left = e;c->right = f;
  d->left = d->right = NULL;
  e->left = e->right = NULL;
  f->left = f->right = NULL;
  levelOrder(a);
}

_Bool initQueue(Queue queue) {
  QNode node = malloc(sizeof(struct LinkedQueue));
  if (node == NULL) return 0;
  node->next = NULL;
  queue->rear = queue->front = node;
  return 1;
}

_Bool offerQueue(Queue queue, TNode element) {
  QNode node = malloc(sizeof(struct LinkedQueue));
  if (node == NULL) return 0;
  node->element = element;
  node->next = NULL;
  queue->rear->next = node;
  queue->rear = node;
  return 1;
}

_Bool qisEmpty(Queue queue) {
  return queue->rear == queue->front;
}

TNode pollQueue(Queue queue) {
  TNode e = queue->front->next->element;
  QNode tmp = queue->front->next;
  queue->front->next = queue->front->next->next;
  if (queue->rear == tmp) queue->rear = queue->front;
  free(tmp);
  return e;
}

void levelOrder(TNode root) {
  struct Queue queue;
  initQueue(&queue);
  offerQueue(&queue, root);  //先让根节点入队
  while (!qisEmpty(&queue)) {  //维持条件为栈非空
    TNode node = pollQueue(&queue);
    printf("%c ", node->element);
    if(node->left) offerQueue(&queue, node->left);  //有左孩子结点，将此结点入队
    if(node->right) offerQueue(&queue, node->right);  //有右孩子结点，将此结点入队
  }
}

运行后就是层序遍历的结果：

当然，二叉树的层序遍历也可以用函数递归来实现，限于篇幅原因，递归的方法以后再进行讲解学习。