Блог

Ниже приведена программа, управляемая меню для различных операций в BST. Основная проблема, с которой я сталкиваюсь, заключается в том, что когда я запускаю бесплатную функцию в функции удаления, пожалуйста, помогите и обновите данную программу. Всякий раз, когда я пытаюсь удалить какой-либо узел после вставки, программа резко завершается. Я попытался выполнить отладку, но проблема все еще сохраняется.

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

struct btNode
{
    int data;
    struct btNode *right;
    struct btNode *left;
};

int found;
struct btNode *temp2;
struct btNode *create(int);
struct btNode *insert(struct btNode *, int);
void inorder(struct btNode *);
void preorder(struct btNode *);
void postorder(struct btNode *);
void delete (struct btNode *, int);

int main()
{
    int choice, item;
    struct btNode *root = NULL;

    do
    {
        printf("nChoose one of the options:n");
        printf("1. Insert 2. Delete 3. Inorder 4. Postorder 5. Preorder 6. Exitn");
        scanf("%d", amp;choice);

        switch (choice)
        {
        case 1:
            printf("nEnter any number to insert:");
            scanf("%d", amp;item);
            root = insert(root, item);
            break;

        case 2:
            printf("nEnter any number to delete:");
            scanf("%d", amp;item);
            delete(root, item);
            break;

        case 3:
            inorder(root);
            break;

        case 4:
            postorder(root);
            break;

        case 5:
            preorder(root);
            break;

        case 6:
            break;

        default:
            printf("nWRONG INPUT");
        }
    } while (choice != 6);

    return 0;
}

struct btNode *create(int num)
{
    struct btNode *temp1 = (struct btNode *)malloc(sizeof(struct btNode));
    temp1->data = num;
    temp1->left = NULL;
    temp1->right = NULL;
    return temp1;
}

struct btNode *search(struct btNode *root, int num)
{
    struct btNode *temp1 = root;

    while (temp1 != NULL)
    {
        if (temp1->data == num)
        {
            found = 1;
            return temp1;
        }

        else
        {
            if (temp1->data >= num)
            {
                temp2 = temp1;
                temp1 = temp1->left;
            }

            else
            {
                temp2 = temp1;
                temp1 = temp1->right;
            }
        }
    }
    found = 0;
}

struct btNode *insert(struct btNode *root, int num)
{
    struct btNode *temp1 = create(num);
    if (root == NULL)
    {
        root = temp1;
        printf("%d insertedn", root->data);
    }
    else
    {
        temp2 = root;
        while (temp2 != NULL)
        {
            if (temp2->data >= num)
            {
                if (temp2->left)
                {
                    temp2 = temp2->left;
                }
                else
                {
                    temp2->left = temp1;
                    printf("%d insertedn", temp2->left->data);
                    break;
                }
            }

            else
            {
                if (temp2->right)
                {
                    temp2 = temp2->right;
                }

                else
                {
                    temp2->right = temp1;
                    printf("%d insertedn", temp2->right->data);
                    break;
                }
            }
        }
    }
    return root;
}

void delete (struct btNode *root, int num)
{
    struct btNode *temp1 = search(root, num);
    if (found == 0)
    {
        printf("element not found");
        return;
    }

    else
    {
        if (temp1->left == NULL amp;amp; temp1->right == NULL)
        {
            free(temp1);
        }

        if (temp1->left != NULL amp;amp; temp1->right == NULL)
        {
            if (temp2->left = temp1)
            {
                temp2->left = temp1->left;
                free(temp1);
            }

            if (temp2->right = temp1)
            {
                temp2->right = temp1->left;
                free(temp1);
            }
        }

        if (temp1->left == NULL amp;amp; temp1->right != NULL)
        {
            if (temp2->left = temp1)
            {
                temp2->left = temp1->right;
                free(temp1);
            }

            if (temp2->right = temp1)
            {
                temp2->right = temp1->right;
                free(temp1);
            }
        }

        if (temp1->left != NULL amp;amp; temp1->right != NULL)
        {
            struct btNode *node1 = temp1;
            struct btNode *node2 = temp1->right;

            while (node2->left != NULL)
            {
                node1 = node2;
                node2 = node2->left;
            }
            temp1->data = node2->data;
            temp1 = node2;
            free(temp1);
        }
    }
}

void inorder(struct btNode *r)
{
    if (r == NULL)
    {
        printf("Tree is empty");
        return;
    }

    else
    {
        if (r->left)
            inorder(r->left);
        printf("%d ", r->data);
        if (r->right)
            inorder(r->right);
    }
}

void preorder(struct btNode *r)
{
    if (r == NULL)
    {
        printf("Tree is empty");
        return;
    }

    else
    {
        printf("%d ", r->data);
        if (r->left)
            preorder(r->left);
        if (r->right)
            preorder(r->right);
    }
}

void postorder(struct btNode *r)
{
    if (r == NULL)
    {
        printf("Tree is empty");
        return;
    }

    else
    {
        if (r->left)
            postorder(r->left);
        if (r->right)
            postorder(r->right);
        printf("%d ", r->data);
    }
}
 

В вашей delete() функции есть ошибки на нескольких уровнях. Среди этих:

• общий API: удаление может изменить корневой узел дерева, но вы не предусмотрели этого. Как минимум удаление изменяет корневой узел, когда удаляется единственный узел дерева с одним узлом, но при таком подходе, как ваш, корневой узел будет меняться всякий раз, когда вы удаляете содержащееся в нем значение.
• Недостаток реализации: аналогично, когда вы выполняете поиск и обнаруживаете целевое значение в корневом узле, вы не задаете (очень плохо названную) temp2 переменную области действия файла. Когда этот поиск выполняется в контексте удаления, это может привести либо delete() к попытке разыменования нулевого указателя, либо к повреждению дерева путем изменения случайного узла, как если бы он был родительским на целевом узле.
• Недостаток реализации: когда вы удаляете конечный узел (кроме корневого), вам необходимо установить указатель его родителя на него NULL .
• Плохой код: у вас есть несколько if утверждений, delete() которые используются = там, где они означают == .
• Плохой стиль: не полагайтесь на глобальные переменные ( temp2 , found ). Если вы хотите, чтобы ваши функции возвращали несколько значений, то либо используйте структуры, либо наделяйте функции параметрами.