0

編集済み*：二分探索木の削除機能に取り組んでいます。私は今、最初のケースに取り組んでいます。これは正しいと思いますが、再帰的に実行できるのか、それともより効率的に実行できるのか疑問に思います。どんな助けでも大歓迎です。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;  
        }
    }
4

1 に答える 1

2

親へのポインタは必要ありません。動作するはずの再帰バージョンは次のとおりです。（参照渡し（&）は、不明な場合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);
}
于 2012-12-24T06:15:38.640 に答える