I have an exercise to do and I submit it to an automatic corrector (Sharif), in my tests all the cases work, but in the broker I am getting a Runtime Error, I have already reviewed this code many times and I do not think the error. (Exaggerated detail is due to the fact of trying to find the error)
Problem
Main
#include<stdio.h>#include<stdlib.h>#include"operations.h"
int main (){
int num;
char buffer;
treeNode * arvore = NULL;
while(1){
// Lê a operação
scanf("%c",&buffer);
// Vê se deseja sair
if(buffer == 'S') break;
// Verifica as operações
if(buffer == 'I'){ // Inserção
//Lê o número para inserir
scanf("%d",&num);
// Insere o número na árvore
insert(&arvore,num);
}else if(buffer == 'R'){ //Remoção
//Lê o número para remoção
scanf("%d",&num);
// Deleta o nó
deleteNode(&arvore,num);
}else if (buffer == 'M'){ //Mostra árvore
inOrd(&arvore);
printf("\n");
}
}
}
Operations library
#ifndef OPERATIONS
#define OPERATIONS
#include <stdio.h>
#include <stdlib.h>
struct TreeNode{
int data;
struct TreeNode * esq;
struct TreeNode * dir;
};
//Definição dos dados
typedef struct TreeNode treeNode;
typedef struct TreeNode ** root;
//Definição das funções
treeNode * createNode();
void inOrd(root Tree);
void insert(root Tree,int data);
void deleteNode(root Tree,int data);
treeNode * pai(root Tree, int data);
treeNode * busca(root Tree,int data);
treeNode * maisDireita(root Tree);
//Implementação das funções
treeNode * createNode(){
treeNode * newNode;
newNode = (treeNode*) malloc(sizeof(treeNode));
newNode->data = 0;
return newNode;
}
void inOrd(root Tree){
if(*Tree == NULL) return;
inOrd(&((*Tree)->esq));
printf("%d ",(*Tree)->data);
inOrd(&((*Tree)->dir));
}
void insert(root Tree,int data){
// Caso a raiz da árvore seja nula
if((*Tree) == NULL){
// Cria o nó para ser adicionado a árvore
treeNode * newNode = createNode();
// Copia o dado para o nó criado
newNode->data = data;
// Coloca esse novo nó na raiz da árvore
(*Tree) = newNode;
return;
}
// Caso o dado a ser inserido seja menor que o dado atual da árvore
if(data < (*Tree)->data)
insert(&((*Tree)->esq),data);
// Caso o dado a ser inserido seja maior que o dado atual da árvore
else
insert(&((*Tree)->dir),data);
}
void deleteNode(root Tree,int data){
/*****************************************
* Temos três casos para se deletar um nó:*
* 1 - Se o nó é uma folha. *
* 2 - Se o nó tem somente um filho. *
* 3 - Se o nó tem dois filhos. *
* *
*****************************************/
//Antes de qualquer caso verificamos se a árvore não é nula.
if((*Tree) == NULL)
return;
// Procuramos o nó que queremos remover.
treeNode * temp;
temp = busca(Tree,data);
/*
Caso 1:
Neste caso, para se remover um nó k, fazemos com que o pai de k, p(k) aponte para NULL e excluimos
o próprio nó.
*/
if(temp->esq == NULL && temp->dir == NULL){
treeNode * paiNode;
// Acha o pai do nó que queremos remover
paiNode = pai(Tree,data);
// Vê se o nó que queremos remover é o da esquerda ou o da direita
// Esquerda
printf("%d\n",paiNode->data);
if (paiNode->esq != NULL){
if (paiNode->esq->data == data){
free(paiNode->esq);
paiNode->esq = NULL;
return;
}
}
// Direita
if (paiNode->dir != NULL){
if(paiNode->dir->data == data){
free(paiNode->dir);
paiNode->dir = NULL;
return;
}
}
}
/*
Caso 2:
Neste caso o nó tem apenas um filho, basicamente fazemos o pai de k apontar para o filho de k
*/
// Ele tem somente um filho a direita
if(temp->esq == NULL && temp->dir != NULL){
treeNode * paiNode = pai(Tree,data);
// Faz com que o filho da direita do pai de temp se torne o filho de temp
paiNode->dir = temp->dir;
// Libera o nó que queremos remover
free(temp);
return;
}
// Tendo somente um filho a esquerda
if(temp->esq != NULL && temp->dir == NULL){
treeNode * paiNode = pai(Tree,data);
// Faz com que o filho da direita do pai de temp se torne o filho de temp
paiNode->esq = temp->esq;
// Libera o nó que queremos remover
free(temp);
return;
}
/*
Caso 3:
Neste caso o nó tem dois filhos, procuramos o filho mais a direita da sub-árvore a esquerda e
substituimos os dados dele e liberamos esta folha
*/
if (temp->esq != NULL && temp->dir != NULL){
int aux;
// Acho o nó mais a direita da sub-árvore a esquerda
treeNode * direita = maisDireita(&(temp->esq));
// Salva o dado do ponteiro direita em um inteiro auxiliar
aux = direita->data;
// Deleta o nó mais a direita
deleteNode(Tree,direita->data);
// Transfere o dado para a o nó que deveria ser "removido"
temp->data = aux;
}
}
treeNode * pai(root Tree, int data){
// So realizamos operações se a árvore não for nula
if(*Tree != NULL){
treeNode * temp;
temp = *Tree;
// Verifica se o nó a direita ou a esquerda é igual ao nó que desejamos procurar, caso seja
// retorna ele
if (temp->esq != NULL)
if (temp->esq->data == data)
return temp;
if (temp->dir != NULL)
if (temp->dir->data == data)
return temp;
// Procura na sub-árvore a esquerda caso o dado seja menor do que o que está no nó.
if (data < temp->data)
pai(&(temp->esq),data);
// Procura na sub-árvore a direita caso o dado seja maior do que o que está no nó.
else if (data > temp->data)
pai(&(temp->dir),data);
}
}
treeNode * busca(root Tree,int data){
// Verifica se a árvore não é vazia
if (*Tree == NULL)
return NULL;
// Checa se o dado do nó é o dado que estamos procurando
if ((*Tree)->data == data)
return (*Tree);
// Caso não seja:
// Se o dado for menor do que o dado atual, vai para a árvore da esquerda
if (data < (*Tree)->data)
busca(&((*Tree)->esq),data);
// Caso contrário vai para a árvore da direita
else
busca(&((*Tree)->dir),data);
}
treeNode * maisDireita(root Tree){
// Verificamos se a árvore não é vazia
if(*Tree != NULL){
treeNode * temp = (*Tree);
// Caminha até o filho mais a direita
while(temp->dir != NULL){
temp = temp->dir;
}
return temp;
}
}
#endif