Я не понимаю, как избавиться от ошибки здесь

Question

#include <iostream>

using namespace std;

class Node {
public:
    int data;
    Node *left, *right;
    Node()
    {
        data = NULL;
        left = right = NULL;
    }
};

Node* insertBST(Node* root, int value)
{
    if (root == NULL) {
        root->data = value;
        root->left = root->right = NULL;
    }
    if ((root->data) > value)
        insertBST(root->left, value);
    if ((root->data) < value)
        insertBST(root->right, value);
}

Node* printBST(Node* root)
{
    if (root != NULL) {
        printBST(root->left);
        cout << "\n" << root->data;
        printBST(root->right);
    }
}

int main()
{
    Node* root = new Node;
    insertBST(root, 30);
    insertBST(root, 20);
    insertBST(root, 40);
    insertBST(root, 70);
    insertBST(root, 60);
    insertBST(root, 80);
    printBST(root);
}

Выше приведен код, который я написал для реализации Binary Search Tree. Когда я его выполняю, программа перестает отвечать и закрывается. Я пытался получить помощь от pythontutor.com, но я не в состоянии справиться с этим. Что я должен сделать, чтобы он работал без ошибок? вот где он останавливается: Нажмите, чтобы увидеть

Любая помощь приветствуется, я новичок в написании программы.

Answer 1

В insertBST в случае root == NULL вы не создаете новый узел и не пытаетесь изменить содержимое root, поскольку это значение равно нулю, что должно привести к нарушению доступа или ошибке сегментации.

Я думаю, что причина того, что ваша программа зависает, а не падает, в том, что вы используете онлайн-компилятор, который игнорирует недопустимые записи и вместо этого позволяет программе продолжаться.Тогда это, возможно, заканчивается бесконечной рекурсией через функцию insertBST.

Чтобы исправить это, вам нужно выделить новый узел, один из способов будет следующим:

void insertBST(Node*& root, int value)
{
    if (root == NULL) {
        root = new Node();
        root->data = value;
        root->left = root->right = NULL;
    }
    if ((root->data) > value)
        insertBST(root->left, value);
    if ((root->data) < value)
        insertBST(root->right, value);
}

Обратите внимание, чтоВаша программа пропускает все узлы, которые она выделяет.Вы должны написать деструктор в Node, который удалит все дочерние узлы и вызвать delete root в конце вашей программы.В качестве альтернативы вообще не используйте необработанные указатели и вместо этого используйте std::shared_ptr или std::unique_ptr.