0

Boas, Eu tenho um erro na função ProcuraArvoreApaga, quando tento apagar um valor da árvore binária não acontece nada e se tentar apagar a raiz da árvore obtenho o seguinte breakpoint:

Exception thrown: read access violation.

raiz was 0xCCCCCCCC.

Disponibilizo aqui o código para quem me quiser ajudar ou para testarem por vocês:

#include<stdio.h>
#include<stdlib.h>
#include<locale.h>
typedef struct tree *Arvore;
struct tree {
    Arvore left;
    Arvore right;
    int *valor;
};

void DestruirNode(Arvore *raiz);
void ProcuraArvoreApaga(Arvore *raiz, int *value);

Arvore CriarArvore(int value) {
    Arvore node;
    if ((node = (Arvore)malloc(sizeof(struct tree))) == NULL) {
        return NULL;
    }

    if ((node->valor = (int*)malloc(sizeof(int))) == NULL) {
        return NULL;
    }
    *node->valor = value;
    node->left = NULL;
    node->right = NULL;

    return node;
}

void DestruirArvore(Arvore *node) {
    free((*node)->valor);
    free(*node);
    *node = NULL;
}

void Inserir(Arvore *raiz, int value) {
    Arvore node = *raiz;
    Arvore anterior = NULL;
    if (*raiz == NULL) {
        *raiz = CriarArvore(value);
        return;
    }
    else {
        while (node != NULL) {
            anterior = node;
            if (*node->valor > value) {
                node = node->left;
            }
            else if (*node->valor < value) {
                node = node->right;
            }
            else {
                return;
            }
        }
        if (*anterior->valor > value) {
            anterior->left = CriarArvore(value);
        }
        else {
            anterior->right = CriarArvore(value);
        }
    }

}

void ImprimirArvore(Arvore raiz, int nivel) {
    int i;
    if (raiz == NULL) {
        for (i = 0; i < nivel; i++) {
            printf("\t");
        }
        printf("*\n");
        return;
    }
    ImprimirArvore(raiz->right, nivel + 1);
    for (i = 0; i < nivel; i++) {
        printf("\t");
    }
    printf("%d\n", *raiz->valor);
    ImprimirArvore(raiz->left, nivel + 1);
}

Arvore Minimo(Arvore *raiz) {
    Arvore node = *raiz;
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}

void DestruirNode(Arvore *raiz) {
    Arvore node = *raiz;
    if ((*raiz)->left == NULL && (*raiz)->right == NULL) {
        DestruirArvore(raiz);
    }
    else if ((*raiz)->right == NULL) {
        *raiz = (*raiz)->left;
        DestruirArvore(raiz);
    }
    else {
        *(*raiz)->valor = *Minimo((*raiz)->right)->valor;
        ProcuraArvoreApaga(&(*raiz)->right, (*raiz)->valor);
    }
}

void ProcuraArvoreApaga(Arvore *raiz, int *value) {
    if (*raiz == NULL) {
        return;
    }
    if (*(*raiz)->valor > *value) {
        ProcuraArvoreApaga(&(*raiz)->right, value);
    }
    else if (*(*raiz)->valor < *value) {
        ProcuraArvoreApaga(&(*raiz)->left, value);
    }
    else {
        /*value = *(*raiz)->valor;*/
        printf("%d", value);
        DestruirNode(&raiz);
    }
    return 0;
}

int main(void) {
    setlocale(LC_ALL, "Portuguese");
    Arvore raiz = NULL;
    int i = 0, escolha;
    int value = NULL;
    int var = NULL;

    for (i = 1; i < 2; i++) {
        printf("\t\tÁrvores binárias\n\n");
        printf("Selecione a operação que deseja efetuar:\n");
        printf("[1] Adicionar valor\n");
        printf("[2] Vizualizar árvore\n");
        printf("[3] Apagar valor/árvore\n");
        printf("[4] Sair\n\n");
        printf(">>");

        scanf("%d", &escolha);
        switch (escolha) {
        case 1:
            system("cls");
            printf("Introduza o valor a adicionar à árvore:\n>>");
            scanf("%d", &value);
            Inserir(&raiz, value);// Adiciona na árvore
            system("cls");
            i = 0;
            break;
        case 2:
            system("cls");
            printf("\t\tVisualização da árvore\n\n");
            ImprimirArvore(raiz, 10);// O 10 adiciona quantos níveis tem a árvore
            i = 0;
            break;
        case 3:
            system("cls");
            printf("Introduza o valor que deseja apagar(um valor que não seja folha apagará os ramos e folhas abaixo dele):\n>>");
            scanf("%d", &var);
            ProcuraArvoreApaga(&raiz, &var);
            system("cls");
            i = 0;
            break;
        case 4:
            break;
        }
    }
}

