这两个术语区分了两种不同的走树方式。

仅仅展示差异可能是最简单的。考虑树：

    A
   / \
  B   C
 /   / \
D   E   F

深度 优先遍历将按此顺序访问节点

A, B, D, C, E, F

请注意，在继续前进之前，您要一直走 下一 条腿。

广度 优先遍历将按此顺序访问节点

A, B, C, D, E, F

在这里，我们在下降之前一直 在每个级别上工作。

（请注意，遍历顺序存在一些歧义，并且我作弊以维持树的每一级的“阅读”顺序。在任何一种情况下，我都可以在 C 之前或之后到达 B，同样我可以到达E 在 F
之前或之后。这可能重要也可能不重要，取决于您的应用程序…）

两种遍历都可以用伪代码实现：

Store the root node in Container
While (there are nodes in Container)
   N = Get the "next" node from Container
   Store all the children of N in Container
   Do some work on N

两种遍历顺序的区别在于 的选择Container。

• 对于 深度，首先 使用堆栈。（递归实现使用调用堆栈…）
• 对于 广度优先 使用队列。

递归实现看起来像

ProcessNode(Node)
   Work on the payload Node
   Foreach child of Node
      ProcessNode(child)
   /* Alternate time to work on the payload Node (see below) */

当您到达没有子节点的节点时，递归结束，因此保证对于有限的非循环图结束。

在这一点上，我还是有点作弊。稍微聪明一点，您还可以 按 以下顺序处理节点：

D, B, E, F, C, A

这是深度优先的一种变体，我不会在每个节点上进行工作，直到我走回树上。然而，我在向下寻找他们的孩子的路上 访问了更高的节点。

这种遍历在递归实现中是相当自然的（使用上面的“Alternate time”行而不是第一个“Work”行），如果使用显式堆栈也不会
太难，但我将把它留作练习。