二叉树的遍历

二叉树定义

二叉树要么为空,要么由根节点(root),左子树(left subtree),右子数(right subtree)组成。

二叉树遍历类型有

  • 先序遍历:根节点 -> 左子树 -> 右子树
  • 中序遍历:左子树 -> 根节点 -> 右子树
  • 后序遍历:左子树 -> 右子树 -> 根节点
  • 层次遍历(广度优先遍历)

图示详解如下

1-binary-tree-traversal-diagram

  • 中序遍历

    中序遍历,只需要把树图排布好,在树下画一直线,之后把节点垂直移动到直线上,从左往右读取,便是中序遍历。例图中序遍历答案为:DBHEIAFCG。

  • 前序遍历和后序遍历

    在计算前序和后序遍历时,先从 A 节点左侧进树沿着树画节点画游历曲线,最后从 A 节点右侧出树,并标明进节点为1,出节点为2。

    • 前序遍历

      前序遍历,沿着游历曲线读取1标志的节点,便为前序遍历。例图前序遍历答案为:ABDEHICFG。

    • 后序遍历

      后序遍历,沿着游历曲线读取2标志的节点,便为后序遍历。例图后序遍历答案为:DHIEBFGCA。

  • 层次遍历(广度优先遍历)

    层次遍历,即按层遍历既可。例图层次遍历答案为:ABCDEFGHI。

遍历的性质

  • 已知前序遍历和中序遍历,可以唯一的确定一个二叉树
  • 已知后序遍历和中序遍历,可以唯一的确定一个二叉树

All content under CC BY-NC-ND 4.0