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

文章目录

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

          本文中以此二叉树为例

          

          一.前序遍历

          常规操作

          先根，再左，再右

          

          确定了遍历整体结构：

          

          

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

          

          

          （图片来源网络，侵删）

          继续操作：

          

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

          

          

          确定右子树中的整体结构

          

          

          

          

          前序结束

          结果为：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