Hey galera.
Estou implementando um método de remoção de elemenos de uma árvore binária.
Precisava que alguem me ajudasse aqui. Parece estar todo correcto mas tenho medo que me tenha faltado algum caso… Obrigado
Meu código:
public void delete(int dados) {
raiz = delete(dados, raiz);
}
/**
Retira um nó da Árvore Binária
- se o elemento for uma folha, remove-se simplesmente o elemento
- se o elemento é um nó interno e tem apenas um filho, esse filho é colocado no lugar do elemento a remover (que é seu pai)
- se o elemento é um nó interno e tem dois filhos, coloca-se na posição do elemento a remover o menor elemento da sub-árvore direita (uma transferência de posição)
*/
public NoBinario delete(int dados, NoBinario temp){
if (dados==temp.dados){ //Se o nó foi encontrado…
if((temp.noEsquerdo==null) && (temp.noDireito==null)){
//1º caso: nó não tem filhos nem á esquerda, nem á direita
//folha simplesmente eliminada
temp=null;
}else if((temp.noEsquerdo!=null) && (temp.noDireito!=null)){
//3º caso: nó tem dois filhos, à esquerda e à direita
if((temp.noEsquerdo.noEsquerdo==null) && (temp.noEsquerdo.noDireito==null) && (temp.noDireito.noEsquerdo==null) && (temp.noDireito.noDireito==null)){
temp.dados=minimo(temp.noDireito);
temp.noDireito=null;
}
else if((temp.noDireito.noEsquerdo==null) && (temp.noDireito.noDireito!=null)){
temp.dados=temp.noDireito.dados;
temp.noDireito=temp.noDireito.noDireito;
}
else if((temp.noDireito.noEsquerdo!=null) && (temp.noDireito.noDireito==null)){
temp.dados=minimo(temp.noDireito);
temp.noDireito.noEsquerdo = null;
}
else if((temp.noDireito.noEsquerdo!=null) && (temp.noDireito.noDireito!=null)){
temp.dados=minimo(temp.noDireito);
temp.noDireito.noEsquerdo = null;
}
else if((temp.noEsquerdo.noDireito==null) && (temp.noEsquerdo.noEsquerdo!=null)){
temp.dados=temp.noEsquerdo.dados;
temp.noEsquerdo=temp.noEsquerdo.noEsquerdo;
}//
else if((temp.noEsquerdo.noDireito!=null) && (temp.noEsquerdo.noEsquerdo==null)){
temp.dados=temp.noEsquerdo.dados;
temp.noEsquerdo=temp.noEsquerdo.noDireito;
}
else if((temp.noEsquerdo.noEsquerdo!=null) && (temp.noEsquerdo.noDireito!=null)){
temp.dados=maximo(temp.noEsquerdo);
temp.noEsquerdo.noDireito=null;
}
}else if((temp.noEsquerdo!=null) && (temp.noDireito==null)){
//2º caso: nó tem filhos apenas à esquerda
//coloca o nó no lugar do elemento que é seu pai do lado esquerdo
temp.dados=temp.noEsquerdo.dados;
temp.noEsquerdo=temp.noEsquerdo.noEsquerdo;
return temp;
}else if((temp.noEsquerdo==null) && (temp.noDireito!=null)){
//2º caso: nó tem filhos apenas à direita
//coloca o nó no lugar do elemento que é seu pai do lado direito
temp.dados=temp.noDireito.dados;
temp.noDireito=temp.noDireito.noDireito;
return temp;
}
}else if (dados<temp.dados){ //Se o elemento for menor que os dados da raiz actual
temp.noEsquerdo=delete(dados, temp.noEsquerdo);
return temp;
}else if (dados>temp.dados){ //Se o elemento for maior que os dados da raiz actual
temp.noDireito=delete(dados, temp.noDireito);
return temp;
}
return temp;
}[color=“red”][/color][color="#444444"][/color]