親ポインタを持つバイナリ検索ツリーからノードを削除する

Question

バイナリ検索ツリーから特定のキーを持つノードを削除するアルゴリズムの作業中です。

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

typedef int ElType; 

typedef struct Tree { 
    ElType key; 
    struct Tree *left; 
    struct Tree *right; 
    struct Tree *parent; 
} Tree; 

Tree* InsertBST(Tree* t, int k) 
{ 
    if (t == NULL) { 
     Tree* w = (Tree*) malloc(sizeof(Tree)); 
     w->key = k; 
     w->left = NULL; 
     w->right = NULL; 
     w->parent = NULL; 
     return w; 
    } 

    if (k <= t->key) { 
     t->left = InsertBST(t->left, k); 
     t->left->parent = t; 
    } 
    else { 
     t->right = InsertBST(t->right, k); 
     t->right->parent = t; 
    } 

    return t; 
} 

Tree* DeleteMaxOfBST(Tree* t, ElType *deleted_value) 
{ 
    if (t == NULL) { 
     *deleted_value = -1; 
     return NULL; 
    } 

    if (t->right == NULL) { 
     *deleted_value = t->key; 
     Tree* w = t->left; 
     w->parent = t->parent; 
     free(t); 
     return w; 
    } 

    t->right = DeleteMaxOfBST(t->right, deleted_value); 
    return t; 
} 

Tree* DeleteNodeOfBST(Tree* t, int k) 
{ 
    if (t == NULL) return NULL; 

    if (k < t->key) { 
     t->left = DeleteNodeOfBST(t->left, k); 
     return t; 
    } 
    else if (k > t->key) { 
     t->right = DeleteNodeOfBST(t->right, k); 
     return t; 
    } 
    else if (t->left == NULL) { 
     Tree* w = t->right; 
     w->parent = t->parent; 
     free(t); 
     return w; 
    } 
    else { 
     ElType max_left; 
     t->left = DeleteMaxOfBST(t->left, &max_left); 
     t->key = max_left; 
     return t; 
    } 
} 

一般的な考え方は、私が親ノードへのポインタとBSTと協力し、いずれかのキーIを持つノードを削除できるようにしたいということです。これまでのところ、私は次のコードを思い付くことができましたBSTの構造を保存しながら指定します。

私のコードはいくつかのツリーのいくつかのキーで動作しますが、見た目のパターンがない他のキーではクラッシュします。私は、次のエラーを取得する：

Segmentation fault (core dumped) 

私は親ノードへのポインタを台無しにしているが、障害がどこにあるかかなり正確に特定することはできません考えるために傾斜しています。私はC言語には比較的新しいので、ポインタが実際にここの問題になっているかどうか、そしておそらくこれを修正する方法についてのコメントは感謝しています。ここで

Answer 1

は

/* C Program for Insertion and Deletion in Binary Search Tree Recursive */ 

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

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

struct node *insert(struct node *ptr, int ikey); 
void display(struct node *ptr,int level); 
struct node *del(struct node *ptr, int dkey); 

int main() 
{ 
    struct node *root=NULL,*ptr; 
    int choice,k; 
    while(1) 
    { 
     printf("\n"); 
     printf("1.Insert\n"); 
     printf("2.Delete\n"); 
     printf("3.Display\n"); 
     printf("4.Quit\n"); 
     printf("\nEnter your choice : "); 
     scanf("%d",&choice); 

     switch(choice) 
     { 
     case 1: 
      printf("Enter the key to be inserted : "); 
      scanf("%d",&k); 
      root = insert(root, k); 
      break; 
     case 2: 
      printf("Enter the key to be deleted : "); 
      scanf("%d",&k); 
      root = del(root,k); 
      break; 
     case 3: 
      display(root,0); 
      break; 
     case 4: 
      exit(1); 
     default: 
      printf("\nWrong choice\n"); 
     }/*End of switch */ 
    }/*End of while */ 

    return 0; 

}/*End of main()*/ 

