二叉树深度优先遍历（DFS）和广度优先遍历（BFS）

定义

二叉树每个节点最多有两个子树结构，分别是“左子树”（left subtree）和“右子树”(right subtree)。

遍历

广度优先遍历（BFS）

广度优先搜索(Breadth First Search)，又称层次遍历。从树的根节点(root)开始，然后按照从上到下，从左到右的顺序依次遍历每一层的子节点直到遍历整个树的节点。

深度优先遍历（DFS）

对于一颗二叉树，深度优先遍历(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。树的深度优先遍历主要分为：前序遍历、中序遍历以及后序遍历

• 前序遍历：若二叉树为空则结束，否则依次先访问根节点，然后访问左子树，最后访问右子树。
• 中序遍历：若二叉树为空则结束，否则先访问根节点的左子树，然后访问根节点，最后访问右子数。
• 后序遍历：若二叉树为空则结束，否则先访问根节点的左子树，然后访问右子数，最后访问根节点。

深度优先一般采用递归的方式实现，递归的深度为树的高度。

示例

        0               # 层级遍历：0,1,2,3,4,5,6,7,8,9
     /    \             # 前序遍历：0,1,3,7,8,4,9,2,5,6
    1      2            # 中序遍历：7,3,8,1,9,4,0,5,2,6
   / \    / \           # 后序遍历：7,8,3,9,4,1,5,6,2,0
  3   4  5   6
 / \  /
7   8 9

实现

• DFS

  使用数据结构栈，（stack）

• BFS

  使用数据结构链表

参考链接

• 简述树的深度优先算法、广度优先算法，及非递归实现的特点。
• Python 广度优先/深度优先遍历二叉树
• python 实现二叉树的广度优先遍历和深度优先遍历