0

二分探索木からノードを削除する機能を実装しています。関数のプロトタイプが設定されており、変更できません。学校の課題です。私のコード:

typedef struct tBSTNode {
    char Key;                                                                 
    struct tBSTNode * LPtr;                                
    struct tBSTNode * RPtr;  
} *tBSTNodePtr; 

void BSTDelete (tBSTNodePtr *RootPtr, char K) {
  tBSTNodePtr *tmp;

  if (*RootPtr != NULL) {
    if (K < (*RootPtr)->Key)
        BSTDelete(&(* RootPtr)->LPtr, K);
    else if (K > (*RootPtr)->Key)
        BSTDelete(&(* RootPtr)->RPtr, K);
    else {
            if ((* RootPtr)->LPtr == NULL) {
                /* there is only right branch or none*/
                tmp = RootPtr;
                *RootPtr = (* RootPtr)->RPtr;
                free(*tmp);
                *tmp = NULL;
            }
            else if ((* RootPtr)->RPtr == NULL) {
                /* there is only left branch or none*/
                tmp = RootPtr;
                *RootPtr = (* RootPtr)->LPtr;
                free(*tmp);
                *tmp = NULL;
            }
            else
                /* there are both branches, but that is for another topic*/
        }
    }
}  

このコードは、削除するノードに接続されているブランチがない場合に備えて正しく機能します。*tmp = NULL;に問題があると思います。行と私は自分のアドレスをブランチの残りの部分に失っていますが、一方で、この行が含まれていない場合は SEGFAULT を取得しており、その理由を理解しようとしています.

編集:

わかりました、今私は間違いがどこにあったかを知っています。ばかげた間違いです。tBSTNodePtr tmp;を使用するべきでした。tBSTNodePtr *tmp;の代わりに

4

2 に答える 2

1

ポインターの使用に問題があります。持っていてsometype *ptr、このptrが書き込みスペースをアドレス指定しているかどうかを確認します(ptr!=NULL)*ptrたとえば、構造体など、値自体を参照しています。C のポインター型の詳細を参照してください。

于 2012-11-05T09:31:42.403 に答える
0

削除のロジックが間違っています

 if ((* RootPtr)->LPtr == NULL) {
                /* there is only right branch or none*/
                tmp = RootPtr;
                *RootPtr = (* RootPtr)->RPtr;
                free(*tmp);
                *tmp = NULL;
            }

このコードでは、必要なノードを削除していますが、そのノードの子ルートを追加していません

 if ((* RootPtr)->LPtr == NULL) {
                /* there is only right branch or none*/
                tmp = RootPtr;
                *RootPtr = (* RootPtr)->RPtr;
                free(*tmp);
                *tmp = NULL;
                insert(RootPtr);  //insert the child node again in the tree
            }
于 2012-11-05T09:24:31.887 に答える