Нарушение доступа для чтения. Язык Си
Проблема, которую я изложу ниже появилась у меня при попытках написать код дерева двоичного поиска. Весь код я по возможности описал комментариями.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <time.h>
typedef struct treeNode
{
struct treeNode* left;
int data;
struct treeNode* right;
} TREENODE;
//ПРЯМОЙ ОБХОД ЭЕЛЕМЕНТОВ
void preOrder(TREENODE* tree)
{
if (tree != NULL)
{
printf("%3d ", tree->data);
preOrder(tree->left);
preOrder(tree->right);
}
}
//ПОИСК УЗЛА ПО ЕГО МЕТКЕ В ДДП
TREENODE* searchNode(TREENODE* tree, int value)
{
TREENODE* q = tree;/*указатель на текущий узел*/
/*цикл поиска узла*/
while (q != NULL)
{
if (q->data == value)
break;/*нашли узел и выходим из цикла*/
else
{
if (value < q->data)/*если число меньше, нужно двигаться влево*/
q = q->left;
else /*если число больше, нужно двигаться вправо*/
q = q->right;
}
}
/*вышли из цикла поиска элемента*/
if (q == NULL)
{
puts("Not founded!");
return NULL; /*узел не найден */
}
puts("Founded!");
return q;/*узел найден */
}
//ВСТАВКА НОВОГО УЗЛА В ДДП
TREENODE* insertNode(TREENODE* tree, int value)
{
TREENODE* newNode = (TREENODE*)malloc(sizeof(TREENODE));
TREENODE* root = tree;
if (newNode != NULL)
{
/*создали узел дерева*/
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
}
else
{
puts("Error!");
}
if (root == NULL) /*пустое дерево*/
return newNode;/*новый узел становиться корнем дерева*/
while (root != NULL)
{
/*вставка в дерево*/
if (value < root->data)
{ /*если число меньше, нужно двигаться влево*/
if (root->left != NULL)
root = root->left;
else
{
root->left = newNode;
break;
}
}
else if (value > root->data)
{
/*если число больше, нужно двигаться вправо*/
if (root->right != NULL)
root = root->right;
else
{
root->right = newNode;
break;
}
}
else
{
puts("Clone");
break;
}
}
return tree;
}
//УДАЛЕНИЕ УЗЛА ИЗ ДДП
TREENODE* deleteNode(TREENODE* tree, int value)
{
TREENODE* q = tree;/*указатель на текущий узел*/
TREENODE* parent = NULL;/*указатель на родителя*/
TREENODE* s1, * s2, * s;/*указатели на сыновей*/
TREENODE* max_node;/*указатель для поиска максимального элемента в правом поддереве*/
int tmp;
/*цикл поиска удаляемого узла*/
while (q != NULL)
{
if (q->data == value)
break;/*нашли узел и выходим из цикла*/
else
{
parent = q;/*текущий узел это отец для следующего*/
if (value < q->data)/*если число меньше, нужно двигаться влево*/
q = q->left;
else /*если число больше, нужно двигаться вправо*/
q = q->right;
}
}
/*вышли из цикла поиска элемента*/
if (q == NULL)
{
puts("Not founded!");
return tree; /*узел не найден и возвращаем указатель на дерево*/
}
s1 = q->left;
s2 = q->right;
if (s1 == NULL && s2 == NULL)/*если удаляемый узел лист*/
{
if (parent != NULL)/*не корень дерева*/
{
/*обнуляем у отца ссылку на удаляемый узел*/
if (parent->left == q)
parent->left = NULL;
else parent->right = NULL;
}
else/*удаление корня дерева*/
{
free(q);
return NULL;/*дерево пустое*/
}
}
else if (s1 == NULL || s2 == NULL)/*если только один сын у удаляемого узла*/
{
s = (s1 == NULL) ? s2 : s1;/*находим сына*/
if (parent != NULL)/*не корень дерева*/
{
/*обнуляем у отца ссылку на удаляемый узел*/
if (parent->left == q)
parent->left = s;
else parent->right = s;
}
else/*удаление корня дерева*/
{
free(q);
return s;/*новый корень дерева*/
}
}
else/*удаление узла у которого два сына*/
{
/*удаление происходит замещением*/
/*ищем в левом поддереве самый правый узел
- он является самым максимальным из всех узлов правого поддерева
- для замены удаляемого узла*/
max_node = q->left;
while (max_node->right != NULL)
{
max_node = max_node->right;
}
tmp = max_node->data;/*копируем значение максимального узла из правого поддерева*/
tree = deleteNode(tree, tmp);/*удалим замещающий узел*/
q->data = tmp;/*копируем значение максимального узла из правого поддерева в удаляемый*/
return tree;
}
free(q);
return tree;
}
int main() {
setlocale(LC_ALL, "Russian");
int a, b, c;
char key;
struct TREENODE tree;
while (1) {
system("cls");
puts("1 - Добавление нового узла.");
puts("2 - Удаление узла.");
puts("3 - Поиск узла.");
puts("4 - Вывод элементов.");
puts("Для выхда нажмите ESC...");
key = getchar();
switch (key) {
case '1':
puts("Введите число.");
scanf("%d", &a);
insertNode(&tree, a);
break;
case '2':
puts("Выберите число для удаления.");
scanf("%d", &b);
deleteNode(&tree, b);
break;
case '3':
puts("Выберите элемент для поиска.");
scanf("%d", &c);
searchNode(&tree, c);
break;
case '4':
preOrder(&tree);
break;
case 27:
puts("Выход.");
exit(0);
break;
}
}
return 0;
}
Ошибка компиляции на VS Code или на онлайн компиляторах заключается в том, как я понимаю, что в переменной root хранится какой-то мусор, так как при сравнении root с null выдает ошибку: "Вызвано исключение: нарушение доступа для чтения. root было 0xCCCCCCCC." Например, в строке if (value < root->data) в функции прямого обхода элементов вылазит данная ошибка. Самое интересное, что на QT Creator эта программа работает без каких либо проблем, исключений и ошибок. Я попробовал решить данную проблему, путем замены NULL значением 0xCCCCCCCC, и это вроде как работает, но это не точно.
Например я заменил вот так:
//ВСТАВКА НОВОГО УЗЛА В ДДП
TREENODE* insertNode(TREENODE* tree, int value)
{
TREENODE* newNode = (TREENODE*)malloc(sizeof(TREENODE));
TREENODE* root = tree;
if (newNode != NULL)
{
/*создали узел дерева*/
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
}
else
{
puts("Error!");
}
if (root == 0xCCCCCCCC) /*пустое дерево*/
return newNode;/*новый узел становиться корнем дерева*/
while (root != 0xCCCCCCCC)
{
/*вставка в дерево*/
if (value < root->data)
{ /*если число меньше, нужно двигаться влево*/
if (root->left != 0xCCCCCCCC)
root = root->left;
else
{
root->left = newNode;
break;
}
}
else if (value > root->data)
{
/*если число больше, нужно двигаться вправо*/
if (root->right != 0xCCCCCCCC)
root = root->right;
else
{
root->right = newNode;
break;
}
}
else
{
puts("Clone");
break;
}
}
return tree;
}
Подскажите пожалуйста, что я не так сделал, или что я не понимаю правильно. Скриншот с примером одной ошибки прилагается.
