构建二叉搜索树

我们知道，一个节点可以有两个子节点，节点本身可以以递归方式表示一棵树。我们将定义功能更强大的节点类，使其具备查找最大值、最小值、前生值和后生值所需的所有功能。稍后，我们还将为节点添加删除功能。下面是 BST 节点类的代码：

节点类看起来简单明了，与我们在上一节中定义的步骤相吻合。每个新节点都是叶子节点，因此在创建时没有左右节点。我们知道，可以在节点左边找到较小的值，从而找到最小值，因此我们要到最左边的节点和最右边的节点寻找最大值。对于后继节点，我们要从给定节点的右侧子树中找到节点的最小值，并从左侧子树中找到前代节点的最大值。

现在，我们需要一个 BST 结构来在树中添加新节点，以便遵循插入原则：

如果我们看一下前面的代码，BST 类只有一个属性，它将标记根节点。在构建 BST 对象的过程中，我们传递了一个单一的值，它将被用作树的根节点。isEmpty 方法会检查树是否为空。insert 方法允许我们在树中添加一个新节点。该逻辑会检查值是否大于或小于根节点，并遵循 BST 原则在正确的位置插入新节点。如果值已经插入，我们将忽略它，避免向树中添加。

我们还有一种 traverse 方法，可以遍历节点，并以有序的格式查看数据（先左侧，再节点，再右侧节点值）。它有一个指定的名称，我们将在下一节探讨。现在，让我们准备一段示例代码，使用 BST 类并添加一些数字，检查数字是否以正确的方式存储。如果 BST 正常工作，那么无论我们如何插入数字，遍历都会显示一个排序的数字列表：

如果我们看一下前面的代码，10 是我们的根节点，然后，我们随机添加了新节点。最后，我们调用了遍历方法来显示节点以及节点在二叉搜索树中的存储方式。下面是前面代码的输出结果：

实际树的外观是这样的，与 BST 实现的预期效果完全一致：

现在，我们将在 BST 类中添加搜索部分。我们要查找树中是否存在值。如果值不在 BST 中，则返回 false，否则返回节点。下面是简单的搜索功能：

在前面的代码中，我们可以看到，我们正在树中从节点开始搜索一个值，并沿着树的左侧或右侧迭代搜索。如果没有找到带有该值的节点，则返回该节点的叶子，即 NULL。我们可以这样测试代码：

输出结果如下。由于 14 不在我们的列表中，它将显示 Not Found，而对于 36，它将显示 Found：

现在，我们将进入编码中最复杂的部分，即删除节点。我们需要实现一个节点可以有 0 个、1 个或 2 个子节点的每种情况。下图向我们展示了删除节点时需要满足的三个条件，并确保二叉搜索树在操作后仍然是二叉搜索树。在处理有两个子节点的节点时，我们必须小心谨慎。因为我们需要在节点之间来回切换，所以我们需要知道哪个节点是当前节点的父节点。因此，我们需要添加一个额外的属性来跟踪任何节点的父节点：

以下是我们添加到 Node 类中的代码更改：

现在，该代码块还为新创建的节点与其直接父节点创建了父节点关系。我们还想将删除功能附加到单个节点上，这样我们就可以找到一个节点，然后使用 delete 方法将其删除。以下是删除功能的代码：

第一个条件是检查节点是否是叶子节点。如果节点是叶子节点，那么我们只需让父节点删除子节点（左节点或右节点）的引用。这样，该节点就会从树中断开，从而满足我们的第一个条件，即有零个子节点。

下一个条件实际上是检查我们的第三个条件，即一个节点有两个子节点。在这种情况下，我们要获取节点的后继节点，将后继值赋值给节点本身，然后删除后继节点。这只是简单地复制粘贴后继节点的数据。

接下来的两个条件将检查节点是否只有一个子节点，如案例 2 图所示。由于节点只有一个子节点，它可以是左子节点，也可以是右子节点。因此，该条件会检查单个子节点是否是节点的左子节点。如果是，我们就需要根据节点本身与其父节点的位置，将左子节点指向节点父节点的左或右引用。同样的规则也适用于右节点。在这里，右节点的引用被设置为其父节点的左或右子节点，而不是基于节点位置的引用。

由于我们更新了节点类，因此需要对 BST 类进行一些修改，以便插入和删除节点。插入代码如下：

代码看起来与我们之前使用的代码相似，但有一个小改动。现在，我们在创建新节点时会发送当前节点的引用。当前节点将作为新节点的父节点。新的 Node($data, $node) 代码实际上就是这样做的。

对于删除节点，我们可以先进行搜索，然后使用节点类中的 delete 方法删除搜索到的节点。因此，remove 函数本身将非常小，就像这里的代码一样：

如代码所示，我们首先搜索数据。如果节点存在，我们就使用 delete 方法将其删除。现在，让我们用 remove 调用来运行之前的示例，看看是否有效：

我们只是从树中删除 15，然后从根开始遍历树。现在我们将看到以下输出：

我们可以看到，15 节点不再是 BST 的一部分。这样，我们就可以删除任何节点，如果我们使用同样的方法遍历，就会看到一个排序列表。如果我们看一下前面的输出，就会发现输出是以升序显示的。这背后是有原因的，我们将在下一个主题—​不同的树遍历方法中探讨。