Remoção de nó em árvore binária

Cabreuvas
(usa Debian)

Enviado em 23/04/2022 - 18:38h

Olá, estou tentando fazer um algoritmo simples de árvore binária em C, mas a função para deletar um nó simplesmente não faz efeito algum.

void delNode(Node *root)

{   

    Node *leaf, **nroot;

    int found = 0, target;



    printf("\nNode to be removed: ");

    scanf("%d", &target);

    printf("\n");



    while (root != NULL){

        if (root->code == target){

            nroot = &root;

            found = 1;

            break;

        }

        if (target < root->code) root = root->left;

        else root = root->right;

    }



    if (!found){

    printf("Node not found.");

    return;

    }



    if ((*nroot)->left == NULL && (*nroot)->right == NULL) *nroot = NULL;

    else if ((*nroot)->left != NULL) *nroot = (*nroot)->left;

    else if ((*nroot)->right != NULL) *nroot = (*nroot)->right;

    else {

        leaf = findClosest(*nroot);

        *nroot = leaf;

        leaf = NULL;

        free(leaf);

    }

    if (*nroot == NULL) free(*nroot);

    return;

} 

int main()

{

    Node *root = NULL;

    for (int i=0; i<10; i++){

        if (root == NULL) root = insNode(root, createNode());

        else insNode(root, createNode());

    }

    printf("\n");

    prntTree(root);

    printf("\n");

    delNode(root);

    prntTree(root);

    return 0;

} 

Creio que seja problema no ponteiro do nó a ser removido, mas eu tentei apontar de todas as formas e nada de remover o nó, se os senhores tiverem alguma dica de como isso poderia ser implementado seria de grande ajuda.

Código completo: https://pastebin.com/VRXKMtXA

paulo1205
(usa Ubuntu)

Enviado em 25/04/2022 - 05:28h

Se você quer poder alterar qualquer nó, incluindo o nó raiz, então você tem de se referir a ele com um ponteiro para ponteiro. Caso contrário, a modificação que você fizer dentro da função não vai aparecer fora dela.

Você até tenta usar um ponteiro para ponteiro com a variável que você chamou de nroot, mas perceba que você a inicializou com o endereço do parâmetro da função, cujo valor é uma mera cópia do endereço que foi passado à função como argumento.

Lembre-se que o C sempre passa argumentos por valor; se você quiser uma referência, tem de criar uma por meio do operador &, e passar o valor obtido manualmente dessa operação.


... Então Jesus afirmou de novo: “(...) eu vim para que tenham vida, e a tenham plenamente.” (João 10:7-10)

leandropscardua
(usa Ubuntu)

Enviado em 25/04/2022 - 11:04h

É bom rodar o free primeiro e depois atribuir null no ponteiro. Senão vc perde a referência da memória e a aplicação continua prendendo ela.

paulo1205
(usa Ubuntu)

Enviado em 25/04/2022 - 22:32h

Atribuir NULL só é necessário quando você remove um nó que era uma folha (i.e. não tem nós filhos). Quem desfaz todos os vínculos do programa com a memória é a chamada a free(), não a alteração de valor do ponteiro.


... Então Jesus afirmou de novo: “(...) eu vim para que tenham vida, e a tenham plenamente.” (João 10:7-10)