目前,我目前正在尝试修复我正在使用递归的查找和删除功能。但是,我正在运行的问题是,当它到达案例二的结尾时,如何确定它是否会导致案例零或案例一。
以下是我正在尝试做的事情的简短描述:案例二(两个子项) - 与右侧子树的最小值交换,这会导致情况为零或情况一。
bool findAndRemove(const Type& v)
{
return findAndRemove(root, nullptr, v);
}
bool findAndRemove(Node<Type> *fr, Node<Type> *parent, const Type& v) const
{
if (fr == nullptr)
{
return true;
}
if (v < fr->element)
{
return findAndRemove(fr->left, fr, v);
}
else if (v > fr->element)
{
return findAndRemove(fr->right, fr, v);
}
else
{
switch (GetChildren(fr))
{
case 0:
if (parent->left == fr)
{
parent->left = nullptr;
delete fr;
}
else
{
parent->right = nullptr;
delete fr;
}
break;
case 1:
if (parent->left == fr)
{
if (fr->left != nullptr)
{
parent->left = fr->left;
delete fr;
}
else
{
parent->left = fr->right;
}
}
else
{
if (fr->right != nullptr)
{
parent->right = fr->right;
delete fr;
}
else
{
parent->right = fr->left;
}
}
break;
case 2:
{
Node<Type> * swap = fr->right;
while (swap->left != nullptr)
{
swap = swap->left;
}
Type temp = fr->element; // 30
temp = swap->element; // 35
swap->element = fr->element; // 30
fr->element = temp;
//temp = swap->element;
//swap->element = temp;
//temp = fr->element;
break;
}
}
}
return false;
}
根据算法:
- 在右侧子树中查找最小值;
- 将要删除的节点的值替换为找到的最小值。现在,右子树包含一个重复项!
- 将"删除"应用于右侧子树以删除重复项。
在代码中,swap
指向该右侧子树中的最小节点,因此,如果在此节点上调用 findAndRemove
函数,只需将其删除即可。
{
// STEP 1: find a minimum value in the right subtree;
Node<Type> * swap = fr->right;
while (swap->left != nullptr)
{
swap = swap->left;
}
// STEP 2: replace value of the node to be removed with found minimum.
fr->element = swap->element;
// STEP 3: apply remove to the right subtree to remove a duplicate.
// Here you should call 'findAndRemove' on 'swap' node
break;
}