i know that people already posted many errors like this one, but i really don't know what's wrong on my code. I'm coding a binary search Tree, and i have the following Error in the insertion function: 0xC0000005: violation access while reading location 0x0000000000000000. thats my data structure: Obs: this error only happens on Visual Studio, i already compiled and executed it on different IDES such as CodeBlocks and Dev-Cpp with different compilers, and even with the same compiler as Visual Studio and i didn't get this error.
typedef struct INFO{
int value;
}info;
typedef struct key {
info* info;
struct key* left;
struct key* right;
}key;
thats the following function:
int insertBST(key** bst, info info) {
int insert = 0;
key* newKey = createKey(info);
if (!(*bst)) {
*bst = newKey;
return 1;
}
if ((*bst)->info->value < newKey->info->value) insert = insertBST(&((*bst)->right), info); //The erros happens in this line
if ((*bst)->info->value > newKey->info->value) insert = insertBST(&((*bst)->left), info);
return insert;
}
i call the Function on my main in the folowing way:
case 1:
puts("Informe um valor:");
scanf_s("%i", &(info.value));
printf("insercao: %i\n", insertBST(&bst, info));
break;
wich is inside of a switch that's also inside of a do while loop.
c File:
#include "BST.h"
info* createInfoKey(int value) {
info* newInfo = (info*)calloc(1, sizeof(info));
if (!newInfo) return newInfo;
newInfo->value = value;
}
key* createKey(info inf) {
key* newKey = (key*)calloc(1, sizeof(key));
if (!newKey) return newKey;
newKey->info = createInfoKey(inf.value);
newKey->left = NULL;
newKey->right = NULL;
if (!newKey->info) return newKey;
newKey->info->value = inf.value;
return newKey;
}
key* leftBST(key* key) {
return key->left;
}
key* rightBST(key* key) {
return key->right;
}
void listPreOrder(key* bst, node** first, node** last) {
if (!bst) return;
if (bst) {
*first = insertE(bst->info->value , *first, last);
}
listPreOrder(bst->left, first, last);
listPreOrder(bst->right, first, last);
}
key* rebuildTree(node** preListFirst, node* inListFirst, node** preListLast, node** inListLast) {
if(!(*preListFirst)) return NULL;
if(!(*preListFirst) && !inListFirst) return NULL;
node* aux = inListFirst, * aux2 = NULL;
info inf;
inf.value = (*preListFirst)->info->value;
key* newKey = createKey(inf);
if(inListFirst && inListFirst->info->value == (*preListFirst)->info->value){
(*preListFirst) = (*preListFirst)->next;
return newKey;
}
if (aux)
if (aux->next)
while (aux->next->info->value != (*preListFirst)->info->value) {
aux = aux->next;
}
(*preListFirst) = (*preListFirst)->next;
aux2 = aux->next;
if(aux2) if(aux2->next) aux2 = aux2->next;
aux->next = NULL;
newKey->left = rebuildTree(preListFirst, inListFirst, preListLast, inListLast);
newKey->right = rebuildTree(preListFirst,aux2, preListLast, inListLast);
return newKey;
}
void listInOrder(key* bst, node** first, node** last) {
if (!bst) return;
listInOrder(bst->left, first, last);
if (bst) {
*first = insertE(bst->info->value, *first, last);
}
listInOrder(bst->right, first, last);
}
void listPosOrder(key* bst, node** first, node** last) {
if (!bst) return;
listPosOrder(bst->left, first, last);
listPosOrder(bst->right, first, last);
if (bst) {
*first = insertE(bst->info->value, *first, last);
}
}
void printPreOrder(key* bst) {
if (!bst) return;
printf("[%i] \n", bst->info->value);
printPreOrder(bst->left);
printPreOrder(bst->right);
}
int nFolhas(key* bst) {
static int i=0;
if (!bst) return 0;
if(!bst->right && !bst->left) i++;
nFolhas(bst->left);
nFolhas(bst->right);
return i;
}
void printInOrder(key* bst) {
if (!bst) return;
printInOrder(bst->left);
printf("[%i] \n", bst->info->value);
printInOrder(bst->right);
}
void printPosOrder(key* bst) {
if (!bst) return;
printPosOrder(bst->left);
printPosOrder(bst->right);
printf("[%i] \n", bst->info->value);
}
int insertBST(key** bst, info info) {
int insert = 0;
key** bst2;
key* newKey = createKey(info);
if (!(*bst)) {
*bst = newKey;
return 1;
}
if ((*bst)->info->value < newKey->info->value) {
bst2 = &((*bst)->right);
insert = insertBST(bst2, info);
}
if ((*bst)->info->value > newKey->info->value) {
bst2 = &((*bst)->left);
insert = insertBST(bst2, info);
}
return insert;
}
key* searchBST(key* bst, info info) {
if (!bst) return NULL;
if (bst->info->value == info.value) return bst;
if (bst->info->value < info.value) return searchBST(bst->right, info);
if (bst->info->value > info.value) return searchBST(bst->left, info);
}
int searchBSTFather(key* bst, info info, key** father) {
if (!bst) return -1;
if (bst->info->value == info.value) return 0;
if (!bst->left && !bst->right) return 0;
if (bst->right && bst->right->info->value == info.value) {
*father = bst;
return 1;//1 = filho a direita
}
if (bst->left && bst->left->info->value == info.value) {
*father = bst;
return 2;// 2 = filho a esquerda
}
if (bst->info->value < info.value) return searchBSTFather(bst->right, info, father);
if (bst->info->value > info.value) return searchBSTFather(bst->left, info, father);
}
key* smaller(key* bst) {
if (!bst) return NULL;
if (!bst->left) return bst;
if (bst->left) return smaller(bst->left);
}
key* larger(key* bst) {
if (!bst) return NULL;
if (!bst->right) return bst;
if (bst->right) return smaller(bst->left);
}
int heightBST(key* bst) {
int height = 0, left = 0, right = 0;
if (!bst) return 0;
left = 1 + heightBST(bst->left);
right = 1 + heightBST(bst->right);
height = left > right ? left : right;
return height;
}
key* removeCurrent(key* bst, key* current) {
key* aux, * aux2;
aux = current;
//Os casos de remocao dessa implementacao trabalham juntos.
if (!aux->left) {
aux2 = current->right;
free(aux);
return aux2;
}
aux2 = current->left;
if (aux2)
while (aux2->right) {
aux = aux2;
aux2 = aux2->right;
}
if (aux != current) {
aux->right = aux2->left;
aux2->left = current->left;
}
if (aux2) aux2->right = current->right;
free(current);
return aux2;
}
int removeBST(key** bst, info info) {
key* father = NULL, * current = (*bst), * subTree = NULL;
int side;
if (!(*bst)) return 0;
side = searchBSTFather((*bst), info, &father);
if (side == -1) return 0;
if (side == 1) if (father) current = father->right;
if (side == 2) if (father) current = father->left;
subTree = removeCurrent((*bst), current);
if (side && father) { //Se o pai nao existir significa que a arvore possui apenas um no, que e a propria raiz
if (side == 2) father->left = subTree;
else father->right = subTree;
}
else (*bst) = subTree;
return 1;
}
void printBST(key* bst) {
if (!bst) {
return;
}
printf("[%i] ", bst->info->value);
printBST(bst->left);
printBST(bst->right);
}
Header File:
#ifndef BST_H
#define BST_H
#include <stdio.h>
#include <stdlib.h>
#include "ListaCircular.h"
#include <stdbool.h>
typedef struct key {
info* info;
struct key* left;
struct key* right;
}key;
info* createInfoKey(int value);
key* createKey(info inf);
key* leftBST(key* key);
key* rightBST(key* key);
void listPreOrder(key* bst, node** first, node** last);
void listInOrder(key* bst, node** first, node** last);
void listPosOrder(key* bst, node** first, node** last);
key* rebuildTree(node** preListFirst, node* inListFirst, node** preListLast, node** inListLast);
void printBST(key* bst);
void printPreOrder(key* bst);
void printInOrder(key* bst);
void printPosOrder(key* bst);
int insertBST(key** bst, info info);
key* searchBST(key* bst, info info);
int searchBSTFather(key* bst, info info, key** father);
key* smaller(key* bst);
key* larger(key* bst);
int heightBST(key* bst);
key* removeCurrent(key* bst, key* current);
int removeBST(key** bst, info info);
#endif
Main File:
#include "BST.h"
int main() {
int op, side = 0;
bool result;
key* bst = NULL, * aux = NULL, * father = NULL;
node *first = NULL, *last = NULL, *first2 = NULL, *last2 = NULL;
info info;
puts("1-Inserir\n2-Remover\n3-Imprimir\n4-Buscar\n\n5-Altura\n6-Buscar menor chave\n7-Buscar Pai\n8-Remover atual");
puts("9-Criar lista a partir de um percurso");
do {
scanf_s("%i", &op);
switch (op) {
case 1:
puts("Informe um valor:");
scanf_s("%i", &(info.value));
printf("insercao: %i\n", insertBST(&bst, info));
break;
case 2:
puts("Informe um valor:");
scanf_s("%i", &(info.value));
if (removeBST(&bst, info)) puts("Remocao bem sucedida");
else puts("Erro na remocao");
break;
case 3:
printBST(bst);
break;
case 4:
puts("Informe um valor:");
scanf_s("%i", &(info.value));
if (searchBST(bst, info)) puts("chave encontrada");
else puts("chave nao encontrada");
break;
case 5:
op = heightBST(bst) + 1;
printf("altura: %i\n", op - 1);
case 6:
aux = smaller(bst);
if (aux) if (aux->info) printf("%i\n", aux->info->value);
break;
case 7:
puts("Informe um valor:");
scanf_s("%i", &(info.value));
side = searchBSTFather(bst, info, &father);
if (father) printf("Pai: %i\n", father->info->value);
printf("side: %i\n", side);
break;
case 8:
puts("Informe um valor:");
scanf_s("%i", &(info.value));
aux = searchBST(bst, info);
aux = removeCurrent(bst, aux);
if (aux) printf("AUX: %i\n", aux->info->value);
else puts("aux nao existe");
break;
case 9:
puts("1-PreOrdem\n2-InOrdem\n3-PosOrdem");
scanf_s("%i", &op);
if (op == 1) {
listPreOrder(bst, &first, &last);
puts("Lista pre Ordem:");
print(first);
}
if (op == 2) {
listInOrder(bst, &first2, &last2);
puts("Lista em Ordem:");
print(first2);
}
if (op == 3) {
listPosOrder(bst, &first2, &last2);
puts("Lista em Ordem:");
print(first2);
}
break;
}
} while (op);
return 0;
}
thanks, i've found the problem, it seems i forged to return the alocated info in the following function:
info* createInfoKey(int value) {
info* newInfo = (info*)calloc(1, sizeof(info));
if (!newInfo) return newInfo;
newInfo->value = value;
}
it should be like this :
info* createInfoKey(int value) {
info* newInfo = (info*)calloc(1, sizeof(info));
if (!newInfo) return newInfo;
newInfo->value = value;
return newInfo;
}
thanks again.
User contributions licensed under CC BY-SA 3.0