二叉搜索树解析

二进制搜索树具有以下属性:左侧节点的值小于指向它的节点, 而右侧节点的值大于指向它的节点。
“二叉搜索树”中的节点不必指向其值紧随其后的节点。
示例:图中显示的树是二叉搜索树。
二叉搜索树解析 插入二叉搜索树:考虑一个二叉树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)中显示的二叉树。
解决方案:要删除根节点, 请首先用根中最接近的元素替换根节点。为此, 请先向左移动一个步骤, 然后再向右移一个尽可能远的位置, 然后删除替换的节点。删除后的树如图:
二叉搜索树解析

    推荐阅读