JavaScript pt 1中的数据结构-二进制搜索树

二进制树对于了解您是新兴的开发人员还是后端工程师的微调性能很重要。它是计算机科学中用于可视化各种数据集的基本数据结构族。在此博客中，我们将深入介绍二叉树及其在JavaScript中的一些实现。您可以在此处看到我的完整回购，在该回购中，我已经开始编码其他数据结构，例如哈希表和链接列表，我计划在接下来的几周内通过博客发布这些信息— https://github.com/mega0319/data-结构

二叉树在本质上倾向于递归。想一想。该树从根节点开始，并且必须遵守最多只有两个子节点的规则。左孩子和右孩子。因此，如果一个节点只能有两个孩子，我们如何获得更大的树？

嗯，此示例中的每个子节点也可以是具有自己的两个子节点的父节点。左子节点和右子节点称为同级节点。

因此，每棵树可以由许多子树组成。以这种方式嵌套树是我们可以递归编写搜索和排序算法的原因，我们将在后面介绍。

该树的根节点为2，并且有两个子节点7和5。节点5有一个子节点9，后者有其自己的子节点，节点4。节点7有其自己的两个子节点2和6。你明白了。

用JS编码二进制搜索树

二进制搜索树是强大的构造。我们可以在其中组织和存储数据，并使用强大的方法来遍历它们。

二进制搜索 树是一种二进制树 ，按以下方式组织：

每个左子节点的值必须小于其父节点的值。

每个右子节点的值必须大于其父节点的值。

在实际代码中实现数据结构将帮助您巩固对结构的理解。如果您有一点好奇，我强烈建议您这样做。

让我们首先为二进制搜索树构建构造函数。

瞧！很简单。我们有我们的二进制搜索树构造函数。我们传入树的值，并将其左子节点和右子节点设置为null，因为我们知道二叉树最多只能有两个子节点。这是容易的部分。让我们向原型添加更多功能。

我们将构建的下一个功能是插入。 这将使我们可以将节点添加到二进制搜索树中。我们将使用递归来做到这一点。正如我之前提到的，二叉树本质上是递归的，我们只需几行代码就可以使用递归来完成非常强大的功能。

在此函数中，我们要检查的第一件事是要插入的值是否小于或等于我们的根节点。如果较小，则将检查根节点是否有左子节点。如果不是，我们将以基本情况为基础，并在该位置创建一个新的二进制搜索子树。如果有一个左子节点，我们会打我们的递归的情况下 ，再次调用insert，但这次有问题的左子节点上。如果您熟悉递归，则将很有意义。如果没有，我建议您在这里浏览我关于递归的博客。

插入二叉搜索树的对数运行时间为O（log n） 。

如果该值不小于或等于我们的根节点，则遍历树的右侧。从技术上讲，我可以在这里使用else语句，但是为了具体起见，我想明确一点。

好的，接下来我们将构建包含函数。

我们的contains函数将搜索我们的二进制搜索树，如果找到传入的值，则返回true；否则，返回false。注意，这也是一个递归函数。我们有基本情况，它将检查当前节点值是否等于我们的搜索值。然后，我们检查搜索值是否小于或等于根节点的值。与插入方法类似，我们将递归地遍历树以查找值。这样的二进制搜索也具有对数运行时间，并且具有O（log n）时间复杂度。大！现在，我们可以将节点插入树中并进行搜索。下一步是什么？

遍历树

如果我们想触摸树中的每个节点怎么办？如果我们能够触摸每个节点，那么我们将能够在节点上执行某些功能，例如将每个节点打印出来。我们将采用两种方式实现这一目标；使用深度优先搜索和广度优先搜索。

深度优先搜索

在深度优先搜索中，您从根节点开始，一直遍历分支直到最底部的节点或叶节点。

这是深度优先搜索的一种实现。

我们的深度优先搜索功能具有两个参数：iteratorFunc和order。

如您所见，我们再次利用了递归。除了订单类型，如果我们的根节点有一个左子节点，它将调用该函数。隐含基本情况，就好像不再有剩余的子节点一样，它将不再调用该函数。根据我们传递的顺序，它将在不同的时间点调用迭代器函数。

深度优先搜索方法有三种不同类型：

预购- 在遍历左右子树之前先命中当前节点数据
按顺序- 在遍历左侧子树之后但在右侧子树之前，命中当前节点数据
后置订单-遍历左右子树后命中当前节点数据

我们的迭代器函数是我们可以传入的函数。遍历树时，该函数可以对每个节点执行操作。我们可以使用这样简单的方法。

广度优先搜索

在广度优先搜索中，我们在遍历树的每个级别之前系统地遍历树的每个级别。这是一个外观的示例。

哦，看，一会儿循环！为了实现广度优先搜索，我们首先将一个数组“ queue”设置为具有元素“ this”。 “这”基本上是根节点。只要队列数组中有内容，我们的while循环就会运行。一旦进入while循环，我们将把第一项移出队列，并将其设置为treeNode。然后，我们将在该节点上用完迭代器功能。一旦完成，我们将检查左右子树并将其推入队列。这将逐级扫描树并相应地命中每个节点，直到没有剩余节点为止。辉煌！

DFS与BFS

DFS和BFS有许多不同的用例。假设我们建立了一个家谱树，并将其存储在二进制搜索树结构中。每个家庭成员节点还具有保存有关该成员是否已死亡的数据的属性。我们希望找到当前仍在世的所有成员。在这种情况下，深度优先搜索将是一个很好的解决方案，因为我们要遍历每个分支的最深节点或叶节点 ，并且我们想要的数据很可能在树中更深。

如果我们想要祖先呢？如果是这种情况，那么我们要收集顶部节点或根节点附近的所有节点。 最好通过此处的广度优先搜索逐级扫描树。