搜索树的删除

三种情况：子叶，单子结点，双子结点

BTreeNode* Findrightmin(BTreeNode* root)
{
    BTreeNode* cur = root;
    while (cur -> left_child != nullptr)
    {
        cur = cur->left_child;
    }
    return cur;
}
void delete_bst_value(BTreeNode* root, int value) {
    if (root == nullptr)
        return;
    BTreeNode* prev = root;
    BTreeNode* cur = root ->right_child;
    while (cur->value != value)
    {
        if (value > cur->value)
        {
            prev = cur;
            cur = cur->right_child;
        }
        else
        {
            prev = cur;
            cur = cur->left_child;
        }
    }
    if (root != cur)
    {
        root = cur;
    } // 找到 value 此时设置为 root 
    if (root->left_child == nullptr && root->right_child != nullptr)
    {
        BTreeNode* left = root->right_child->left_child;
        BTreeNode* right = root->right_child->right_child;
        BTreeNode* cur = root->right_child;
        root->value = root->right_child->value;
        root->left_child = left;
        root->right_child = right;
        delete cur;
    }
    else if (root->left_child != nullptr && root->right_child == nullptr)
    {
        BTreeNode* left = root->left_child->left_child;
        BTreeNode* right = root->left_child->right_child;
        BTreeNode* cur = root->left_child;
        root->value = root->left_child->value;
        root->left_child = left;
        root->right_child = right;
        delete cur;
    }
    else if (root->left_child == nullptr && root->right_child == nullptr)
    {
        if (root->value > prev->value)
        {
            prev->right_child = nullptr;
        }
        else
        {
            prev->left_child = nullptr;
        }
        delete root;
    }
    else
    {
         BTreeNode* temp = Findrightmin(root->right_child);   //此处处理为，将原root左结点放入temp左侧，然后将root右子结点作为新的根结点，做法破坏树高。
         BTreeNode* cur = root->right_child;
         temp->left_child = root->left_child;
         BTreeNode* left = root->right_child->left_child;
         BTreeNode* right = root->right_child->right_child;
         root->value = root->right_child->value;
         root->right_child = right;
         root->left_child = left;
         delete cur;
    }
    
}