深度优先-广度优先

一、深度优先遍历

  1. 深度优先遍历:也叫深度优先搜索,对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。
  2. 要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历,具体如下:
    • 先序遍历:对任一子树,先访问根,然后遍历其左子树,最后遍历其右子树。
    • 中序遍历:对任一子树,先遍历其左子树,然后访问根,最后遍历其右子树。
    • 后序遍历:对任一子树,先遍历其左子树,然后遍历其右子树,最后访问根。

二、广度优先遍历

  1. 广度优先遍历:又叫层次遍历,或广度优先搜索,从上往下对每一层依次访问,在每一层中,从左往右(也可以从右往左)访问结点,访问完一层就进入下一层,直到没有结点可以访问为止。