【二叉树】层序遍历

前序&中序&后序遍历：深度优先遍历dfs

层序遍历：广度优先遍历bfs

层序遍历概念&结构

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。

设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历的实现

层序遍历用队列实现，需要把队列的代码拷贝到多文件项目里面：单链表实现【队列】_单链表队列出队-CSDN博客

整体思路

• 把根节点放入队列
• 保存根节点在tmp，打印根节点（遍历），然后把根节点的左右孩子入队列
• 根节点出队列
• 循环上诉过程（父亲出的时候就带入父亲的左右孩子）
• 若为NULL则不入队列
• 达到一层一层遍历（层序遍历）

• 注意
• tmp保存的是树节点的地址
  
• 销毁的是队列的头节点（里面也是树节点的地址）
  
• 不会销毁树的节点
  

代码实现

测试代码在前面博文有：链式二叉树（1）-CSDN博客

//层序遍历
void LevelOrder(BTNode* root)
{
  Queue pq;
  QueueInit(&pq);
  if(root)
  QueuePush(&pq, root);
  while (!QueueEmpty(&pq))
  {
    BTNode* tmp = QueueFront(&pq);//队列头的元素
    QueuePop(&pq);//出元素到队头
    printf("%d ", tmp->data);
    if(tmp->left)
    QueuePush(&pq, tmp->left);
    if(tmp->right)
    QueuePush(&pq, tmp->right);
  }
  QueueDestroy(&pq);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  LevelOrder(root);
  BinaryTreeDestory(root);
  root = NULL;
  return 0;
}

图示理解

BT升级

若我们想要一层一层打印，怎样去一层一层打印？

整体思路

• 设置一个变量LeveSize记录每层的个数
• 每一层的数据个数，控制一层一层数据出队列
• 换行打印

代码实现

//BT升级换行打印
//层序遍历
void LevelOrder(BTNode* root)
{
  Queue pq;
  QueueInit(&pq);
  if (root)
    QueuePush(&pq, root);
  int levesize = 1;
  while (!QueueEmpty(&pq))
  {
    while (levesize--)
    {
      BTNode* tmp = QueueFront(&pq);//队列头的元素
      QueuePop(&pq);//出元素到队头
      printf("%d ", tmp->data);
      if (tmp->left)
        QueuePush(&pq, tmp->left);
      if (tmp->right)
        QueuePush(&pq, tmp->right);
    }
    printf("\n");
    levesize = QueueSize(&pq);//队列里面的元素个数
  }
  QueueDestroy(&pq);
}
int main()
{
  BTNode* root = CreatBinaryTree();
  LevelOrder(root);
  BinaryTreeDestory(root);
  root = NULL;
  return 0;
}

图示理解

应用

大家可以思考扫雷用递归去实现？QQ加好友的好友？

• 展开形式：广度优先遍历
• 展开形式：深度优先遍历
• 八度递归
• 层序遍历：加好友的好友（搜索算法）>>>>后面的算法篇章我们会介绍

题目

练习：请写出下面的前序/中序/后序/层序遍历

1.某完全二叉树按层次输出（同一层从左到右）的序列为 ABCDEFGH 。该完全二叉树的前序序列为（ ）

A ABDHECFG

B ABCDEFGH

C HDBEAFCG

D HDEBFGCA

2.二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK;中序遍历：HFIEJKG.则二叉树根结点为（）

A E

B F

C G

D H

3.设一课二叉树的中序遍历序列：badce，后序遍历序列：bdeca，则二叉树前序遍历序列为____。

A adbce

B decab

C debac

D abcde

4.某二叉树的后序遍历序列与中序遍历序列相同，均为 ABCDEF ，则按层次输出（同一层从左到右）的序列为

A FEDCBA

B CBAFED

C DEFCBA

D ABCDEF

答案：AADA

🙂感谢大家的阅读，若有错误和不足，欢迎指正。大家新年快乐！！