c++ - 在 C++ 中为二叉搜索树创建删除函数

Question

已编辑*：我正在研究二叉搜索树的删除功能。我现在正在处理第一个案例。我认为这是正确的，但我想知道它是否可以递归或更有效地完成。任何帮助表示赞赏。假设 BSTSearch 搜索一个节点，isLeaf如果该节点是叶子，则返回 true，并且每个节点都有一个指针，允许它们访问其父节点。

void
BinarySearchTree::BSTDelete(int x, BSTNode *node){

    BSTNode *deleteNode;
    deleteNode = BSTSearch(x,node); 

    if(isLeaf(deleteNode)){

        if(deleteNode->sortkey > (deleteNode->parent)->sortkey){
             delete (deleteNode->parent)->right;
            (deleteNode->parent)->right = NULL;
        }

        else{
            delete (deleteNode->parent)->left;
            (deleteNode->parent)->left = NULL;  
        }
    }

Answer 1

您不需要指向父级的指针。这是一个应该可以工作的递归版本：（按引用传递（&），以防您不知道，允许您修改变量，类似于按指针BSTNode *&传递；是按引用传递的指针，因此我们可以修改值节点->左/右（指针）（不仅仅是他们指向的东西））

void BinarySearchTree::BSTDelete(int x, BSTNode *&node)
{
   if (node == NULL)
      return;
   if (x == node->sortKey)
   {
      if (isLeaf(node))
      {
         delete node;
         node = NULL;
      }
      else
      {
         // other stuff goes here
      }
      return;
   }
   else if (x < node->sortKey)
      BSTDelete(x, node->left);
   else
      BSTDelete(x, node->right);
}