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

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

Cabreuvas
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


  


2. Re: Remoção de nó em árvore binária

Paulo
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)


3. Re: Remoção de nó em árvore binária

leandro peçanha scardua
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.


4. Re: Remoção de nó em árvore binária

Paulo
paulo1205

(usa Ubuntu)

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

leandropscardua escreveu:

É 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.


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)






Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts