Ошибка сегментации при удалении узла из BST - PullRequest
0 голосов
/ 27 сентября 2018

Я получаю ошибку сегментации при удалении узла из bst.

Я сделал функцию delnode для

удаления узла из дерева двоичного поиска

Я применяю его в трех случаях
- когда узел имеет два дочерних узла
- когда узел является конечным узлом
- когда есть только дочерний элементузел, который мы хотим удалить.

код -

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

struct node{
  int data;
  struct node * left ;
  struct node * right ;
};
struct node * newnode(int d){
    struct node * nn = (struct node *)malloc(sizeof(struct node));
    nn->data = d;
    nn->left = NULL;
    nn->right = NULL;
    return nn;
}
struct node * inserttree(struct node * r , int d){
    if(!r){
        return newnode(d);
    }
    if(d<=r->data){
        r->left = inserttree(r->left,d);
    }else{
        r->right = inserttree(r->right,d);
    }
    return r;
}
void inorder(struct node * r){
    if(r){
        inorder(r->left);
        printf("%d ",r->data);
        inorder(r->right);
    }
}
struct node * searchkey(struct node * r,int val){
    if(r){
        if(r->data == val){
            return r;
        }
        searchkey(r->left,val);
        searchkey(r->right,val);
        return r;
    }
}
struct node * searchabovekey(struct node * r , int val){
    if(r){
        if(r->left->data==val || r->right->data==val){
            return r;
        }
        searchabovekey(r->left,val);
        searchabovekey(r->right,val);
        return r;
    }
}
struct node * findinorderpredecessor(struct node * t){
    if(t){
    struct node * temp = t->left;
    while(t->right){
        t=t->right;
    }
    return t;
}

}
void delnode(struct node * r, int val){
    if(r){
    struct node * keynode = searchkey(r,val);
    struct node * abovekeynode = searchabovekey(r,val);

    //three cases 

    //first case two child present
    if(keynode->left!=NULL && keynode->right!=NULL){
        struct node * inopre = findinorderpredecessor(keynode);
        keynode->data = inopre->data;
        struct node * aboveinopre = searchabovekey(inopre,inopre->data);
        if(aboveinopre->left == inopre){
            aboveinopre->left = NULL;
            free(inopre);
            return;
        }
        if(aboveinopre->right == inopre){
            aboveinopre->right = NULL;
            free(inopre);
            return;
        }
    }else if(keynode->left == NULL && keynode->right == NULL){
        //second case no child present
        if(abovekeynode->left == keynode){
            abovekeynode->left = NULL;
            free(keynode);
            return;
        }
        if(abovekeynode->right == keynode){
            abovekeynode->right = NULL;
            free(keynode);
            return;
        }
    }else{
        //third case when only one child is present
        if(abovekeynode->left==keynode){
            if(keynode->left!=NULL){
                abovekeynode->left=keynode->left;
                free(keynode);
                return;
            }
            if(keynode->right!=NULL){
                abovekeynode->left=keynode->right;
                free(keynode);
                return;
            }
        }
        if(abovekeynode->right==keynode){
            if(keynode->left!=NULL){
                abovekeynode->right=keynode->left;
                free(keynode);
                return;
            }
            if(keynode->right!=NULL){
                abovekeynode->right=keynode->right;
                free(keynode);
                return ;
            }
        }
    }
  }
}

int main()
{
    printf("enter n : ");
    int n;
    scanf("%d",&n);
    int a[n];
    printf("\nenter the values :");
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    struct node * root = NULL;
    root=inserttree(root,a[0]);
    for(int i=1;i<n;i++){
        inserttree(root,a[i]);
    }
    printf("\ninorder is :\n");
    inorder(root);
    while(1){
        printf("\nwould you like to delete?\n1.yes\n2.no\n");
        int c;
        scanf("%d",&c);
        if(c==2){
            return 0;
        }
        if(c==1){
            printf("\nenter the data to delete : ");
            int d;
            scanf("%d",&d);
            delnode(root,d);
            printf("\ninorder is :\n");
            inorder(root);
            printf("\n");
        }
    }
    return 0;
}

1 Ответ

0 голосов
/ 27 сентября 2018

В функции searchabovekey при тестировании, если (node-> left-> data = val ..., левый или правый узел может быть нулевым, поэтому вы пытаетесь прочитать область нераспределенной памяти. Вы должны проверитьсначала, если node-> left и node-> right не равны нулю.

...