我有以下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;
}
}
}