删除

删除函数用于从二叉搜索树中删除指定的节点。但是，我们必须以不违反二叉搜索树属性的方式从二叉搜索树中删除节点。二叉搜索树中删除节点有三种情况。

要删除的节点是叶子节点

这是最简单的情况，在这种情况下，将叶子节点替换为 NULL 并简单地释放分配的空间。

在下图所示中，我们要删除节点 85，因为该节点是叶子节点，因此该节点将被 NULL 替换，并释放分配的空间。

要删除的节点只有一个子节点。

在这种情况下，用其子节点替换节点，然后删除包含要删除的值的子节点。简单地将其替换为 NULL 并释放分配的空间。

在下图所示中，要删除节点 12。它只有一个子节点。该节点将被其子节点替换，并且被替换的节点 12（现在是叶子节点）将被简单删除。

要删除的节点有两个子节点。

与其他两种情况相比，这是一种稍微复杂的情况。但是，要删除的节点会递归地替换为其后序继节点或前驱节点，直到节点值（要删除的值）位于树的叶子上。完成此过程后，用 NULL 替换节点并释放分配的空间。

在下图所示中，要删除节点 50，它是树的根节点。下面是树的后序遍历。

6, 25, 30, 50, 52, 60, 70, 75.

将 50 替换为其后序继节点 52。现在，50 将被移动到树的叶子上，该叶子将被简单删除。

算法

删除 (树, 项目)

• 步骤 1：如果树 = NULL
    写“树中未找到项目”否则如果项目 < 树 -> 数据
   删除(树->左, 项目)
   否则如果项目 > 树 -> 数据
    删除(树 -> 右, 项目)
   否则如果树 -> 左 且 树 -> 右
   设置 temp = 查找最大节点(树 -> 左)
   设置树 -> 数据 = temp -> 数据
    删除(树 -> 左, temp -> 数据)
   否则
    设置 temp = 树
    如果树 -> 左 = NULL 且 树 -> 右 = NULL
    设置树 = NULL
   否则如果树 -> 左 != NULL
   设置树 = 树 -> 左
   否则
     设置树 = 树 -> 右
   [IF 结束]
   释放 temp
  [IF 结束]
• 步骤 2：结束

函数