c++ - 在C++中为二进制搜索树创建删除功能

编辑*:我正在研究二进制搜索树的删除功能。我现在正在处理第一种情况。我认为这是正确的，但是我想知道是否可以递归或更有效地完成它。任何帮助表示赞赏。假设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;
        }
    }

最佳答案

您不需要指向父级的指针。这是一个应该起作用的递归版本:(通过引用传递(&)，以防您不知道，允许您修改变量，类似于通过指针传递； BSTNode *&是通过引用传递的指针，因此我们可以修改node-> left / right(指针)的值(不仅是它们指向的值))

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