Árvores Binárias
Uma árvore binária é uma estrutura de dados caracterizada por:
- Ou não tem elemento algum (árvore vazia).
- Ou tem um elemento distinto, denominado raiz, com dois ponteiros para duas estruturas diferentes, denominadas sub-árvore esquerda e sub-árvore direita.
Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores de busca binária.
Todo nodo de uma árvore pode ter no máximo 2 nodos filhos, a árvore será chamada de binária. Os 2 filhos de um nodo são chamados de filho à esquerda e filho à direita.
Um nó em uma árvore binária não tem necessariamente 2 nodos filhos, pode ter somente 1 ou nenhum no caso das folhas. Mas a estrutura do nodo mantém-se para abrigar o máximo de 2 que podem ou não ser preenchidos com referências para os nodos filhos.
Caso a referência da esquerda esteja vazia, quer dizer que não há nodos filhos à esquerda.Caso a referencia da direita esteja vazia, quer dizer que não há filhos à direita.
Caso as duas referências, da esquerda e da direita estejam vazias, quer dizer que não há nenhum nodo filho, portanto este nodo é uma folha. Inicialmente teremos os métodos de busca e inserção com definição da raiz.
public class Nodo {
public Nodo
esquerda;
public int
valor;
public Nodo direita;
public void
Nodo() {}
public Nodo(Nodo
esquerda, int valor, Nodo direita) {
this.esquerda
= esquerda;
this.valor
= valor;
this.direita = direita;
}
public
void toShow() throws NullPointerException {
System.out.println( "[" + valor + "]"
);
}
}
|
public class Arvore {
private
Nodo raiz;
public void definirRaiz(Nodo
nodo) {
raiz =
nodo;
}
public Nodo buscar(int
valorProcurado) {
Nodo
corrente = raiz;// Começa a busca pela raiz
while
(corrente.valor != valorProcurado) {
if
(valorProcurado < corrente.valor) {
corrente
= corrente.esquerda;// Esquerda
}
else
{
corrente
= corrente.direita;// Direita
}
if
(corrente == null) // Nao achou...
return null;
}
return
corrente;
}
public
void inserir(int valor) {
Nodo novoNodo = new Nodo(
null, valor, null );
if
(raiz == null) {// primeiro nodo?
definirRaiz( novoNodo );
System.out.println( "Definindo " + valor + "
como RAIZ" );
}
else
{// ja existe raiz
Nodo
corrente = raiz;
Nodo
filho;
while
(true) {
filho
= corrente;
//
Verificando o galho da esquerda
if
(valor < corrente.valor) {// vai para esquerda
corrente
= corrente.esquerda;
if
(corrente == null) {// fim da linha
filho.esquerda
= novoNodo;
System.out.println( "Inserindo " + valor
+
" à esquerda de " + filho.valor );
return;
}
}//
Fim esquerda
//
Verificando o galho da direita
else
{
corrente
= corrente.direita;
if
(corrente == null) {// fim da linha
filho.direita
= novoNodo;
System.out.println( "Inserindo " + valor
+
" à direita de " + filho.valor );
return;
}
}//
Fim direita
}//
Fim While
}//
Fim else nao-raiz
}
public
void exibir() {
if
(this.raiz == null) {
System.out.println( "Arvore vazia" );
}
else
{
exibir( this.raiz, 1 );
}
}
private void
exibir(Nodo nodo, int t) {
if
(nodo != null) {
exibir(
nodo.direita, t + 1 );
for (int i = 0; i <
t; i++) {
System.out.printf( " " );
}
System.out.printf( "%d \n", nodo.valor
);
exibir(
nodo.esquerda, t + 1 );
}
}
}
|
REMOÇÃO
DE NODOS
Neste
caso temos 3 situações:
- O nodo a ser removido é uma folha.
- O nodo a ser removido tem grau 1.
- O nodo a ser removido tem grau 2.
No
primeiro caso,
basta remover o nodo da árvore sem maiores preocupações.
No
segundo caso, o nodo
em questão é recortado da árvore e o seu antecessor passa a referenciar seu
sucessor.
No
terceiro caso, o mais
complexo entre eles, para uma árvore como esta abaixo:
Para
removermos o Nodo com o valor 12, que tem 2 Nodos filhos, o procedimento é o
seguinte:
- Encontrar o menor elemento na subárvore à direita do Nodo a ser removido. Neste exemplo o elemento procurado é o 19.
- Substituir o valor do Nodo a ser removido, pelo valor do menor Nodo da suabárvore da direita.
- Remover o menor Nodo da subárvore da direita.
Primeiramente
acrescentamos à classe Arvore o método recursivo minValorSubDireita(Nodo nodo);
que traz o menor valor da subárvore da direita.
|
|
public int minValorSubDireita(Nodo
nodoDireita) {
if (nodoDireita.esquerda
== null) {
return
nodoDireita.valor;
}
else {
return
minValorSubDireita( nodoDireita.esquerda );
}
}
|
|
| public void
remover(int valor){
Nodo corrente =
raiz;
Nodo extensao;
while(true){
extensao = corrente;
if (valor >
corrente.valor) {// direita
corrente = corrente.direita;
if (corrente.direita == null
&& corrente.esquerda == null) {
extensao.direita = null;
return;
}
else if(corrente.direita
== null && corrente.esquerda != null){
if (raiz ==
corrente)
raiz =
corrente.esquerda;
else if
(corrente.esquerda != null && corrente.direita == null)
extensao.direita =
corrente.esquerda;
else
extensao.direita =
corrente.direita;
}
else if(corrente.esquerda
== null && corrente.direita != null){
if (raiz ==
corrente)
raiz =
corrente.direita;
else if
(corrente.esquerda != null && corrente.direita == null)
extensao.direita =
corrente.esquerda;
else
extensao.direita =
corrente.direita;
}
else{
minSubDireito(extensao.direita);
}
}
else{//esquerda
corrente = corrente.esquerda;
if (corrente.direita == null
&& corrente.esquerda == null) {
extensao.esquerda = null;
return;
}
else if(corrente.direita
== null && corrente.esquerda != null){
if (raiz ==
corrente)
raiz =
corrente.esquerda;
else if
(corrente.esquerda != null && corrente.direita == null)
extensao.esquerda =
corrente.esquerda;
else
extensao.esquerda =
corrente.direita;
}
else if(corrente.esquerda
== null && corrente.direita != null){
if (raiz ==
corrente)
raiz =
corrente.direita;
else if
(corrente.esquerda != null && corrente.direita == null)
extensao.esquerda =
corrente.esquerda;
else
extensao.esquerda =
corrente.direita;
}
else{
minSubDireito(extensao.esquerda);
}
}
}
}
|
Nenhum comentário:
Postar um comentário