数据结构——遍历二叉树

二叉树遍历原理

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

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

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

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

二叉树遍历方法

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

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

1、前序遍历

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

2、中序遍历

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

3、后序遍历

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

4、层序遍历

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

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

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

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

推导遍历结果

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

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

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

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

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

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

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

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

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

原文发布于微信公众号 - Android机动车(JsAndroidClub)

原文发表时间:2018-06-21

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏我的技术专栏

数据结构图文解析之:树的简介及二叉排序树C++模板实现.

13640
来自专栏Java爬坑系列

【Java入门提高篇】Day21 容器类详解(四)ArrayList源码分析

   今天要介绍的是List接口中最常用的实现类——ArrayList,本篇的源码分析基于JDK8,如果有不一致的地方,可先切换到JDK8后再进行操作。

22260
来自专栏从流域到海域

二叉树的性质和常用操作代码集合

二叉树的性质和常用操作代码集合 性质: 二叉树的性质和常用代码操作集合 性质1:在二叉树的第i层上至多有2^i-1个结点 性质2:...

23490
来自专栏开发与安全

数据结构:二叉树的遍历和存储结构

在《二叉树的定义和性质》中我们已经认识了二叉树这种数据结构。我们知道链表的每个节点可以有一个后继,而二叉树(Binary Tree)的每个节点可以有两个后继。比...

32490
来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

20420
来自专栏赵俊的Java专栏

从源码上分析 ArrayList

13810
来自专栏拭心的安卓进阶之路

Java 集合深入理解(7):ArrayList

今天心情有点美丽,学学 ArrayList 放松下吧! 什么是 ArrayList ? ? ArrayList 是 Java 集合框架中 List接口 的一个实...

23970
来自专栏王硕

原 B树C语言代码实现

748100
来自专栏数据结构与算法

codevs 1814 最长链

1814 最长链 时间限制: 1 s 空间限制: 256000 KB 题目等级 : 钻石 Diamond 题目描述 Description 现给出...

31450
来自专栏我是东东强

常见算法之二叉树遍历

所谓遍历二叉树,就是遵从某种次序,顺着某一条搜索路径访问二叉树中的各个结点,使得每个结点均被访问一次,而且仅被访问一次。本文详细介绍了二叉树的前序(又称先序)、...

17920

扫码关注云+社区

领取腾讯云代金券