Двоичное дерево поиска — удаление узла без указателя на предшественника

У меня есть следующая реализация 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 один (из-за задания, которое я получил от своего учителя).

1

Решение

Как-то так, адаптируйся к своим требованиям и заполни пробелы

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;
}
}
}
2

Другие решения

Других решений пока нет …