Breakpoint in function SearchAppleApaga (Binary trees)

0

Good, I have an error in the SearchArvoreApaga function, when I try to delete a value from the binary tree nothing happens and if I try to delete the root of the tree I get the following breakpoint:

Exception thrown: read access violation.

Root was 0xCCCCCCCC.

Make the code available to anyone who wants to help me or to test for you:

#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;
        }
    }
}

I use Visual Studio 2015

    
asked by anonymous 26.06.2017 / 18:16

1 answer

0

Your code has some problems with logic, for example, the DestroyNode function calls theAppleApp. You also are not deleting the reference of the deleted node on the parent node, causing it to point to an invalid memory location.

#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;
        }
    }
}
    
09.08.2017 / 20:39