数据结构与算法——第6章-树-二叉树的4种遍历(6.5.1)

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

一 概述

1
2
1.层次遍历
2.普通遍历

二 遍历二叉树的算法

1
2
3
遍历二叉树可以算作是对树存储结构做的最多的操作，既是重点，也是难点。
本节将从初学者的角度给大家分析一下 4 种遍历二叉树算法的由来。
图 1 是一棵二叉树，对于初学者而言，遍历这棵二叉树无非有以下两种方式。

三 层次遍历

1
2
3
前面讲过，树是有层次的，拿图 1 来说，该二叉树的层次为 3。
通过对树中各层的节点从左到右依次遍历，即可实现对正棵二叉树的遍历，此种方式称为层次遍历。
比如，对图 1 中二叉树进行层次遍历，遍历过程如图 2 所示：

四 普通遍历

1
2
3
4
其实，还有一种更普通的遍历二叉树的思想，即按照 "从上到下，从左到右" 的顺序遍历整棵二叉树。
还拿图 1 中的二叉树举例，其遍历过程如图 3 所示：
以上仅是从初学者的角度，对遍历二叉树的过程进行了分析。接下来我们从程序员的角度再对以上两种遍历方式进行剖析
这里，我们要建立一个共识，即成功遍历二叉树的标志是能够成功访问到二叉树中所有的节点。

六 参考

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