Итеративный способ удаления корневого узла двоичного дерева в c

Question

void Bst_DeleteStudent(struct BstStudent** root, char student_name[]){
    struct BstStudent* current = *root;
    struct BstStudent* parent = NULL;
    int flag = 0;
    int i;

    while(current != NULL){
        if(strcmp(current->name, student_name) > 0){
            parent = current;
            current = current->left;
        }
        else if(strcmp(current->name, student_name) < 0){
            parent = current;
            current = current->right;
        }
        else{
            flag = 1;
            //If node has no children
            if(current->left == NULL && current->right == NULL){
                if(parent->left == current){
                    parent->left = NULL;
                }
                else{
                    parent->right = NULL;
                }
                free(current);
                return;
            }
            //If current has one child
            else if((current->left == NULL && current->right != NULL) || (current->left != NULL && current->right == NULL)){
                //If node has a right child 
                if(current->right != NULL && current->left != NULL){
                    if(parent->right == current){
                        parent->right = current->right;
                    }
                    else if(parent->left == current){
                        parent->left = current->right;
                    }
                }
                //If node has a left child
                else if(current->left != NULL && current->right == NULL){
                    if(parent->right == current){
                        parent->right = current->left;
                    }
                    else if(parent->left == current){
                        parent->left = current->left;
                    }
                }
                free(current);
                return;
            }
            //If current has two children
            else{
                struct BstStudent* swap_this = current->right;
                struct BstStudent* swap_this_prev = current;

                while(swap_this->left != NULL){
                    swap_this_prev = swap_this;
                    swap_this = swap_this->left;
                }

                strcpy(current->name, swap_this->name);
                current->id = swap_this->id;
                for(i=0; i<5; i++){
                    current->marks[i] = swap_this->marks[i];
                }

                if(swap_this_prev->left == swap_this){
                    swap_this_prev->left = swap_this->right;
                }
                else if(swap_this_prev->right == swap_this){
                    swap_this_prev->right = swap_this->right;
                }
                free(swap_this);
                return;
            }
        }
    }
    if(flag == 1){
        printf("\nStudent named '%s' removed\n", student_name);
    }
    else{
        printf("\nNo student named '%s' is found in the list!\n", student_name);
    }
}

Привет, ребята, в настоящее время я хочу сделать функцию удаления для реализации бинарного дерева поиска, которая сортирует узлы по именам в алфавитном порядке. Мой код работает отлично, можно удалить большую часть времени. Код дает ошибку сегментации только в конкретном случае, когда я хочу удалить корневой узел, и у корневого узла есть только один дочерний элемент или его нет. Любое другое удаление работает. Ребята, не могли бы вы помочь мне?

Answer 1

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

struct BstStudent{
    char name[50];
    int id;
    float marks[5];
    struct BstStudent* left;
    struct BstStudent* right;
};

void Bst_IntroduceStudent(struct BstStudent** root, char student_name[], int student_id){
    struct BstStudent* new_student = (struct BstStudent*)malloc(sizeof(struct BstStudent));
    struct BstStudent* current = *root;
    struct BstStudent* previous = NULL;
    int i;

    strcpy(new_student->name, student_name);
    new_student->id = student_id;
    new_student->left = NULL;
    new_student->right = NULL;
    for(i=0; i<5; i++){
        new_student->marks[i] = 0;
    }

    //Check if the tree is empty
    if(*root == NULL){
        *root = new_student;
    }
    else{
    //If not empty, go through the tree until we find the right spot for the student
    while(current != NULL){
        if(strcmp(current->name, new_student->name) > 0){
            previous = current;
            current = current->left;
        }
        else if(strcmp(current->name, new_student->name) < 0){
            previous = current;
            current = current->right;
        }
        else if(strcmp(current->name, new_student->name) == 0){
            printf("\n** A student with that name already exists! **\n");
            free(new_student);
            return;
        }
    }
    //If we found the right node after which we want to place the student, decide if place right or left
    if(strcmp(previous->name, new_student->name) > 0){
        previous->left = new_student;
    }
    else{
        previous->right = new_student;
    }
}  
}

