时间戳

首页 > 解决方案 > 删除二叉搜索树中的节点会引发错误

c - 删除二叉搜索树中的节点会引发错误

问题描述

专家，这是我在二叉搜索树中创建和删除节点的代码。它可以正常插入，但在尝试删除节点时（调用 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");
        }
    }
}

标签： cbinary-search-treecoredump

解决方案

您必须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为空，这也会导致下一个，这会导致段错误。

另外：nullptr如果可以使用 C++11，请使用。

推荐阅读