一旦你对不同的数据结构有了足够的了解，你就会开始想：那么多的数据结构......重点又是什么呢？为什么我们首先要有所有这些结构？

当你深入到单一结构中时，就会有“只见树木，不见森林”的感觉。现在是时候让我们放宽我们的视野了，因为我们现在终于可以--终于！--开始进入超级有趣的东西了。我所说的超级有趣是指--算法!

在这个系列的开始，我想更多地了解我一直听说过的所有这些算法（偶尔会发现自己在技术面试前的半夜里上网搜索，疯狂地试图通过记住互联网告诉我应该知道的术语来准备）。但是，事实证明，在你能够进入算法之前，你必须知道数据结构！现在我们已经知道了。而现在我们知道了。我们谈到了以下几个方面的区别[[链表]],数据结构，以及何时一种结构会比另一种结构更合适。我们深入研究了以下几个方面的区别 [[图]] and [[树]], 以及它们在互联网上和我们的机器中存在的所有隐蔽地方。

现在，时机成熟了：利用我们的数据结构，以了解它们到底有什么用。没有比这个方法学习算法更好的开始了，算法在很长一段时间内都是让我感到困惑的根源：深度优先搜索。

树形遍历

在我们真正进入深度优先搜索的复杂性之前，我们需要先回答一个重要的问题：遍历一棵树到底是什么意思？我们对[[图]]有一点了解，但对树呢？

我怎样才能遍历一棵二叉树？

好吧，如果你的记忆力比我好，你会记得树实际上只是图的有限版本--也就是说，树是有一套更严格的规则可循的图。我们已经知道，有许多不同的方式来穿越一个图：我们可以从一个节点开始，然后在另一个节点结束，或者我们可以在同一个地方开始和结束。我们可以找到一条简单的路径，让我们从不重复同一个节点或边两次，或者我们可以找到一条允许我们重复节点和边的路径。

然而，尽管它们有相似之处，但树和图肯定是不同的。对我们来说，重要的是了解当我们谈论穿越树时，我们究竟在谈论什么。因此，让我们看看我们在这里处理的是什么。

由于树是图的一种类型，从逻辑上讲，树的遍历是图的一种类型。树的遍历有时也被称为树搜索。然而，树的遍历过程与更广泛的图的遍历过程有些不同。当我们搜索一棵树时，我们通常是为了达到以下目的：检查树结构中的所有节点，或者更新结构中的所有节点。不管是这两种情况中的哪一种，有一件重要的事情需要注意：我们不会多次搜索树中的节点。如果我们试图检查或更新树中的每一个节点，我们就不会想通过多次访问一个节点来重复自己的工作

因此，当我们穿越一棵树时，我们真正要做的是穿过这棵树而不重复自己。

实际穿越一棵树是什么意思？

但重要的不仅仅是每个节点只访问一次--顺序也很重要! 事实证明，当涉及到树时，当涉及到遍历和只访问树上的每个节点时，我们实际上只有两种主要技术可以依靠。最终，我们有两个选择：我们可以走得很远，或者我们可以走得很深。

遍历二叉树的两种方法。

描述这两种方法的比较常见的术语是广度优先搜索和深度优先搜索，它们可能正是你所期望的那样。

在 "广度优先搜索（BFS）"中，我们通过广撒网来搜索树中的所有节点，可以这么说。这意味着我们将从一级到下一级的节点中进行搜索，并在继续访问孙子节点之前遍历一个节点的所有子节点（在访问曾孙节点之前我们将访问孙子节点......你懂的！）。

但我们现在还不会谈论广度优先搜索。相反，让我们来看看这两个选项中的第二个。深度优先搜索（DFS）_。

在深度优先搜索中，一旦我们开始沿着一条路径前进，我们就不会停止，直到我们到达终点。换句话说，我们穿过树的一个分支，直到我们到达一片叶子，然后我们再回到树的主干上。

在上图中，我们可以看到，我们不是逐层穿越，而是通过访问所有的子代、孙代、曾孙代（等等）来穿越这棵树，直到我们走到一条路径的尽头。然后--也只有在那时--我们才会回到上层，开始新的道路。我们走过这条路，先访问所有红色的节点，然后继续访问橙色的节点。

这棵树太深了，我差点淹死了

当然，在计算机科学的世界里没有什么是那么简单的。尽管我们已经把树的遍历选项分成了两个可能的轨道--BFS和DFS，但事实证明，我们可以更深入地进行深度优先搜索 。

一旦我们把树形遍历的方法缩小到使用深度优先搜索，我们仍然只走了一半。即使在DFS的领域里，我们也有一些不同的选择，即在我们的树状搜索中要实施哪种深度优先策略！我们有几种不同的方法，可以让我们的树状搜索变得更容易。

