У меня проблемы с функцией вставки для моего бинарного дерева поиска

Question

По сути, в моей функции вставки происходит то, что часть, которая вызывает размещение узла справа от корня в моем bst, вызывает сбой программы, и я понятия не имею, почему. Функция вставки заключается в следующем.

node* insert(node *root, node *element)
{

    // Inserting into an empty tree.
    if (root == NULL)
        return element;
    else {

        // element should be inserted to the right.
        if (element->bk->key < root->bk->key) {

            printf("Inserting in left position.\n");
            // There is a right subtree to insert the node.
            if (root->left != NULL)
                root->left = insert(root->left, element);

            // Place the node directly to the right of root.
            else
                root->left = element;
        }

        // element should be inserted to the left.
        else {

            // There is a left subtree to insert the node.
            if (root->right != NULL)
                root->right = insert(root->right, element);

            // Place the node directly to the left of root.
            else
                root->right = element;
        }

        // Return the root pointer of the updated tree.
        return root;
    }
}

Answer 1

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

1. element не указывает на действительный экземпляр node (неинициализированный указатель, висячий указатель и т. Д.).
2. element->bk имеет значение NULL или недопустимый указатель.
3. element->left не равно NULL при входе в функцию.
4. element->right не равно NULL при входе в функцию.

Кстати, функция намного сложнее, чем должна быть:

node* insert(node *root, node *element) {
    if (root == NULL)
        return element; // Inserting into an empty tree.
    else {
        if (element->bk->key < root->bk->key) {
            printf("Inserting in left position.\n");
            root->left = insert(root->left, element);
        } else {
            printf("Inserting in right position.\n");
            root->right = insert(root->right, element);
        }
        // Return the root pointer of the updated tree.
        return root;
    }
}

Обратите внимание, что два оператора if (root->X != NULL) и два предложения else не нужны. Вызов функции с помощью root==NULL будет делать правильно, благодаря проверке if (root==NULL) вверху.

Answer 2

Лучшим кандидатом на аварию будет

if (element->bk->key < root->bk->key)

Так что либо element->bk или root->bk равны NULL, либо указывают на никуда.

Answer 3

Шаги отладки, которые я бы предпринял:

1. запустить в отладчике
2. в противном случае распечатайте все, прежде чем использовать его, используя fflush (stdout) между ними, чтобы, если вы не получили отпечаток, вы знали, что этот фрагмент плохо инициализирован.
3. Я бы исправил ваши комментарии так, чтобы они действительно отражали то, что вы делаете (справа и слева в обратном направлении в комментариях), чтобы когда вы устали / расстроились, вы не запутались.
4. Как сказал aix, упрощают, что может решить ваши проблемы (хотя, вероятно, нет) или, по крайней мере, немного упростить переход в отладчике, подумать и прочитать.

Как уже упоминалось, если вы дадите нам вызов / инициализацию, мы можем помочь больше.