详细图解二叉树四种遍历(前序中序后序层次遍历)

• 算法结构

文章目录

  • 一.前序遍历
    • 常规操作
    • 简单方法
  • 二.中序遍历
    • 常规操作
    • 简单方法
  • 三.后序遍历
    • 常规操作
  • 四.层次遍历
    • 常规操作

本文中以此二叉树为例

在这里插入图片描述

一.前序遍历

常规操作

先根，再左，再右

在这里插入图片描述

确定了遍历整体结构：

在这里插入图片描述

在这里插入图片描述

确定了左子树中的整体结构

在这里插入图片描述

继续操作：

在这里插入图片描述

到此左子树中的遍历已经完成

在这里插入图片描述

在这里插入图片描述

确定右子树中的整体结构

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

前序结束

结果为：A B D F E C G I J H K

在这里插入图片描述

简单方法

从根结点出发向左开始绕二叉树一圈，经过的节点顺序即为先序遍历顺序

在这里插入图片描述

结果为：A B D F E C G I J H K

二.中序遍历

常规操作

先左，再根，再右

在这里插入图片描述

由此可确定根A在中间，下面分别确定左右子树中的顺序

在这里插入图片描述

左子树中：

在这里插入图片描述

由此确定了左子树中的顺序

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

右子树中：

对右子树进行整体划分

在这里插入图片描述

由此可以确定：

在这里插入图片描述

继续：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

中序遍历结束

结果为：F D B E A I G J C H K

简单方法

以该二叉树为例

在这里插入图片描述

结果为：F D B E A I G J C H K

三.后序遍历

常规操作

先左，再右，再根

在这里插入图片描述

将整体结构化分出来，后序遍历时根节点永远在最后一位

在这里插入图片描述

在这里插入图片描述

继续对左子树的结构进行划分

在这里插入图片描述

在这里插入图片描述

自此，左子树中遍历结束

在这里插入图片描述

在这里插入图片描述

划分右子树结构

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

后序遍历结束

结果为：F D E B I J G K H C A

四.层次遍历

常规操作

将二叉树每一行作为一个整体，从上到下输出，每行按照从左到右的顺序输出

在这里插入图片描述

第一行：A

第二行：B C

第三行：D E G H

第四行：F I J K

结果为：A B C D E G H F I J K

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

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

相关推荐