Eu utilizo o Visual Studio 2015

1
  • Não ajeitei o código, só questões. Por que você está passando value por referência na função ProcuraArvoreApaga? Por que você passa o endereço de uma árvore se árvore é o endereço de uma struct tree (em outras palavras raiz é um ponteiro de ponteiro)? Outra observação é que DestruirNode chama ProcuraArvoreApaga e ProcuraArvoreApaga chama DestruirNode. Commented 9/08/2017 às 17:27

1 Resposta 1

0

Teu código tem algunss problemas na lógica, como por exemplo, a função DestruirNodo chama a ProcuraArvoreApaga. Você também não está apagando a referência do nodo apagado no nodo pai, fazendo com que ele apontasse para uma posição inválida da memória.

#include<stdio.h>
#include<stdlib.h>
#include<locale.h>

typedef struct tree {
    struct tree *left;
    struct tree *right;
    int valor;
}Arvore;

void DestruirNode(Arvore* raiz);
void ProcuraArvoreApaga(Arvore** raiz, int value);

Arvore* CriarArvore(int value) {
    Arvore* node;
    if ((node = (Arvore*)malloc(sizeof(Arvore))) == NULL) {
        return NULL;
    }

    node->valor = value;
    node->left = NULL;
    node->right = NULL;

    return node;
}

void DestruirArvore(Arvore* node) {
    free(node);
    node = NULL;
}

void Inserir(Arvore** raiz, int value) {
    Arvore* node = *raiz;
    Arvore* anterior = NULL;
    if (*raiz == NULL) {
        *raiz = CriarArvore(value);
        return;
    }
    else {
        while (node != NULL) {
            anterior = node;
            if (node->valor > value) {
                node = node->left;
            }
            else if (node->valor < value) {
                node = node->right;
            }
            else {
                return;
            }
        }
        if (anterior->valor > value) {
            anterior->left = CriarArvore(value);
        }
        else {
            anterior->right = CriarArvore(value);
        }
    }

}

void ImprimirArvore(Arvore *raiz, int nivel) {
    int i;
    if (raiz == NULL) {
        for (i = 0; i < nivel; i++) {
            printf(".\t");
        }
        printf("*\n");
        return;
    }
    ImprimirArvore(raiz->right, nivel + 1);
    for (i = 0; i < nivel; i++) {
        printf(".\t");
    }
    printf("%d\n", raiz->valor);
    ImprimirArvore(raiz->left, nivel + 1);
}

Arvore* Minimo(Arvore* raiz) {
    Arvore *node = raiz;
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}

void DestruirNode(Arvore* raiz) {
    Arvore* node = raiz;
    if (node->left != NULL) {
        DestruirNode(node->left);
    }
    else if (node->right != NULL) {
        DestruirNode(node->right);

    }
    DestruirArvore(node);
}

void ProcuraArvoreApaga(Arvore** raiz, int value) {
    Arvore *node = *raiz;
    Arvore *pai = NULL;
    if(node->valor == value){
        *raiz = NULL;
        DestruirNode(node);
    } else {
        while(node && node->valor != value){
            pai = node;
            if(node->valor > value) node = node->left;
            else node = node->right;
        }
        if(node->valor == value){
            if(pai->valor > value) pai->left = NULL;
            else pai->right = NULL;
            DestruirNode(node);
        } 
    }
}

int main(void) {
    setlocale(LC_ALL, "Portuguese");
    Arvore* raiz = NULL;
    int i = 0, escolha;
    int value = NULL;
    int var = NULL;

    for (i = 1; i < 2; i++) {
        printf("\t\tÁrvores binárias\n\n");
        printf("Selecione a operação que deseja efetuar:\n");
        printf("[1] Adicionar valor\n");
        printf("[2] Vizualizar árvore\n");
        printf("[3] Apagar valor/árvore\n");
        printf("[4] Sair\n\n");
        printf(">>");

        scanf_s("%d", &escolha);
        switch (escolha) {
        case 1:
            system("cls");
            printf("Introduza o valor a adicionar à árvore:\n>>");
            scanf_s("%d", &value);
            Inserir(&raiz, value);// Adiciona na árvore
            system("cls");
            i = 0;
            break;
        case 2:
            system("cls");
            printf("\t\tVisualização da árvore\n\n");
            ImprimirArvore(raiz, 0);// O 10 adiciona quantos níveis tem a árvore
            i = 0;
            break;
        case 3:
            system("cls");
            printf("Introduza o valor que deseja apagar(um valor que não seja folha apagará os ramos e folhas abaixo dele):\n>>");
            scanf_s("%d", &var);
            ProcuraArvoreApaga(&raiz, var);
            system("cls");
            i = 0;
            break;
        case 4:
            break;
        }
    }
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .