二叉搜索树解析

二进制搜索树具有以下属性：左侧节点的值小于指向它的节点, 而右侧节点的值大于指向它的节点。

“二叉搜索树”中的节点不必指向其值紧随其后的节点。

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

插入二叉搜索树：考虑一个二叉树T。假设我们给T插入了一个ITEM信息。该ITEM作为叶子插入到树中。以下步骤说明了在二进制搜索树T中插入ITEM的过程。

1. 将ITEM与根节点进行比较。
2. 如果ITEM> ROOT NODE, 则继续执行右子项, 它成为右子树的根节点。
3. 如果ITEM <ROOT NODE, 则继续到左孩子。
4. 重复上述步骤, 直到遇到一个没有左右子树的节点。
5. 现在, 如果ITEM大于节点, 则将ITEM作为右子节点插入；如果ITEM小于节点, 则将ITEM作为左子节点插入。

示例：将3、1、4、6、9、2、5、7插入最初为空的二进制搜索树后, 显示二进制搜索树。

解决方案：在空的二进制搜索树中插入以上节点如图所示：

二进制搜索树中的删除：考虑一个二进制树T。假设我们要从二进制搜索树中删除给定的ITEM。要从二叉搜索树中删除一个ITEM, 根据被删除节点的子节点数, 我们有三种情况。

1. 删除的节点没有子节点：删除没有子节点的节点非常简单, 因为将节点替换为null。
2. 删除的节点只有一个子节点：用唯一的子节点替换已删除节点的值。
3. 删除节点只有两个子节点：在这种情况下, 将删除的节点替换为值最接近已删除节点的节点。为了找到最接近的值, 我们向左移动一次, 然后再向右移动一次。此节点称为直接前任。现在, 使用直接前任节点替换已删除节点的值, 然后使用case1或case2删除已替换节点。

示例：显示删除根节点后, 图（viii）中显示的二叉树。

解决方案：要删除根节点, 请首先用根中最接近的元素替换根节点。为此, 请先向左移动一个步骤, 然后再向右移一个尽可能远的位置, 然后删除替换的节点。删除后的树如图：