【数据结构】—树：中序遍历

• 算法结构

【数据结构】树—中序遍历

文章目录

  • 【数据结构】树—中序遍历
  • 一、什么是中序遍历？
  • 二、中序遍历详解
  • 总结

一、什么是中序遍历？

中序遍历，是数据结构中树的遍历方式之一。

特点：左、根、右。

每次遍历时，先遍历左节点的数据，之后遍历本节点，最后遍历右节点，循环往复，直至树中数据遍历完成。

二、中序遍历详解

这是一棵二叉查找树。

以该树为例，如何进行中序遍历？请看我一步步的画图演示。

左根右，指的是遍历的顺序，先遍历左节点，再遍历根节点，最后遍历右节点。

以下图为例，我们进行中序遍历：

10是根节点，先查10的左节点，查到了5节点。

中序遍历1

将5当作暂时的根节点，先查5的左节点，查到了3节点。

中序遍历2

将3当作暂时的根节点，先查3的左节点，3没有左节点，于是返回至3节点，输出3。

中序遍历3

3的左节点、3本身都已经遍历完成，接下来查3的右节点，查到了4节点

中序遍历4

将4当作暂时的根节点，先查4的左节点，4没有左节点，于是返回至4节点，输出4。

中序遍历5

4的左节点、4本身都已经遍历完成，接下来查4的右节点，4没有右节点，于是返回至4节点。

中序遍历6

此时4的左节点、4本身、4的右节点都已经遍历完成，返回其上一级节点：3节点。

中序遍历7

此时3的左节点、3本身、3的右节点都已经遍历完成，返回其上一级节点：5节点。

中序遍历8

此时5的左节点已经遍历完成，输出5。

中序遍历9

5的左节点、5本身都已经遍历完成，接下来查5的右节点，查到了9节点。

中序遍历10

将9当作暂时的根节点，先查9的左节点，9没有左节点，于是返回至9节点，输出9。

中序遍历11

9的左节点、9本身都已经遍历完成，接下来查9的右节点，9没有右节点，于是返回至9节点。

中序遍历12

此时9的左节点、9本身、9的右节点都已经遍历完成，返回其上一级节点：5节点。

中序遍历13

此时5的左节点、5本身、5的右节点都已经遍历完成，返回其上一级节点：10节点。

中序遍历14

此时10的左节点已经遍历完成，输出10。

中序遍历15

10的左节点、10本身都已经遍历完成，接下来查10的右节点，查到了18节点

中序遍历16

将18当作暂时的根节点，先查18的左节点，18没有左节点，于是返回至18节点，输出18。

中序遍历17

18的左节点、18本身都已经遍历完成，接下来查18的右节点，查到了21节点。

中序遍历18

将21当作暂时的根节点，先查21的左节点，查到了19节点。

中序遍历19

将19当作暂时的根节点，先查19的左节点，19没有左节点，于是返回至19节点，输出19。

中序遍历20

19的左节点、19本身都已经遍历完成，接下来查19的右节点，19没有右节点，于是返回至19节点。

中序遍历21

此时19的左节点、19本身、19的右节点都已经遍历完成，返回其上一级节点：21节点。

中序遍历22

此时21的左节点已经遍历完成，输出21。

中序遍历23

21的左节点、21本身都已经遍历完成，接下来查21的右节点，查到了59节点。

中序遍历24

将59当作暂时的根节点，先查59的左节点，查到了33节点。

中序遍历25

将33当作暂时的根节点，先查33的左节点，33没有左节点，于是返回至33节点，输出33。

中序遍历26

33的左节点、33本身都已经遍历完成，接下来查33的右节点，33没有右节点，于是返回至33节点。

中序遍历27

此时33的左节点、33本身、33的右节点都已经遍历完成，返回其上一级节点：59节点。

中序遍历28

此时59的左节点已经遍历完成，输出59。

中序遍历29

59的左节点、59本身都已经遍历完成，接下来查59的右节点，59没有右节点，于是返回至59节点。

中序遍历30

此时59的左节点、59本身、59的右节点都已经遍历完成，返回其上一级节点：21节点。

中序遍历31

此时21的左节点、21本身、21的右节点都已经遍历完成，返回其上一级节点：18节点。

中序遍历32

此时18的左节点、18本身、18的右节点都已经遍历完成，返回其上一级节点：10节点。

中序遍历33

此时根节点10的左节点、根节点本身、根节点的右节点都已经遍历完成，这棵树的中序遍历完成。

遍历结果：

[3，4，5，9，10，18，19，21，33，59]

我们可以发现，二叉查找树经过中序遍历后，会变得有序，当然，这个顺序是依靠二叉查找树的排序规则来进行的。如果排序规则是左边大，右边小，那么经过中序遍历后的序列会是倒序的。

总结

二叉查找树进行中序遍历后，返回的序列是排好序的。

数据结构方面的内容刚刚接触，讲解不够深刻，还望谅解。

本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://www.net2asp.com/a591537761.html

赞 (0)
« 上一篇 1天前
下一篇 » 1天前

相关推荐