数据结构二叉树BinaryTree之遍历

Posted by Naah on Thursday, Aug 17,2017 10:46:27

1.前序遍历

 

  规则为若二叉树为空,则返回空,否则按如下顺序进行访问

  1. 访问根节点
  2. 访问左节点
  3. 访问右节点

 

总结:中左右

  1. 顺序:中左右
  2. 规律:要访问的放中间
  3. 每次进入子树,要访问时先访问根,如果有左访问左,没有左访问右

 

该图前序遍历为:ABDGHCEIF


2.中序遍历

  规则为若二叉树为空,则返回空,否则按如下顺序进行访问

  1. 访问左节点
  2. 访问跟节点
  3. 访问右节点

 

总结:

  1. 顺序:左中右
  2. 规律:要访问的放中间
  3. 每次进入子树,要访问时先访问左节点,然后访问根节点,之后访问右节点

 

该图中序遍历为:GDHBAEICF

————————————————

 

3.后序遍历

  规则为若二叉树为空,则返回空,否则按如下顺序进行访问

  1. 访问左节点
  2. 访问右节点
  3. 访问中节点

 

总结:

1.顺序:左右中 2.规律:要访问的放中间 3.每次进入子树,要访问时先访问左节点,然后访问右节点,之后访问跟节点

  该图后序遍历为:GHDBIEFCA

————————————————

4.层序遍历  

横向遍历

按照层次进行遍历

该图后序遍历为:ABCDEFGHI

更新