void Bst_DeleteStudent(struct BstStudent** root, char student_name[]){
    struct BstStudent* current = *root;
    struct BstStudent* parent = NULL;
    int flag = 0;
    int i;

    while(current != NULL){
        if(strcmp(current->name, student_name) > 0){
            parent = current;
            current = current->left;
        }
        else if(strcmp(current->name, student_name) < 0){
            parent = current;
            current = current->right;
        }
        else{
            flag = 1;
            //If node has no children
            if(current->left == NULL && current->right == NULL){
                if(parent->left == current){
                    parent->left = NULL;
                }
                else{
                    parent->right = NULL;
                }
                free(current);
                return;
            }
            //If current has one child
            else if((current->left == NULL && current->right != NULL) || (current->left != NULL && current->right == NULL)){
                //If node has a right child 
                if(current->right != NULL && current->left != NULL){
                    if(parent->right == current){
                        parent->right = current->right;
                    }
                    else if(parent->left == current){
                        parent->left = current->right;
                    }
                }
                //If node has a left child
                else if(current->left != NULL && current->right == NULL){
                    if(parent->right == current){
                        parent->right = current->left;
                    }
                    else if(parent->left == current){
                        parent->left = current->left;
                    }
                }
                free(current);
                return;
            }
            //If current has two children
            else{
                struct BstStudent* swap_this = current->right;
                struct BstStudent* swap_this_prev = current;

                while(swap_this->left != NULL){
                    swap_this_prev = swap_this;
                    swap_this = swap_this->left;
                }

                strcpy(current->name, swap_this->name);
                current->id = swap_this->id;
                for(i=0; i<5; i++){
                    current->marks[i] = swap_this->marks[i];
                }

                if(swap_this_prev->left == swap_this){
                    swap_this_prev->left = swap_this->right;
                }
                else if(swap_this_prev->right == swap_this){
                    swap_this_prev->right = swap_this->right;
                }
                free(swap_this);
                return;
            }
        }
    }
    if(flag == 1){
        printf("\nStudent named '%s' removed\n", student_name);
    }
    else{
        printf("\nNo student named '%s' is found in the list!\n",    student_name);
    }
}

void Bst_Marks(struct BstStudent *student){ 
    printf("Insert the student marks!\n");

    //Declaring variables for looping and inserting marks
    int i;
    float mark;

    //Loop through each module (element) in the marks array and inserting a mark
    for( i=0; i<5; i++){
        printf("Insert the mark for the %d module!\n",i+1);
        scanf("%f",&mark);
        student->marks[i] = mark;
    }
}

void Bst_IntroMarks(struct BstStudent* root, char student_name[]){
    struct BstStudent* current = root;
    int flag = 0;

    while(current != NULL){
        if(strcmp(current->name, student_name) > 0){
            current = current->left;
        }
        else if(strcmp(current->name, student_name) < 0){
            current = current->right;
        }
        else{
            Bst_Marks(current);
            flag = 1;
            break;
        }
    }
    if(flag == 0){
        printf("\nThere is no student named: %s\n", student_name);
    }  
}

void Bst_SearchPrint(struct BstStudent* root, char student_name[]){
    struct BstStudent* current = root;
    int i, flag = 0;

    while(current != NULL){
        if(strcmp(current->name, student_name) > 0){
            current = current->left;
        }
        else if(strcmp(current->name, student_name) < 0){
            current = current->right;
        }
        else{
            printf("\n----------------\n");
            printf("Name:   %s\n", current->name);
            printf("Student ID: %d\n", current->id);
            for(i=0; i<5; i++){
                printf("Module %d:   %f\n", i+1, current->marks[i]);
            }
            flag = 1;
            break;
        }
    }
    if(flag == 0){
        printf("\nThere is no student named: %s\n", student_name);
   }
}

void Bst_PrintAll(struct BstStudent** root){
    struct BstStudent* temp = *root;
    int i;

    if(temp == NULL){
        return;
    }
    else{
        Bst_PrintAll(&temp->left);
        printf("\n----------------\n");
        printf("Name:   %s\n", temp->name);
        printf("Student ID: %d\n", temp->id);
        for(i=0; i<5; i++){
            printf("Module %d:   %f\n", i+1, temp->marks[i]);
        }
        Bst_PrintAll(&temp->right);
    }
}

void leftRotateBinary(struct BstStudent** current){
    struct BstStudent* temp;
    struct BstStudent* original;
    struct BstStudent* right;

    if(*current == NULL || (*current)->right == NULL){
        return;
    }

    original = *current;
    right = original->right;

    temp = (struct BstStudent*)malloc(sizeof(struct BstStudent));
    int i;
    strcpy(temp->name, original->name);
    temp->id = original->id;
    for(i=0; i<5; i++){
        temp->marks[i] = original->marks[i];
    }

    strcpy(original->name,right->name);
    original->id = right->id;
    for(i=0; i<5; i++){
        original->marks[i] = right->marks[i];
    }    

    temp->right = right->left;
    temp->left = original->left;
    original->right = right->right;
    original->left = temp;

    free(right);
}

