0

Tenho a seguinte árvore binária :

exemplo de uma arvore binária

Definida pela seguinte estruta de dado :

typedef struct Node{
  int data;
  struct Node * left;
  struct Node * right;
} node;

typedef struct Node * root;

E tenho a seguinte função :

void removeNode(root * start, int key){
    node * ant; 
    if (*start == NULL){
      return ;
    }

    //Verifica se a chave é igual ao nó naquele momento
    if((*start)->data == key){
        //Verifica se é uma folha
        if((*start)->left == NULL && (*start)->right == NULL){
            free(*start);
            *start = NULL;
            return;
        }
        //Verifica se tem somente um descendente à esquerda
        else if((*start)->left != NULL && (*start)->right == NULL){
            ant = (*start)->left;
            free(*start);
            *start = NULL;
            return;
        }
        //Verifica se tem somente um descendente à direita
        else if((*start)->left == NULL && (*start)->right != NULL){
            ant = (*start)->right;
            free(*start);
            *start = NULL;
            return; 
        }
    } else {
        ant = *start;
        removeNode(&(*start)->left,key);
        ant = *start;
        removeNode(&(*start)->right,key);
    }
}

Preciso remover os nós com as seguintes especificações:

  1. Caso o nó seja uma folha, simplesmente remover ele.
  2. Ao se remover um nó de chave x, com apenas 1 descendente, o ancestral de x será o ancestral do descendente de x.

O meu problema está em pegar o antecedente, tentei desta forma, mas quando tento remover o 8, por exemplo, o ant fica no 6.

Como proceder?

1 Resposta 1

0

O erro é o seguinte:

    void tree_remove(tree * root, int id){
    if((*root) == NULL) return ;
    if(id < (*root)->value) tree_remove(&(*root)->left, id);    
    if(id > (*root)->value) tree_remove(&(*root)->right, id);
    else if(id == (*root)->value){

        //auxiliar recebe o nó
        node * aux = (*root);
        //SE O NÓ A SER REMOVIDO FOR UMA FOLHA
        if((*root)->left == NULL && (*root)->right == NULL){
            free(aux);
            (*root) = NULL;
        }
        //SE SÓ HOUVER O GALHO DIREITO
        else if((*root)->left == NULL){
            //O que apontava pro nó, agora aponta pro seu galho direito
            //assim a referencia não é perdida
            (*root) = (*root)->right;
            //depois que a perna direita é passada pro local do nó, ela é
            //liberada
            aux->right = NULL;
            free(aux);
            aux = NULL;
        }
        //SE SÓ HOUVER O GALHO ESQUERDO
        else if((*root)->right == NULL){
            (*root) = (*root)->left; //Mesmo acontece aqui
            aux->left = NULL;
            free(aux);
            aux = NULL;
        }
        //PEGA O MAIOR DO GALHO ESQUERDO OU O MENOR DO DIREITO
        else{
            aux = MenorNo(&(*root)->right); //função que vai pegar o menor nó
            //do galho direito 
            //Menor nó do galho direito recebe os 
            //galhos do nó que será removido
            aux->left = (*root)->left; 
            aux->right = (*root)->right; 
            //Memória é liberada
            free((*root)); //liberado
            (*root)->left = (*root)->right = NULL; //liberada a memoria dos
            //galhos
            (*root) = aux; //menor galho esquerdo é 'linkado' no local do 
            //outro
            aux=NULL;
        }
    }
}

Função do MenorNo(), caso esteja interessado:

    node * MenorNo(tree * root){
    //PERCORRE ATÉ O ULTIMO NÓ ESQUERDO
    if((*root)->left != NULL)
        return MenorNo(&(*root)->left);
    else{ //CHEGA NO ULTIMO
        node * aux = (*root); //PEGA A REFERENCIA DELE
        //SE HOUVER UMA PERNA DIREITA, O PONTEIRO PASSA
        //A APONTAR PRA ELA (CASO CONTRARIO O GALHO DIREITO SE PERDE)
        if((*root)->right != NULL) 
            (*root) = (*root)->right;
        //CASO CONTRARIO É SETADO NULL
        else (*root) = NULL;
        return aux; //RETORN O MENOR PONTEIRO
    }
}

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 .