《大话数据结构》之二叉树的四种遍历

Bertha 。 2022-08-18 00:43 22阅读 0赞

二叉树的遍历共分四种：前序遍历、中序遍历、后序遍历、层序遍历。

除层序遍历以外，所谓的前序、中序、后序，是按父节点所处位置的不同来划分的。父节点在两个子节点的中间，那就是中序，在两个子节点的前面那就是前序。

此外二叉树对子节点的遍历都是先左后右的。（如果说，男左女右的话，那么可以认为这样有点重男轻女，这个思想在国外也是有的(\*^\_\_^\*) 嘻嘻……）

![Center][]

以上面这个二叉树为例。

前序遍历：

1、按前序遍历写下根节点和他的子节点

A B C

2、先左后右，看B和他的子节点，在第一步的基础上，写下按前序遍历，B和他的子节点的顺序，忽略A和C

A ( B D ) C

3、看B的左节点D，按前序遍历写下D和他子节点的顺序

A B ( D G H ) C

4、此刻A的左子树已经遍历完成，开始看右子树，同样，按父节点在前，先左后右的顺序写下C和他的子节点的序列

A B D G H ( C E F )

5、先左后右，先看C的右节点E,按父节点在前，先左后右的顺序写下E和他的子节点的序列

A B D G H C ( E I ) F

6、此时整个二叉树已经全部遍历完成，没有节点没有访问到，那么完整的序列就是

A B D G H C E I F

中序遍历：

思想和步骤与前序一样，只是父节点变成在中间访问。

1、按父节点在中间，先左后右的顺序遍历根节点和他的子节点

B A C

2、按父节点在中间，先左后右的顺序遍历根节点左节点B和他的子节点

(D B ) A C

3、按父节点在中间，先左后右的顺序遍历B的左节点D和他的子节点

(G D H ) B A C

4、根节点的左子树遍历完成，那就开始遍历右子树，C和他的子节点

G D H B A ( E C F)

5、按父节点在中间，先左后右的顺序遍历C的左节点E和他的子节点

G D H B A ( E I ) C F

6、至此所有节点遍历完成，最终中序遍历顺序为

G D H B A E I C F

后序遍历：

思想和步骤与前面是一样一样的，只是父节点变成在最后访问。

1、按父节点在后面，先左后右的顺序遍历根节点和他的子节点

B C A

2、按父节点在后面，先左后右的顺序遍历根节点左节点B和他的子节点

(D B ) C A

3、按父节点在后面，先左后右的顺序遍历B的左节点D和他的子节点

(G H D ) B C A

4、根节点的左子树遍历完成，那就开始遍历右子树，C和他的子节点

G H D B ( E F C ) A

5、按父节点在后面，先左后右的顺序遍历C的左节点E和他的子节点

G H D B ( I E ) F C A

6、至此所有节点遍历完成，最终后序遍历顺序为

G H D B I E F C A

层序遍历：

最简单的一种遍历方法。按层次，从左到右写，完全不需要考虑前后问题。

1、先遍历第一层

A

2、遍历第二层

A ( B C )

3、遍历第三层

A B C ( D E F )

4、遍历第四层

A B C D E F ( G H I )

5、所有层次遍历完成，最终层序遍历结果为

A B C D E F G H I

[Center]: /images/20220731/91bcc797694f4f7da3f8325b26a84d3b.png

发表评论取消回复

表情：

评论列表（有 0 条评论，22人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构实验四：二叉树的遍历

实验要求 1、建立二叉树； 2、递归和非递归的遍历算法，要求先序和后序采用递归遍历，中序采用非递归遍历； 3、实验报告格式及图表清晰； 4、如有雷同，均算抄袭，

清疚/ 2022年12月23日 15:29/ 0 赞/ 197 阅读

相关常用数据结构之二叉树及树的四种遍历方式

1.树我们选择一种数据结构，不仅要能存储数据，而且要能体现数据之间的关系。目前数据主要有是三种关系一对一、一对多、多对多；之前我们讨论了线性表(数组、链表、栈、队列),

悠悠/ 2022年12月11日 03:26/ 0 赞/ 14 阅读

相关数据结构之二叉树的遍历

二叉树的遍历分为前序遍历，中序遍历，后序遍历，层序遍历，在本文中，前三种由递归实现，层序遍历由队列实现。 include "stdio.h" includ

╰半橙微兮°/ 2022年08月21日 00:11/ 0 赞/ 178 阅读

相关《大话数据结构》之二叉树的四种遍历

二叉树的遍历共分四种：前序遍历、中序遍历、后序遍历、层序遍历。除层序遍历以外，所谓的前序、中序、后序，是按父节点所处位置的不同来划分的。父节点在两个子节点的中间，那就是中序

Bertha 。/ 2022年08月18日 00:43/ 0 赞/ 23 阅读

相关数据结构学习（四）二叉树的遍历

快速理解深度优先搜索深度优先搜索有三种： 1.前序遍历 2.中序遍历 3.后序遍历它们的区别是什么呢？这三种搜索类型其实是根据访

骑猪看日落/ 2022年08月10日 08:37/ 0 赞/ 165 阅读

相关数据结构之树和二叉树---二叉树的遍历

问题：分别用递归和非递归方式实现二叉树的先序遍历，中序遍历，后序遍历及层序遍历二叉树的基本操作见[数据结构之树和二叉树---二叉树的基本操作][---] //递归方式实现

Myth丶恋晨/ 2022年08月03日 12:55/ 0 赞/ 194 阅读

相关数据结构之遍历二叉树

遍历二叉树在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点。这就提出遍历二叉树的问题，即如何按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问

曾经终败给现在/ 2022年05月31日 12:27/ 0 赞/ 228 阅读

相关数据结构实验之二叉树二：遍历二叉树

Time Limit: 1000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Problem Descrip

水深无声/ 2022年05月14日 02:56/ 0 赞/ 258 阅读

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

二叉树遍历原理二叉树的遍历：是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。这里有两个关键词：访问和次序。访

Myth丶恋晨/ 2022年02月03日 06:57/ 0 赞/ 240 阅读

相关数据结构之二叉树遍历

二叉树遍历方式： ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubm

爱被打了一巴掌/ 2022年01月31日 19:47/ 0 赞/ 241 阅读