1

非再帰的に作成した BST のリーフ ノードを削除しようとしています。問題は、リーフ ノードを削除しようとしたときに、セグメンテーション エラーが発生し、その理由がわかりません。私がコメントしたコードが問題を引き起こしていると思います。そのノードを削除するという考えは間違っていますか、それとも BST からノードを削除する他の方法はありますか?

     #include <stdio.h>
     #include <stdlib.h>

      struct BSTnode
    {
     int data;
     struct BSTnode *left,*right,*parent;

    };

     typedef struct BSTnode node;

     void insert(node **root,int val)
    {
     node *ptr,*newptr;

     newptr=(node *)malloc(sizeof(node));
     newptr->left=NULL;
     newptr->right=NULL;
     newptr->parent=NULL;
     newptr->data=val;

     if((*root)==NULL)
    {
     (*root)=newptr;
     return;
    } 

     ptr=(*root);  

     while(ptr!=NULL && ptr->data!=val)
    {
      if(ptr->data >val )
     {
       if(ptr->left!=NULL)
        ptr=ptr->left;
       else
      {
       ptr->left=newptr;
       newptr->parent=ptr;
       break;
      }
    } 
     else
    {
      if(ptr->right!=NULL)
       ptr=ptr->right;
      else
     {
       ptr->right=newptr;
       newptr->parent=ptr;
       break;
      }
    }
   }

  }

    void deleteLeaf(node **root)
  {

      node *leafParent=NULL;

      if((*root)->left!=NULL)
       deleteLeaf(&((*root)->left));

      if((*root)->right!=NULL)
       deleteLeaf(&((*root)->right));


      if((*root)->left==NULL && (*root)->right==NULL)
     {

      /*  leafParent=(*root)->parent;

          if(leafParent->left==(*root))
           leafParent->left=NULL;
          else
           leafParent->right=NULL;
      */

          free(*root);
        }
      }

 void inorder(node *root)
{
  if(root->left!=NULL)
   inorder(root->left);

  printf(" %d ", root->data);

  if(root->right!=NULL)
   inorder(root->right);
}

 main()
{
 node *root=NULL;
 int i,n,val;

 printf("\n How many elements ?");
 scanf("%d",&n);

 for(i=0;i<n;++i)
{
 scanf("%d",&val);
 insert(&root,val);

}

 printf("\n Inorder traversal : ");
 inorder(root);

 deleteLeaf(&root);
 printf("\n Inorder traversal : ");
 inorder(root);
}
4

2 に答える 2

0

実際、関数 deleteLeaf には、(コメントアウトされた) leafParent が NULL である場合があり、それを leafParent->left で逆参照するとすぐに、セグ フォールトが発生します。したがって、次のようにそこにチェックを入れる必要があります。

    leafParent=(*root)->parent;
    if (leafParent)
    {
        if(leafParent->left==(*root))
        {
            leafParent->left=NULL;
        }
        else
        {
            leafParent->right=NULL;
        }
    }

これにより、セグ フォールトが防止されますが、関数が目的の処理を実行するかどうかはわかりません...つまり、リーフ ノードを削除するだけのロジックを作成するために、まだ微調整が必​​要な場合があります (あなたがやろうとしていることです）。

于 2012-11-01T12:01:23.617 に答える
0

葉だけを実際に削除しているのではないと思います-ツリー全体を再帰的に削除しています。各ノードについて、最初に葉を削除してから、それが葉であるかどうかを確認します((left == NULL) && (right == NULL))-これは、子孫を削除したばかりなので明らかにそうです-そして次に消して。

最初の問題は、Chris がすぐに指摘したように、leafParent が NULL になる可能性があることを確認していないことです。それを確認するか、ルートノードの親をそれ自体に設定して、NULL を逆参照しないようにします。もう1つの（もっと悪い）問題は、メモリを解放するとポインターを無効にしないことです。ポインターを解放したらすぐにポインターをNULLに設定することをお勧めします。後でチェックを行わないと、セグメンテーション違反が発生しますが、メモリのチャンクが他の構造によって割り当てられる可能性があるときに、後でポインターを使用してメモリを静かに破損することはありません。ラッパーを作成してそれを行うこともできます (また、NULL ポインターを解放しようとする試みをチェックすることもできます。これは、実際には何もせずに何もしない有効な操作です - 少なくとも一部のプラットフォームでは)。この特定のケースでは、

つまらない補足として、コードでは、それはどちらかであるかint main(void) { ... }、そうではint main(int argc, int **argv) { ... }ないmain(). :-)

于 2012-11-01T12:53:32.423 に答える