三种情况:子叶,单子结点,双子结点
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;
}
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);
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;
}
}