struct node *insert(struct node *ptr, int ikey) 
{ 
    if(ptr==NULL) 
    { 
     ptr = (struct node *) malloc(sizeof(struct node)); 
     ptr->info = ikey; 
     ptr->lchild = NULL; 
     ptr->rchild = NULL; 
    } 
    else if(ikey < ptr->info) /*Insertion in left subtree*/ 
     ptr->lchild = insert(ptr->lchild, ikey); 
    else if(ikey > ptr->info) /*Insertion in right subtree */ 
     ptr->rchild = insert(ptr->rchild, ikey); 
    else 
     printf("\nDuplicate key\n"); 
    return ptr; 
}/*End of insert()*/ 

void display(struct node *ptr,int level) 
{ 
    int i; 
    if(ptr == NULL)/*Base Case*/ 
     return; 
    else 
    { 
     display(ptr->rchild, level+1); 
     printf("\n"); 
     for (i=0; i<level; i++) 
      printf(" "); 
     printf("%d", ptr->info); 
     display(ptr->lchild, level+1); 
    } 

     printf("\n"); 

}/*End of display()*/ 


struct node *del(struct node *ptr, int dkey) 
{ 
    struct node *tmp, *succ; 

    if(ptr == NULL) 
    { 
     printf("dkey not found\n"); 
     return(ptr); 
    } 
    if(dkey < ptr->info)/*delete from left subtree*/ 
     ptr->lchild = del(ptr->lchild, dkey); 
    else if(dkey > ptr->info)/*delete from right subtree*/ 
     ptr->rchild = del(ptr->rchild, dkey); 
    else 
    { 
     /*key to be deleted is found*/ 
     if(ptr->lchild!=NULL && ptr->rchild!=NULL) /*2 children*/ 
     { 
      succ=ptr->rchild; 
      while(succ->lchild) 
       succ=succ->lchild; 
      ptr->info=succ->info; 
      ptr->rchild = del(ptr->rchild, succ->info); 
     } 
     else 
     { 
      tmp = ptr; 
      if(ptr->lchild != NULL) /*only left child*/ 
       ptr = ptr->lchild; 
      else if(ptr->rchild != NULL) /*only right child*/ 
       ptr = ptr->rchild; 
      else /* no child */ 
       ptr = NULL; 
      free(tmp); 
     } 
    } 
    return ptr; 
}/*End of del()*/ 

はそれが役立つことを願って..................バイナリ検索ツリーの再帰的で挿入と削除のためのCプログラムのソースコードであります君は。詳細については、二分探索木--->に複数のオペレーションのためにここに訪問し、あなたのコードは、それが時にセグメンテーションフォールトが発生している場所を正確に言うのは難しい実行方法のいずれかの例のないC Program for Insertion and Deletion in Binary Search Tree Recursive

ので

Answer 2

C Program for binary search tree deletion without recursion、プログラムが実行中です。プログラムがセグメンテーションフォルトに遭遇すると、プログラムが何らかの理由でメモリにアクセスしようとしていることを意味します。これは、一般的に、あなたのポインタがメモリ内のアドレスを指し示すようにすることを意味します。

私の提案は、コードをステップバイステップで実行し、問題の発生場所を確認することです。あるいは、あなたのプログラムが持っているメモリの問題を示すことができるデバッガを見つけてください。私はValgrindというプログラムがUbuntuや他のLinuxのベストマシンにも存在することを知っていますが、ほかのOSで利用できるものは何か分かりません。 Valgrindについての詳細は、http://valgrind.org/をご覧ください。私は自分のプログラムで潜在的なメモリ処理の問題をチェックする必要があるときはいつでもそれを使用します。

それ以外は、mallocを使用して作成したスペースだけでなく、ポインタがどこを指しているのかを正確に把握してください。指定したノードを削除するときは、ツリーを正しく再接続してください。手動でメモリを操作することは苦痛になることがありますが、そのメモリを奪うことになります。