0
I have an exercise to do and submit it to an automatic broker (Sharif), in my tests all cases work out, but in the broker I’m receiving a Runtime Error, I’ve reviewed this code many times and I don’t find the error. (The exaggerated detail is precisely because I try 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
Runtime Error ==> RTE. This is due to the program exiting with a non-0 code. This is usually due to some segmentation failure or something else that caused your program to abort. Other competitive programming errors (such as this submission system) are: Compilation Error (unable to compile the source), Presentation Error (the content of the answer is correct, but it is not being presented correctly), Wrong Answer (wrong answer) and Time Limit Exceeded(TLE, very slow program, the system could not even judge whether it was missing the answers)
– Jefferson Quesado
@Jeffersonquesado Really, the problem was this, the fact of missing the
return 0
at the end of main.– Matheus
I always thought G++ would put one
return 0
implicit at the end ofmain
. But anyway, I’m glad you corrected– Jefferson Quesado