How to remove a node in a binary search tree with these specifics?

Question

How to remove a node in a binary search tree with these specifics?

Navigation

#1 by (0 votes)

0

I have the following binary tree:

Defined by the following data struct:

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

typedef struct Node * root;

And I have the following function:

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

I need to remove the nodes with the following specifications:

If the node is a leaf, simply remove it.

If you remove a key node x, with only 1 descendant, the ancestor of x will be the ancestor of the descendant of x.

My problem is to get the antecedent, I tried this way, but when I try to remove 8, for example, ant is in 6.

How to proceed?

c

asked by anonymous 04.12.2017 / 23:46

1 answer

search with select in database with repeated records Mount a table of products as a window in java jsp

score 0 · Accepted Answer

The error is as follows:

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

Role of MenorNo() , if interested:

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