-1

二分探索木の削除関数を書こうとしています。考慮すべき 3 つのケースがあることはわかっていますが、どこから始めればよいかわかりません。

私のトラブル atm は、ほとんどの場合、削除する必要があるノードを見つけたら、削除する必要があるノードの後に​​親ノードをノードに設定する必要があるという事実から生じます。親ノードなどを保持するためにカーソルを使用する必要がありますか?

ノードの構造体があります：

struct bt_node {
  int data;
  bt_node* left;
  bt_node* right;
};

remove 関数の定義は次のように設定されます。

void remove(bt_node** top_ref, int data);

助けてくれてありがとう！

4

3 に答える 3

0

これを試すことができます： 

void delete_tree(struct tree **ptr,int item) 
{ 
      struct tree *move,*back,*temp; 

      if(*ptr==NULL) 
      { 
               printf("nEmpty tree..............n"); 
               return; 
      } 
      else 
      { 
               move=*ptr; 
               back=move;

               while(move->info!=item) 
               { 
                         back=move;

                         if(item<move->info) 
                         {
                                   move=move->left; 
                         } 
                         else 
                         { 
                                  move=move->right; 
                         } 
               }

               if(move->left!=NULL&&move->right!=NULL) 
               {

                         temp=move->right;

                         while(temp->left!=NULL) 
                         { 
                                  back=temp; 
                                  temp=temp->left; 
                         }

                         move->info=temp->info; 
                         move=temp; 
               }

               if(move->left==NULL&&move->right==NULL) 
               { 
                         if(back->right==move) 
                         { 
                                  back->right=NULL; 
                         } 
                         else 
                         { 
                                  back->left=NULL; 
                         }

                         free(move); 
                         return; 
               }

               if(move->left==NULL && move->right!=NULL) 
               { 
                         if(back->left==move) 
                         { 
                                  back->left=move->right; 
                         } 
                         else 
                         { 
                                  back->right=move->right; 
                         }

                         free(move); 
                         return; 
               }

               if(move->left!=NULL && move->right==NULL) 
               {
                          if(back->left==move) 
                         { 
                                  back->left=move->left; 
                         } 
                         else 
                         { 
                                  back->right=move->left; 
                         }

                         free(move); 
                         return;
于 2016-04-18T10:37:22.343 に答える
0

それを行うためのきちんとした方法は、再帰を使用することです。削除関数に、現在のノードへの参照を呼び出し元の関数に返すように依頼します。そうすれば、親ノードを簡単に変更できます。

参照用の再帰コードを次に示します。

構造宣言:

 typedef struct node {
    int info;
    struct node* lchild;
    struct node* rchild;
}NODE;


削除のコード:

NODE* deleteElem(NODE* root, int elem) {
    NODE* save;
    if(root == NULL) {
        printf("Element not in the tree !\n");
        return;
    }
    if(root->info == elem) {
        if(root->rchild == NULL && root->lchild == NULL) {                  // no child
            free(root);
            return NULL;
        }
        else if(root->rchild == NULL || root->lchild == NULL) {             // one child
            if(root->rchild == NULL) {
                save = root->lchild;
                free(root);
                return save;
            }
            else {
                save = root->rchild;
                free(root);
                return save;
            }
        }
        else {                                                             // two children
            save = findPred(root->lchild);
            root->info = save->info;
            root->lchild = deleteElem(root->lchild, root->info);
            return root;
        }
    }
    else if(root->info < elem) {
        root->rchild = deleteElem(root->rchild, elem);
    }
    else if(root->info > elem) {
        root->lchild = deleteElem(root->lchild, elem);
    }
    return root;
}
NODE* findPred(NODE* root) {
    static NODE* pred;
    if(root == NULL) {
        return pred;
    }
    else {
        pred = root;
        return findPred(root->rchild);
    }
}

PS : 申し訳ありませんが、関数のプロトタイプ宣言に気付きました。プロトタイプの宣言に合わせてこのコードを変更するのがそれほど難しくないことを願っています。

于 2013-08-08T17:44:43.907 に答える
0

簡単な方法は、検索コードを拡張して、ツリーをたどる際に 2 番目の参照で「最後の」親を追跡することです。この「拡張」検索は、ノードとノードの親を返します。

次に、削除関数でその検索関数を使用するため、削除ロジックで特別なことを行う必要はありません。

于 2013-08-08T17:01:45.020 に答える