Удаление узла в бинарном дереве поиска вызывает ошибку - PullRequest
Новая
       12

Удаление узла в бинарном дереве поиска вызывает ошибку

0 голосов
/ 09 февраля 2019

Эксперты, это мой код создания и удаления узлов в бинарном дереве поиска.Он хорошо работает для вставки, но выдает ошибку сегментации (ядро сбрасывается) при попытке удалить узел (при вызове функции deleteNode ()).Я не понимаю, в чем на самом деле проблема.
Пожалуйста, помогите!Заранее спасибо! 

#include <stdio.h>
#include <stdlib.h>
int size = 0;
typedef struct mylist{
    int data;
    struct mylist *left;
    struct mylist *right;
}node;
node *root;
void create_root(node *root){
    root = NULL;
}
//Inserting nodes
node* insert(node *root, int val){
    node *ptr, *parentptr, *nodeptr;
    ptr = (node*)malloc(sizeof(node));
    ptr -> data = val;
    ptr -> left = NULL;
    ptr -> right = NULL;
    if(root == NULL)
    root = ptr;
    else{
        parentptr = NULL;
        nodeptr = root;
        while(nodeptr != NULL){
            parentptr=nodeptr;
            if(val < nodeptr -> data)
                nodeptr = nodeptr -> left;
            else
            nodeptr = nodeptr -> right;
        }
        if(val < parentptr -> data)
            parentptr -> left = ptr;
        else
            parentptr -> right = ptr;
    }
    return root;
}

node* minValueNode(node* root) 
{ 
    node* cur = root; 

    while (cur->left != NULL) 
        cur = cur->left; 

    return cur; 
} 

node* deleteNode(node* root, int key) 
{ 
    if (root == NULL){ 
        printf("\nValue not found\n");
    }
    if (key < root-> data)
        root->left = deleteNode(root->left, key); 
    else if (key > root-> data) 
        root->right = deleteNode(root->right, key); 
    else
    { 
        if (root->left == NULL) 
        { 
            node *temp = root->right; 
            free(root);
            return temp; 
        } 
        else if (root->right == NULL) 
        { 
            node *temp = root->left; 
            free(root);
            return temp;  
        } 
        node* temp = minValueNode(root->right);  //Inorder successor
        root->data = temp->data; 
        root->right = deleteNode(root->right, temp->data); 
    }
    return root;
}

void main(){
    int option, val;
    node *ptr;
    int flag = 1;
    create_root(root);
    while(flag != 2){
        printf("\nChoose-\n1-Insert\n2-Delete\n3-Exit\n");
        scanf("%d", &option);
        switch(option){
        case 1:{
            printf("\nEnter the value of new node\n");
            size++;
            scanf("%d", &val);
            root = insert(root, val);
            break;
        }
        case 2:{
            int k;
            printf("Enter the value to delete");
            scanf("%d",&k);
            root=deleteNode(root, k);
            size--;
            break;
        }
        case 3:
            flag=2;
            break;
        default:
            printf("\nWrong entry\n");
        }
    }
}

1 Ответ

0 голосов
/ 09 февраля 2019

Вы должны либо вернуть NULL в первом if() в deleteNode(), либо вы должны поставить else перед вторым if()

node* deleteNode(node* root, int key) 
{ 
    if (root == NULL){ 
        printf("\nValue not found\n");
        return NULL; // <== This was missing.
    }
    ...
}

или в качестве альтернативы (возможно, предполагалось?): 

node* deleteNode(node* root, int key) 
{ 
    if (root == NULL){ 
        printf("\nValue not found\n");
    }
    else if(key < root->data)        
    ...
}

В настоящий момент это переходит к следующему if(key < root->data), даже если root равно нулю, что приводит к segfault.

Также: используйте nullptr, если выможно использовать C ++ 11.

...