二叉搜尋樹 - 刪除（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 是樹的高度。