假设我的删除尝试重新平衡树的顺序（从左到右）。
我目前正在编写一个 BinarySearchTree 类，并且我的删除功能目前在大多数情况下都有效（我相信 - 我希望 <3）。我有几个边缘案例要处理：
- 删除根节点是行不通的，因为它没有父节点。
- 在 next 有两个孩子的最后一种情况下，如果它最左边的最右边的后代是右孩子本身，那么 newCurr 将指向 next，这将导致问题，因为 newCurr（又名 next）最终将与 New 交换。
根删除的建议解决方案：
我的解决方案是删除根并使用我的 BST 类的成员函数将根设置为新（使该节点成为根），然后将新的位置设置为 0/NULL。
A：这行得通，但我必须把案例工作放在各处。
在 BST 类中有一个虚拟父节点，它将简单地将根节点作为它的右手对象（由 billyswong 建议）。
A：这可能行得通，但我觉得我应该有特殊情况的工作来处理它。
删除两个孩子的建议解决方案：
我的解决办法，就是临时存储New的位置，将New在其父节点中的位置设置为New的右孩子，然后删除临时指针。
A：这会起作用，但它没有我想象的那么优雅。
- “旋转节点”（不知道我会怎么做，由 Agor 建议）。
这是我的代码：
if (root()->value() == val)
{
delete root();
this->setRoot(New);
newCurr->setLeft(0);
}
else if (newCurr == next)
{
Node *temp = New;
newCurr->setRight(New->right());
delete temp;
}
发帖者请告诉我此代码 1) 是否有效 2) 是否最佳。
编辑：很抱歉我在函数结束时对驼峰帽的使用不一致。对于我的变量名，我想不出更好的描述，但new它是 C++ 中定义的关键字。
Edit2：发布重构代码，但错误仍然存在。
void BinarySearchTree::del(int val)
{
//curr refers to the parent of next
//next is the node we will want to delete
Node* curr = 0;
Node* next = root();
//these will only be used if you get into
//the last case, where you have two children
//on next
Node* newCurr = curr;
Node* New = next;
//boolean value to check if you found the value
//in the binary search tree
bool found;
//set curr and next; will be false if val not found
found = setCurrAndNext(val, curr, next);
//get next to the node needing deletion
//and set curr to its parent
//pass by ref function
//return value is that you found it
if (found)
{
setNewCurrAndNew (newCurr, New);
}
else
{
return;
}
/* next is a leaf */
if (nextIsLeaf(next))
{
handleLeafCase(curr, next);
return;
}
/* next has a single child */
else if (nextHasSingleChild(next))
{
if(leftIsChild(next))
{
handleLeftCase(curr, next);
}
else
{
handleRightCase(curr, next);
}
}
/* next has two children */
else
{
if (newCurr == next)
{
Node *temp = New;
newCurr->setRight(New->right());
delete temp;
}
else if (next == curr->left())
{
if (New == newCurr->left())
{
curr->setLeft(New);
newCurr->setLeft(next);
}
else
{
curr->setLeft(New);
newCurr->setRight(next);
}
}
else
{
if (New == newCurr->left())
{
curr->setRight(New);
newCurr->setLeft(next);
}
else
{
curr->setRight(New);
newCurr->setRight(next);
}
}
if (next->left() == 0 && next->right() == 0)
{
newCurr->setRight(0);
newCurr->setLeft(0);
delete next;
}
else
{
if (next->left() == 0)
{
newCurr->setRight(next->left());
}
else
{
newCurr->setLeft(next->right());
}
delete next;
}
}
}
}