我们可以用几种不同的方式来搜索树的子代、孙代和曾孙代节点。实际上，这一切都归结于我们决定做事情的顺序。

你可能还记得，除了包含一些数据之外，[[二叉树搜索]]只能有两个引用：对其左边的节点的引用（其数据会比较小），以及对其右边的节点的引用（其数据会比较大）。我们已经知道，每当我们搜索一棵树的时候，我们都在试图检查或更新结构中的所有节点。

在这两种情况下，我们需要做三件事。

1. 读取我们要检查或更新的节点的**数据。

2. 检查我们当前所在的节点（左侧引用）的**左侧的节点。

3. 检查我们目前所在的节点（左参考）的右侧的节点。

不同的深度优先策略都是围绕着我们做这三件事的顺序展开的。

深度优先的搜索策略

由于我们每次访问/检查一个节点都要做三件事，所以我们做这些事的顺序有六种可能的排列组合，我在左边的图片中画了出来。

然而，在这六种排列组合中，前三种是最流行的，也是最常见的。事实上，它们是如此的普遍，以至于它们有特殊的名字!

这些常见的DFS策略中的第一个是这样的：a) 读取我们所在节点的数据， b) 访问被引用到左边的节点，如果它存在， c) 访问被引用到右边的节点，如果它存在。读取数据，然后访问左边节点，再访问右边节点的过程通常被写成DLR，其中D代表数据，L代表左边节点，R代表右边节点。

我们使用这种速记方法是为了描述我们要做检查的顺序。所以，我告诉你这三个策略有特殊的名字，对吗？我想我也许应该告诉你它们是什么。

1. 预排序（DLR）。读取节点的数据，然后访问左边的子树/节点，接着是右边的子树/节点。

2. 顺序(LDR)。访问左边的子树/节点，然后读取节点的数据，最后访问右边的子树/节点。

3. 后序（LRD）。访问左边的子树/节点，然后访问右边的子树/节点，最后读取该节点的数据。

好的。所有这些定义可能看起来是一个非常多的信息，要一下子接受。我想通过画图会容易得多--而且希望能更清楚一些！我们来仔细看看。让我们用一棵树的例子来仔细看看前序、内序和后序的遍历是什么样子。

在下面的图片中，我们在一棵总共有12个节点的二叉树上尝试了这三种技术。如果我们在访问每个节点时打印出每个节点的名称，这就是这些遍历的样子。

前序、内序和后序遍历技术。编辑：请注意，这里的INORDER遍历。应该是这样的。"a, b, c, d, e, f, h, i, j, g, k, l"。因为你需要先遍历左面的子树，我们应该在g之前打印/检查节点h，然后检查其子树的左面子树，或者节点i，只有在检查完左面的节点/子树之后，我们才能检查节点j，然后再向上检查节点g、k和l，很抱歉这里的错误!

有趣的是! 如果我们看看这三种遍历是如何工作的，我们会很快注意到，整个 "DLR "的简称实际上具有重要的意义。

例如，在 preorder traversal 中，我们首先读取节点的数据，然后转到左边的子树，再到右边的子树。因此，我们访问的节点（以及我们打印出它们的数据）都遵循这个模式：首先我们打印出根节点的数据，然后是左子树的数据，再是右子树的数据。

然而，在inorder traversal中，我们是沿着路径一直走到最左边的叶子，然后再回到根节点，再沿着路径走到最右边的叶子。顺序遍历特别酷，因为我们最后得到的是一个排序的节点列表!

最后，在postorder traversal中，我们首先访问左边的节点引用，然后是右边的节点，如果没有的话，我们就读取我们当前所在的节点的数据。这就是为什么我们在读取节点a的数据之前，先读取节点c的数据，然后再读取节点b的数据。我们最终在遍历的最后阶段读取根节点（在访问了左子树和右子树的所有节点之后），这与后序遍历的简写相符。LRD。

用递归的方式进行深入研究!

好的，所以我们有三种不同的方法来实现深度优先搜索。

这很帅吧，我想。

但是......我们实际上是如何去实现这些策略的呢？为什么呢，当然是通过使用递归来实现了

如果你是递归的新手，我强烈建议你阅读递归)如果你只是需要快速复习一下的话。递归是在同一个方法中调用一个方法的过程--有效地重复了一个动作。