void rightRotateBinary(struct BstStudent** current){
    struct BstStudent* temp;
    struct BstStudent* original;
    struct BstStudent *left;

    if(*current == NULL || (*current)->left == NULL){
        return;
    }

    original = *current;
    left = original->left;

    temp = (struct BstStudent*)malloc(sizeof(struct BstStudent));
    int i;

    strcpy(temp->name, original->name);
    temp->id = original->id;
    for(i=0; i<5; i++){
        temp->marks[i] = original->marks[i];
    }

    strcpy(original->name, left->name);
    original->id = left->id;
    for(i=0; i<5; i++){
        original->marks[i] = left->marks[i];
    }

    temp->left = left->right;
    temp->right = original->right;
    original->left = left->left;
    original->right = temp;

    free(left);
}

void balanceBinary(struct BstStudent **root){
    struct BstStudent* current = *root;
    int expected, i, odd_node;
    int num_nodes = 0;

    while(current != NULL){
        while(current->left != NULL){
            rightRotateBinary(&current);
        }
        current = current->right;
        num_nodes++;
    } 

    expected = num_nodes - (pow(2,(floor(log2(num_nodes+1)))) - 1);
    current = *root;

    for(i=0; i<expected; i++){
        leftRotateBinary(&current);
        current = current->right;
    }

    current = *root;
    num_nodes = num_nodes - expected;
    odd_node = (num_nodes+1)/2;
    while(odd_node > 1){
        leftRotateBinary(&(*root));

        for(i=0; i<(odd_node-1); i++){
            leftRotateBinary(&(current->right));
            current = current->right;
        }
        odd_node = (odd_node+1)/2;
    }
}



int main(){
//Pointer to root node initially points to empty tree
struct BstStudent* rootPtr = NULL;

    int user_choice;
    char new_name[20], new_name2[20], marks_name[20], report_name[20], delete_name[20];
    int new_ID, new_ID2;

    //Keep displaying the menu until the user decides to quit the program
    do{
        //Main menu
        printf("\nManage data for students: (Type an option and press ENTER)\n");
        printf("1) Introduce new student:\n");
        printf("2) Remove student:\n");
        printf("3) Introduce marks for a student:\n");
        printf("4) Print report for a student:\n");
        printf("5) Print report for all students:\n");
        printf("6) Save to a file:\n");
        printf("7) Retrieve data from a file:\n");
        printf("8) Quit\n\n");

        //Ask the user to choose from the menu options above
        scanf("%d", &user_choice);

        switch(user_choice){
            case 1:
                //Ask the user for the name and ID of student he wants to introduce
                printf("Insert the name of new student: \n");
                scanf("%s", new_name);
                printf("Insert the id of new student: \n");
                scanf("%d", &new_ID);
                Bst_IntroduceStudent(&rootPtr, new_name, new_ID);
                balanceBinary(&rootPtr);
                break;
            case 2:
                printf("Insert the name of student you want to remove: \n");
                scanf("%s", delete_name);
                Bst_DeleteStudent(&rootPtr, delete_name);
                balanceBinary(&rootPtr);
                break;
            case 3:
                printf("Insert the ID of the student you want to introduce marks for!\n");
                scanf("%s", marks_name);
                //Insert the marks
                Bst_IntroMarks(rootPtr, marks_name);
                break;
                break;
            case 4:
                //Ask the user which student's report want to be printed
                printf("Insert the ID of the student you want to print a report!\n");
                scanf("%s", report_name);
                //Print the report for that student
                Bst_SearchPrint(rootPtr, report_name);
                break;
            case 5:
                printf("Print report of all students:\n\n");
                Bst_PrintAll(&rootPtr);
                break;
            case 6:
                break;
            case 7:
                break;
            case 8:
                //Quit the program
                printf("\nProgram ended!\n");
                return 0;
                default:
                break;
        }
    }
    while(user_choice!= 8);
return 0;
}

Вот весь мой код, я не хотел, чтобы он был очень длинным, но если это поможет вам, ребята, лучше понять, как мне помочь, я был бы очень рад

Answer 2

Вы пытаетесь получить доступ к левому / правому узлу NULL(родительского) в случае удаления корневого узла.

Добавьте условие перед доступом к parent, независимо от того, является ли parent значением NULL или нет, если parent не равен NULL, тогда присвойте значение только указателю его узла.

Например

if(parent != NULL) {
    if(parent->left == current){
        parent->left = NULL;
    }
    else{
        parent->right = NULL;
    }
}

Добавьте такое же условие и в другие части кода.