二叉搜索树 - 删除（C）

在开始删除之前我只想在二进制搜索树（BST）上放置一些灯，BST 中的每个节点最多可以有两个节点（左右子节点）。节点的左子树有一个 key 小于或等于其父节点的键。节点的右子树的密钥大于其父节点的密钥。

删除树中的节点，同时保持其二进制搜索树属性。

删除节点时有三种情况需要考虑。

• 情况 1：要删除的节点是叶节点（节点值为 22）。
• 情况 2：要删除的节点有一个子节点（节点值为 26）。
• 情况 3：要删除的节点有两个子节点（节点值为 49）。

案件说明：

1. 当要删除的节点是叶节点时，只需删除该节点并将 nullptr 传递给其父节点。
2. 当要删除的节点只有一个子节点时，将子值复制到节点值并删除子节点 （转换为案例 1）
3. 当要删除的节点有两个子节点时，可以将其右子树中的最小值复制到节点，然后可以从节点的右子树中删除最小值 （转换为案例 2）

注意： 右子树中的最小值可以最多包含一个子项，如果它具有左子项，则表示它不是最小值，或者它不遵循 BST 属性。

树中节点的结构和删除代码：

struct node
{
    int data;
    node *left, *right;
};

node* delete_node(node *root, int data)
{
  if(root == nullptr) return root;
  else if(data < root->data) root->left  = delete_node(root->left, data);
  else if(data > root->data) root->right = delete_node(root->right, data);

  else
  {
    if(root->left == nullptr && root->right == nullptr) // Case 1
    {
      free(root);
      root = nullptr;
    }
    else if(root->left == nullptr)       // Case 2
    {
       node* temp = root;
       root= root->right;
       free(temp);
    }
    else if(root->right == nullptr)      // Case 2
    {
       node* temp = root;
       root = root->left;
       free(temp);
    }
    else                                 // Case 3
    {
       node* temp = root->right;

       while(temp->left != nullptr) temp = temp->left;

       root->data = temp->data;
       root->right = delete_node(root->right, temp->data);
    }
  }
  return root;
}

上述代码的时间复杂度为 O（ h ），其中 h 是树的高度。