数据结构(10) 树[四]（二叉树遍历）

Myth丶恋晨 2022-02-03 06:57 215阅读 0赞

# 二叉树遍历原理 #

**二叉树的遍历：是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。**

# 这里有两个关键词：访问和次序。 #

访问其实是要根据实际的需要来确定具体做什么，比如对每个结点进行相关计算，输出打印等。它算作是一个抽象操作。

二叉树的遍历次序不同于线性结构，最多也就是从头到尾、循环和双向等简单的遍历方式。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择。

### 二叉树遍历方法 ###

二叉树的遍历方式可以有很多，如果我们限制从左到右的顺序，就主要分为四种：

1.  前序遍历
2.  中序遍历
3.  后序遍历
4.  层序遍历

1、前序遍历

若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如下图遍历顺序为：ABDGHCEIF。

![img][]

2、中序遍历

若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点左子树，然后访问根结点，最后中序遍历右子树，如下图遍历顺序为：GDHBAEICF。

![img][img 1]

3、后序遍历

若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点，如下图遍历顺序为：GHDBIEFCA。

![img][img 2]

4、层序遍历

若二叉树为空，则空操作返回，否则从树的第一层开始，也就是从根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问，如下图遍历顺序为：ABCDEFGHI。

![img][img 3]

程序代码：这里的代码是C写的，换算成java一样，只是写法不一样，逻辑一样。所以接下来的代码，请看逻辑

# 1、前序遍历算法 #

![img][img 4]

##  ##

## 实例：分析【前序遍历算法】代码执行逻辑： ##

![img][img 5]

![img][img 6]

![img][img 7]

![img][img 8]

![img][img 9]

![img][img 10]

![img][img 11]

![img][img 12]

![img][img 13]

# 2.中序遍历算法 #

![img][img 14]

## 实例：分析【中序遍历算法】代码执行逻辑： ##

![img][img 5]

![img][img 15]

![img][img 16]

![img][img 17]

![img][img 18]

![img][img 19]

![img][img 20]

![img][img 21]

![img][img 22]

![img][img 23]

# 后续遍历算法 #

![img][img 24]

## 实例：分析【后续遍历算法】代码执行逻辑： ##

![img][img 5]

![img][img 25]

![img][img 26]

我们提到的四种遍历方式，其实都是在把树种的结点编程某种意义上的线性序列，这样给程序执行带来了好处。

**层序遍历很好理解，就是逐层遍历，每层从左到右逐个遍历；前序、中序、后序遍历最根本的区别就是双亲结点的访问时机：前序是先访问双亲结点，然后左孩子，最后右孩子；中序是左孩子，双亲，右孩子；后序是左孩子、右孩子最后双亲结点。**

树的定义就使用了**递归**这一方式，当然，对树的遍历也是使用递归（注意递归算法一定要有结束递归的标志），关于二叉树遍历的算法，就不再详细描述了。

#  #

# 练习： 推导遍历结果 #

有一种题目是为了考察你对二叉树遍历的掌握程度，会这样出题：已知一棵二叉树的前序遍历顺序是ABCDEF，中序遍历顺序是CBAEDF，请问这棵树的后序遍历是什么？

对于这样的题目，如果真正了解各种遍历规则，其实是不难的。

三种遍历都是从根结点开始，前序遍历是先打印再递归左和右，所有前序遍历序列为ABCDEF，第一个字母A就是根结点；再由中序遍历序列CBAEDF，可以只带C和B是A的左子树上的结点，E、D、F是A的右子树上的结点，我们可以得到以下这样的图：

![img][img 27]

然后再看前序序列中的C和B，先B再C，所以B应该是A的左孩子，C就只能说B的孩子了，至于C是B的左还是右孩子，再看中序序列CBAEDF，C在B之前打印，说明C是B的左孩子，如图：

![img][img 28]

再看前序中的E、D、F，他们的顺序是ABCDEF，意味着D是A的右孩子，E和F是D的子孙（注意，他们中有一个不一定是孩子，还可能是孙子）。再看中序序列是CBAEDF，E在D的左侧，F在右侧，所以E是D的左孩子，F是D的右孩子，如图：

![img][img 29]

为了避免推导失误，我们最好自己再按此树推导一遍前序和中序遍历序列。根据二叉树结构图，轻松得到后序遍历为CBEFDA。

这里我们可以得到两个二叉树遍历的性质：

1.  已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树；
2.  已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树；

**注意：已知前序和后序遍历，是不能确定一棵二叉树的。**

[img]: /images/20220203/62db23a0c6be44bbb22b61e281a3e2a1.png
[img 1]: /images/20220203/0a3a8ad1bfe24466a6f8478ca9cfd2dd.png
[img 2]: /images/20220203/590813528b8048eb961ef186a546eec6.png
[img 3]: /images/20220203/9f861a24577e415f985482a36acb0fb7.png
[img 4]: /images/20220203/a98193e17687489db219e78885d6710a.png
[img 5]: /images/20220203/e74624e7231c4220a162b748fae6ad47.png
[img 6]: /images/20220203/467e011d10bd4b26b457b625cc11c594.png
[img 7]: /images/20220203/28e4437050bd42a7a29bae1f4a818d6a.png
[img 8]: /images/20220203/a9e029b7bf1a4ddeb078382b1713eab5.png
[img 9]: /images/20220203/4c2d3cbb01944726a087a463b618acfd.png
[img 10]: /images/20220203/447e4219a1c841db8794c4be05c9256b.png
[img 11]: /images/20220203/405f0fcb39a94f23a2e12b4138fdfbca.png
[img 12]: /images/20220203/f2f51df45edc482bbf24316aa98fc4c3.png
[img 13]: /images/20220203/34ae38f1a2604b83baa3f4d033a41904.png
[img 14]: /images/20220203/dd4a8760f9124db2a5ae44de78e3ce79.png
[img 15]: /images/20220203/55f3c8e353c647d39bb4da9394ec7122.png
[img 16]: /images/20220203/d940d983b6f34d10bea2f25b00ed86e3.png
[img 17]: /images/20220203/7d273e6f68aa4f468a29a9e7e43b9e77.png
[img 18]: /images/20220203/04e421da6f1e4e219a2a12be8f5e6b83.png
[img 19]: /images/20220203/2254e996c9b94c799b1a3b6e375e372d.png
[img 20]: /images/20220203/548fb3317f8a42eba7e3ea3ea2a375ce.png
[img 21]: /images/20220203/ebd8909f350245149f9b9a78e68ba0b5.png
[img 22]: /images/20220203/e0f6e99da0fb4f799c94b6bc9b8427df.png
[img 23]: /images/20220203/b9bf465fc0194c8c9909eadca95f96f8.png
[img 24]: /images/20220203/03e85f9819674462af34f0659899dd2d.png
[img 25]: /images/20220203/af0166a00c3a48e3aa87d51f9a5a67ca.png
[img 26]: /images/20220203/efd65eba8c6e4ffda1efeaa3780fa2d2.png
[img 27]: /images/20220203/ceac61a1bc3b43689411c36736766358.png
[img 28]: /images/20220203/0712acc63bc14a10a7bc23039df5e3e1.png
[img 29]: /images/20220203/216f02c096aa4c32b7a593f5ea031cd6.png