二叉搜索树 - 删除节点，没有指针的前任

Question

我有以下实现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结构（因为我从我的老师收到的任务）。

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