你可能已经看到了深度优先策略是如何被实现为一个递归方法的。如果你想一想，它开始变得越来越清晰：我们在做同样的事情--读取数据、检查左节点的引用、检查右节点的引用--一次又一次，直到我们完成树中所有的节点。当然，有时我们以稍微不同的顺序做这三个动作，这取决于我们选择的策略--但我们仍然在以同样的顺序对我们访问的每个节点做同样的三件事。

我们可以通过首先考虑这些节点在我们的代码中可能是什么样子来实现这个递归。这里有一个二进制搜索树的节点的小横截面，以帮助你直观地了解。

二进制搜索树节点的横截面图

每个节点都有三个部分--数据、左参考和右参考。一开始，我们就可以很清楚地看到一件事：我们将不得不为树上的每一个节点重复 "读取 "节点的这三个部分的动作。

因此，我们使用DFS遍历一棵树所需的时间与树中的节点数成正比。在二叉树上使用广度优先搜索的时间复杂度是O(n)，其中n是树上的节点数。

如果我们有5个节点，就会花费O(5)，如果我们有50个节点要访问，就会花费O(50)的时间。

好吧，那么我们如何在代码中实现这些节点的 "横截面 "之一？嗯，它可能会像一个对象一样简单，看起来像这样。

node1 = {
data: 1,
left: referenceToLeftNode,
right: referenceToRightNode
};

这还不算太糟! 我们要不要再往前走一步？让我们为预排序遍历搜索策略写出一个函数。我将用JavaScript进行伪编码，但希望它能很容易从一种语言翻译成另一种语言。

好吧，这也没有我想象中的那么糟糕！我们所做的只是把**************的转换。我们所做的就是把预排序遍历的DLR速记转换成代码。这个函数接收一个节点，并检查该节点是否存在。然后，它读取节点的数据，并对左节点的引用进行预排序搜索，接着对右*节点的引用进行预排序搜索。

哇! 递归在行动。我们实际上写了一个函数，但我们在自己内部调用了完全相同的函数。你的脑子转过来了吗？

好吧，好吧，跟着我，因为这个递归魔法实际上揭示了一件更重要的事情：深度优先搜索的时间复杂性。我们知道，DFS所需要的时间直接对应于一棵树有多大--具体来说，就是它有多少个节点，因为那是我们需要访问的节点，这将直接影响到我们遍历整棵树所需要的时间！但是空间的复杂性呢？

但是空间的复杂性呢？嗯，因为DFS通常是递归实现的，这就导致我们从自身内部多次调用一个函数。让我们回头看看我们的横断面示例树。如果我们实现了预排序搜索，我们将从节点1到2，从2到4，从节点4到8进行遍历。每次我们访问这些节点之一时，我们都会从我们传递根节点时调用的第一个函数中调用 preorderSearch 函数。

为什么这很重要？嗯，因为调用栈。你可能还记得在本系列的早期，我们了解到堆栈。这意味着只有当最后一个函数完成运行并返回时，我们才能开始从堆栈的顶部弹出那些_当前占用空间的函数。

深度优先搜索的递归实现

这意味着我们的调用栈将继续增长，直到我们到达一个叶子节点。

一旦我们到达一个叶子节点，我们的 "preorderSearch "函数将 "返回"，因为我们将传递给它一个 "左 "和一个 "右 "节点的引用，而这两个节点根本就不存在。

然后在我们的调用栈中的每个 "开放 "的函数将开始返回并关闭，直到我们回到我们开始调用的第一个函数。这一点很重要，因为它体现了深度优先搜索的_空间复杂性--即我们需要的内存空间取决于我们的树的高度，或O(h)。树的高度将告诉我们在最深的递归函数调用中需要多少内存，这将告诉我们运行深度优先搜索算法的最坏情况。

当我们退一步讲，这实际上是非常强大的--我们仅仅通过观察一个数据结构，就可以了解到一个算法的优势（和劣势！）！这是很重要的。既然我们已经知道了树的用途--例如在 "git bisect "命令中，以及在实现复杂的结构中，如迷宫--我们可以了解使用DFS搜索它们有多容易或多困难，只需简单地看一眼。

我不知道你怎么想的，但我想说的是，我们已经在成为算法向导的道路上走得很远了!

资源

深度优先搜索在编码面试中似乎经常出现，一开始可能很难让人理解。如果DFS仍然感到困惑，或者你只是想了解更多关于它的工作原理和不同的搜索策略，你可以从下面的链接开始。

1. Binary Trees, Professor H. Levent Akin

2. Traversals, Nathan Landman, Karleigh Moore, Jimin Khim

3. BFS vs DFS for Binary Tree, GeeksforGeeks

4. Applications of Depth First Search, GeeksforGeeks

5. Binary tree traversal: Preorder, Inorder, Postorder, mycodeschool