Двоичное дерево поиска — удаление узла без указателя на предшественника
У меня есть следующая реализация BST:
struct BstNode
{
int value;
BstNode* leftSubnode;
BstNode* rightSubnode;
BstNode(int value)
{
this->value = value;
this->leftSubnode = this->rightSubnode = nullptr;
}
};
struct BstTree
{
BstNode* root;
};
и вы можете видеть, что у меня нет указателя на предшественника (родителя текущего узла). У меня нет проблем с реализацией методов добавления / отображения, но я не могу понять, как удалить узел из моей структуры. Есть ли возможность сделать это, когда у вас есть только указатели на левый и правый узел? Обратите внимание, что все методы должны быть реализованы для BstTree структура, а не для BstNode один (из-за задания, которое я получил от своего учителя).
Решение
Как-то так, адаптируйся к своим требованиям и заполни пробелы
void remove(BstTree& tree, int value)
{
BstNode* parent = nullptr;
BstNode* node = tree.root;
while (node)
{
if (node->value == value)
{
if (parent)
{
// remove node using the parent pointer
}
else
{
// remove the root node
}
return;
}
if (value < node->value)
{
// go down left branch
parent = node;
node = node->leftSubNode;
}
else
{
// go down right branch
parent = node;
node = node->rightSubNode;
}
}
}
Другие решения
Других решений пока нет …