软考-软件设计师：数据结构-二叉树的遍历（广度优先遍历、深度优先遍历）

作者：马育民 • • 阅读：10058

介绍

二叉树的遍历，把 树上所有节点都访问一遍。因为树不是线性的（不像数组、链表可以从头读到尾），所以必须规定 访问顺序

分类

根据访问顺序分为广度优先遍历、深度优先遍历

广度优先遍历(BFS)

广度优先遍历，breadth-first search, BFS，也叫 层序遍历、层次遍历，核心是按 从上到下、从左到右 的顺序逐层访问节点

深度优先遍历 (DFS)

深度度优先，Depth - First Search，DFS，先往深走，遇到叶子节点再往回走

根据 访问根节点 的时机不同，又分为：

  • 前序遍历：先访问根，然后访问 左节点（如果左节点下还有左节点，），最后访问 右子树
  • 中序遍历：先访问左子树，然后访问 根，最后访问 右子树
  • 后序遍历：先访问左子树，然后访问 右子树，最后访问 根

理解记忆：

  • 先序：根先访问，即：【根-左-右】
  • 中序：根中间访问，即：【左-根-右】
  • 后序：根最后访问，即：【左-右-根】

例子1

二叉树如下图：

层次遍历(从上至下，从左至右)

从上至下，从左至右，上图遍历结果为：

1、2、3、4、5、6、7、8

前序遍历【根-左-右】

先处理根结点，然后处理左子树，最后处理右子树，上图遍历过程：

  1. 先访问根，所以第一个是根节点 1
  2. 访问 1 的左节点 2。节点 2 也是有子结点，继续往下
  3. 访问 2 的左节点 4
  4. 访问 2 的右节点 5。节点 5 也是有子结点，继续往下
  5. 访问 5 的左节点 7。节点 7 也是有子结点，继续往下
  6. 访问 7 的左节点，无
  7. 访问 7 的右节点 8。此时 根 1 的左侧子树都完毕
  8. 访问 1 的右节点 3。节点 3 也是有子结点，继续往下
  9. 访问 3 的左节点，无
  10. 访问 3 的右节点 6

结果为：

1、2、4、5、7、8、3、6

中序遍历【左-根-右】——容易错

先处理左子树，然后处理根结点，最后处理右子树，上图遍历过程：

  1. 看根 1 的左节点 2，由于 节点 2 也是有子结点，所以不取值 2，继续往下看
  2. 看节点 2 的左节点 4，节点 4 没有子结点，取该值 4
  3. 遍历顺序是 左→根→右，取节点 4 的父节点 2
  4. 看节点 2 的右节点 5，节点 5 也是有子结点，所以不取值 5，继续往下
  5. 看节点 5 的左节点 7，由于 节点 7 也是有子结点，所以不取值 7，继续往下看
  6. 看节点 7 的左节点 无/空，所以取节点 7
  7. 看节点 7 的右节点 8，节点 8 是叶子节点，取值 8
  8. 取节点 7 的父节点 5。此时 根节点 1 的左侧遍历结束
  9. 取根节点 1
  10. 看根节点 1 的右节点 3，节点 3 也是有子结点，所以不取值 3，继续往下
  11. 看节点 3 的左节点 无/空，所以取节点 3
  12. 看节点 3 的右节点 6，节点 6 是叶子节点，取值 6

结果为：

4、2、7、8、5、1、3、6

提示：中间是根节点

后序遍历【左-右-根】——容易错

先处理左子树，然后处理右子树根结点，最后处理，上图遍历过程：

  1. 看根 1 的左节点 2，由于 节点 2 也是有子结点，所以不取值 2，继续往下看
  2. 看节点 2 的左节点 4，节点 4 是叶子节点，取该值 4
  3. 遍历顺序是 左→右→根，看节点 4 的父节点 2 的右节点 5，节点 5 也是有子结点，所以不取值 5，继续往下
  4. 看节点 5 的左节点 7，由于 节点 7 也是有子结点，所以不取值 7，继续往下看
  5. 看节点 7 的左节点 无/空，不取值
  6. 看节点 7 的右节点 8，节点 8 是叶子节点，取值 8
  7. 节点 7 的左右子节点遍历完，取值 7
  8. 看节点 7 的父节点 5 的右节点 无/空，不取值
  9. 节点 5 的左右子节点遍历完，取值 5
  10. 节点 2 的左右子节点遍历完，取值 2。此时根节点 1的左子树遍历完毕
  11. 看根节点 1 的右节点 3，节点 3 也是有子结点，所以不取值 3，继续往下看
  12. 看节点 3 的左节点 无/空，不取值
  13. 看节点 3 的右节点 6，节点 6 是叶子节点，取值 6
  14. 节点 3 的左右子节点遍历完，取值 3。此时根节点 1的右子树遍历完毕
  15. 取根节点 1

结果为：

4、8、7、5、2、6、3、1

提示：最后一个是根节点

例子2

前序遍历：1 2 4 5 7 8 3 6

中序遍历：4 2 7 5 8 1 3 6

后序遍历：4 7 8 5 2 6 3 1

层次遍历：1 2 3 4 5 6 7 8

题

由前序序列为 ABHFDECG；中序序列为 HBEDFAGC 构造二叉树。

分析

技巧：

前序确定根结点，根结点：A
中序区分左右子树，左子树：HBEDF，右子树：GC

答案

题

某二叉树的中序、先序遍历序列分别为 {20，30，10，50，40} ,
{10，20，30，40，50}，则该二叉树的后序遍历序列为（）。

A、50, 40, 30, 20, 10
B、30,20,10, 50, 40
C、30, 20, 50, 40, 10
D、20,30,10,40,50

分析

通过先序遍历可知，根节点是 10，后续遍历序列最后一个元素是根节点 10，可排除 B、C

通过中序遍历可知：右子树的结点是 50、40，后续遍历序列倒数第二个元素是 50 或 40，可排除 A

答案

C

原文出处：/show_1GWvtZObrjE.html

吉ICP备15003043号