数据结构与算法——第6章-树-二叉树遍历算法再剖析(6.5.2)

发表于 分类于 ， ， 阅读时长 ≈ 1 分钟

一 概述

1
2
3
1.二叉树遍历图示
2.3种遍历二叉树的算法
3.3种遍历二叉树的示例

二 二叉树遍历图示

2.1 二叉树访问次序

1
2
3
4
首先观察图 2 中的层次遍历，整个遍历过程只经过各个节点一次，
因此在层次遍历过程，每经过一个节点，都必须立刻访问该节点，否则错失良机，后续无法再对其访问。
若对图 1 中二叉树进行层次遍历，则访问树中节点的次序为：
1 2 3 4 5 6 7

2.2 二叉树遍历图示

1
2
3
而普通遍历方式则不同，通过观察图 3 可以看到，整个遍历二叉树的过程中，
每个节点都被经过了 3 次（虽然叶子节点看似只经过了 2 次，但实际上可以看做是 3 次）。
以图 3 中的节点 2 为例，如图 4 所示，它被经过了 3 次。

2.3 说明

1
2
3
因此，在编程实现时，我们可以设定真正访问各个节点的时机，
换句话说，我们既可以在第一次经过各节点时就执行访问程序，
也可以在第二次经过各节点时访问，甚至可以在最后一次经过各节点时访问。

三 3种遍历二叉树的算法

1
2
3
4
这也就引出了以下 3 种遍历二叉树的算法：
1. 先序遍历：每遇到一个节点，先访问，然后再遍历其左右子树（对应图 4 中的 ①）；
2. 中序遍历：第一次经过时不访问，等遍历完左子树之后再访问，然后遍历右子树（对应图 4 中的 ②）；
3. 后序遍历：第一次和第二次经过时都不访问，等遍历完该节点的左右子树之后，最后访问该节点（对应图 4 中的 ③）；

四 3种遍历二叉树的示例

1
2
3
4
5
6
7
8
9
10
以图 1 中的二叉树为例，

其先序遍历算法访问节点的先后次序为：
1 2 4 5 3 6 7
中序遍历算法访问节点的次序为：
4 2 5 1 6 3 7
后序遍历访问节点的次序为：
4 5 2 6 7 3 1

以上就是二叉树 4 种遍历算法的由来，其各个算法的具体实现过程其代码实现后续章节会详解介绍。

六 参考

  • C语言中文网—由浅入深讲二叉树4种遍历算法的由来