手把手教 二叉树的遍历

二叉树的遍历

二叉树的三种遍历方式：先序遍历、中序遍历、后序遍历

先序：
    始终执行以下步骤，
    1、访问根节点
    2、遍历左子树
    3、遍历右子树
中序：
    始终执行以下步骤，
    1、遍历左子树
    2、访问根节点
    3、遍历右子树
后序：
    始终执行以下步骤，
    1、遍历左子树
    2、遍历右子树
    3、访问根节点

“始终”：为什么要说“始终”执行呢？因为二叉树的每一个子树又可以看成是一个新的二叉树，遍历步骤、方式都保持一样，所以应该“始终”执行同样的操作，我们也应该始终把它看成一棵新的二叉树。(还是用图来讲吧)

              图

先序：
   1、访问根节点，所以先序的第一个元素为A
   2、遍历左子树：
         (我们应该把左子树看成一棵新的二叉树，“始终”执行)
          1、访问根节点，所以第二个元素为B
          2、遍历左子树：
               (我们应该把左子树看成一棵新的二叉树，“始终”执行)
               1、访问根节点，所以第三个元素为D
               2、遍历左子树：(D没有左子树，则遍历右子树)
               3、遍历右子树：只有一个元素，所以第四个元素为G
          3、遍历右子树：(B没有右子树)
   3、遍历右子树：
          (我们应该把右子树看成一棵新的二叉树，“始终”执行)
          1、访问根节点：所以第五个元素为C
          2、访问左子树：只有一个元素，所以第六个元素为E
          3、访问右子树：只有一个元素，所以第七个元素为F
   三个步骤执行完了，先序遍历为：ABDGCEF

中序
   1、遍历左子树：
         (我们应该把左子树看成一棵新的二叉树，“始终”执行)
         1、遍历左子树：
               (我们应该把左子树看成一棵新的二叉树，“始终”执行)
               1、遍历左子树：(D没有左子树，所以下一步)
               2、访问根节点，所以第一个元素为D
               3、遍历右子树：只有一个元素，所以第二个元素为G
         2、访问根节点：所以第三个元素为B
         3、遍历右子树：(B没有右子树)
    2、访问根节点：所以第四个元素为A
    3、遍历右子树：
          (我们应该把右子树看成一棵新的二叉树，“始终”执行)
          1、遍历左子树：只有一个元素，所以第五个元素为E
          2、访问根节点：所以第六个元素为C
          3、遍历右节点：只有一个元素，所以第七个元素为F
    三个步骤执行完了，中序遍历为：DGBAECF

后序
    后序遍历就给大家练习吧~



一些技巧：
    1、先序遍历第一个元素一定是根节点
    2、中序遍历中，任何一个元素的前一个元素一定在二叉树中它的左边，比如D在G前面，则D在G左边
    3、后序遍历最后一个元素一定是根节点
    4、先、中、后意思是说访问根节点的先后顺序，而且始终从左往右，从上往下...
    5、等你来更新...
  (还有什么技巧不要吝啬哦，记得评论里讲一下我更新...)


总结
   上面那些步骤看起来复杂，其实熟练了过后在头脑里就可以完成了，主要就是要记住最开始给的执行步骤