【二叉树三种遍历顺序】

水深无声 2022-12-04 02:24 333阅读 0赞

1、中序遍历

指对树中任意节点的访问是在遍历完其左子树后进行的，访问此节点后，再对其右子树遍历（左根右）。遍历从根节点开始，遇到每个节点时，其遍历过程为：

  • 中序遍历其左子树；
  • 访问根节点；
  • 中序遍历其右子树。

举例：

在这里插入图片描述

该树遍历结果：DBHEAFICG

2、先序遍历

他是指对节点的访问在其左、右子树遍历之前进行的（根左右）。遍历是从根节点开始，遇到每个节点时，其遍历过程为：

  • 访问根节点；
  • 先序遍历其左子树；
  • 先序遍历其右子树

举例：

在这里插入图片描述

该树遍历结果：ABDEHCFIG

3、后序遍历

它是指左右子树的遍历先进行，然后才是对此节点的访问（左右根）。后续遍历则是从根节点开始，遇到每个结点时，其遍历过程为：

  • 后序遍历其左子树
  • 后序遍历其右子树
  • 访问根节点

" class="reference-link">举例：在这里插入图片描述

该树遍历结果：DHEBIFGCA

面试题

还有一个命题：给定了二叉树的任何一种遍历序列，都无法唯一确定相应的二叉树。但是如果知道了二叉树的中序遍历序列和任意的另一种遍历序列，就可以唯一地确定二叉树

例子1：已知二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是（？）。

中序遍历：DEBAC

后序遍历：DABEC

后序遍历序列的最后一个结点是根结点，所以可知c为根结点。

中序遍历序列的根结点在中间，其左边是左子树，右边是右子树。所以从中序遍历序列中可看出，根结点C只有左子树，没有右子树。
在这里插入图片描述

(2)中序遍历：DEBA

后序遍历：DABE

后序遍历序列的最后一个结点是根结点，所以可知e为c的左子树的根结点。

中序遍历序列的根结点在中间，其左边是左子树，右边是右子树。所以从中序遍历序列中可看出，根结点E的左子结点是D，右子树是BA。

在这里插入图片描述

(3)中序遍历：BA

后序遍历：AB

由后序遍历序列可知B为E的右子树的根结点。由中序遍历序列中可看出，A为根结点B的右子结点。
在这里插入图片描述

树的结构如下：
在这里插入图片描述

该二叉树的前序遍历序列是（CEDBA）

例子2：已知二叉树的前序遍历序列是ABDGCEFH,中序遍历序列是DGBAECHF,它的前序遍历序列是（？）。

(1)先序遍历：ABDGCEFH

中序遍历：DGBAECHF

先序遍历序列的第一个结点是根结点，所以可知a为根结点。

中序遍历序列的根结点在中间，其左边是左子树，右边是右子树。所以从中序遍历序列中可看出，根结点A的左子树是DGB，右子树是ECHF。

在这里插入图片描述

a的左子树：

(2)先序遍历：BDG

中序遍历：DGB

先序遍历序列的第一个结点是根结点，所以可知b为a的左子树的根结点。

中序遍历序列的根结点在中间，其左边是左子树，右边是右子树。所以从中序遍历序列中可看出，根结点B的左子树是DG，没有右子树。

在这里插入图片描述

B的左子树：

(3)先序遍历：DG

中序遍历：DG

由先序遍历序列可知D为B的左子树的根结点。

中序遍历序列的根结点在中间，其左边是左子树，右边是右子树。所以从中序遍历序列中可看出，根结点D的右子结点是G。

在这里插入图片描述

A的右子树：

(4)先序遍历：CEFH

中序遍历：ECHF

由先序遍历序列可知C为A的右子树的根结点。

从中序遍历序列中可看出，根结点C的左子结点是E，右子树是HF。

在这里插入图片描述

C的右子树：

(5)先序遍历：FH

中序遍历：HF

由先序遍历序列可知F为C的右子树的根结点。

从中序遍历序列中可看出，根结点F的左子结点是H，没有右子树。

在这里插入图片描述

树的结构如下：
在这里插入图片描述

它的前序遍历序列是（GDBEHFCA）

发表评论

表情：
评论列表 （有 0 条评论，333人围观）

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

相关阅读

    相关 【二叉树三种遍历顺序】

    1、中序遍历 指对树中任意节点的访问是在遍历完其左子树后进行的，访问此节点后，再对其右子树遍历（左根右）。遍历从根节点开始，遇到每个节点时，其遍历过程为： 中序遍

    水深无声水深无声/ 0 赞/ 334 阅读

    相关 二叉树的三种遍历

    二叉树的遍历分为以下三种： 先序遍历：遍历顺序规则为【根左右】 中序遍历：遍历顺序规则为【左根右】 后序遍历：遍历顺序规则为【左右根】 什么是【根左右】？就是先遍历根，

    野性酷女野性酷女/ 0 赞/ 255 阅读

    相关 二叉树的三种遍历问题

    1、先序遍历：【根左右】 ![70][] 所谓【根左右】是指先遍历根节点，然后左孩子节点，最后右孩子节点。 所以，上图的遍历顺序是：ABCDEF 2、中序遍历：【

    r囧r小猫r囧r小猫/ 0 赞/ 307 阅读

    相关 二叉树的三种遍历口诀

    二叉树的三种遍历口诀 最近在准备笔试面试题，复习复习数据结构相关知识，在二叉树这边好多都忘了，所以特地写下来，防止以后忘了可以迅速查找 1.前序遍历：根节点—-左子树—

    痛定思痛。痛定思痛。/ 0 赞/ 365 阅读