二叉搜索树

二叉搜索树具有这样的特性：左侧节点包含的值小于指向它的节点，而右侧节点包含的值大于指向它的节点。

“二叉搜索树”中的节点不必指向其值紧邻的前驱和后继节点。

示例：图中显示的树是一个二叉搜索树。

插入到二叉搜索树：考虑一个二叉树 T。假设我们有一个信息项 ITEM 要插入到 T 中。ITEM 作为叶子插入到树中。以下步骤解释了将 ITEM 插入到二叉搜索树 T 中的过程。

1. 将 ITEM 与根节点进行比较。
2. 如果 ITEM>根节点，则移动到右子节点，它将成为右子树的根节点。
3. 如果 ITEM<根节点，则移动到左子节点。
4. 重复上述步骤，直到遇到没有左子树和右子树的节点。
5. 现在，如果 ITEM 大于该节点，则将 ITEM 作为右子节点插入；如果 ITEM 小于该节点，则将 ITEM 作为左子节点插入。

示例：将 3、1、4、6、9、2、5、7 插入到最初为空的二叉搜索树后，显示该二叉搜索树。

解决方案：将上述节点插入到空的二叉搜索树中，如图所示

在二叉搜索树中删除：考虑一个二叉树 T。假设我们要从二叉搜索树中删除给定的 ITEM。要从二叉搜索树中删除一个 ITEM，我们有三种情况，具体取决于要删除节点的子节点数。

1. 删除的节点没有子节点： 删除没有子节点的节点非常简单，只需用 null 替换该节点即可。
2. 删除的节点只有一个子节点：用唯一的子节点替换删除的节点的值。
3. 删除的节点只有两个子节点：在这种情况下，用值最接近被删除节点的节点替换被删除的节点。要找到最接近的值，我们先向左移动一步，然后尽可能向右移动。此节点称为直接前驱。现在，用直接前驱的值替换被删除节点的值，然后使用情况 1 或情况 2 删除被替换的节点。

示例：删除根节点后，显示图 (viii) 中显示的二叉树。

解决方案：要删除根节点，首先用根节点最接近的元素替换根节点。为此，首先向左移动一步，然后尽可能向右移动到该节点。然后删除被替换的节点。删除后的树如图所示