ArvorePesquisaInt

[diogodejesus 0]

/* Classe que implementa uma árvore binária de pesquisa sobre inteiros */public class ArvorePesquisaInt extends ArvoreBinaria{ // Construtor public ArvorePesquisaInt(int valor) { super(new Integer(valor)); } // Insere um valor na árvore public void inserir(int valor) { int vlr; Nodo nd = obterRaiz(); while (true) { //obtendo o conteudo do nodo e transformando em inteiro e mandando esse valor inteiro para a variavel vlr vlr = ((Integer)nd.obterConteúdo()).intValue(); if (valor == vlr) { return; } if (valor < vlr) { if (nd.obterFilhoEsquerdo()!= null) { nd = nd.obterFilhoEsquerdo(); } else { inserirFilhoEsquerdo(nd, new Integer(valor)); return ; } } if (valor > vlr) { if (nd.obterFilhoDireito()!= null) { nd = nd.obterFilhoDireito(); } else { inserirFilhoDireito(nd, new Integer(valor)); return; } } } /* ALGORITMO: * * O nodo atual começa sendo a raiz * Fica em repetição fazendo: * Compara o valor procurado com o conteúdo do nodo atual * Se o valor for igual, termina, pois o valor já está na árvore * Se o valor for menor, tenta ir para o filho esquerdo do nodo atual * Se existir o filho esquerdo, volta para o início da repetição * Caso contrário, é lá que deveria estar o valor procurado, então * crie novo nodo como filho esquerdo do nodo atual e termine * Se o valor for maior, tenta ir para o filho direito do nodo atual * Se existir o filho direito, volta para o início da repetição * Caso contrário, é lá que deveria estar o valor procurado, então * crie novo nodo como filho direito do nodo atual e termine */ } // Pesquisa se valor está presente na árvore e retorna o nodo correspondente public Nodo pesquisar(int valor) { /* ALGORITMO: * * Semelhante a "insere", só que apenas retorna o nodo se encontrado, * caso contrário retorna "null". */ int vlr; Nodo nd = obterRaiz(); while (true) { //obtendo o conteudo do nodo e transformando em inteiro e mandando esse valor inteiro para a variavel vlr vlr = ((Integer)nd.obterConteúdo()).intValue(); if (valor == vlr) { return (nd); } if (valor < vlr) { if (nd.obterFilhoEsquerdo() != null) { nd = nd.obterFilhoEsquerdo(); } return (nd); } if (valor > vlr) { if (nd.obterFilhoDireito() != null) { nd = nd.obterFilhoDireito(); } return (nd); } } // Substitui o nodo por outro, alterando o seu pai private void substituir(Nodo n, Nodo substituto) { /* ALGORITMO: * * Obtém o nodo pai * Se o pai é nulo, "n" é a raiz, então faz com que a raiz seja o substituto * Caso contrário: * Se n é o filho esquerdo do pai, então o filho esquerdo passa a ser o substituto * Se n é o filho direito do pai, então o filho direito passa a ser o substituto * Se o substituto não é nulo, atualiza o pai desse nodo */ } // Remove um valor da árvore, ajustando a mesma /*public boolean remover(int valor) { /* ALGORITMO: * * Se tamanho for 1, não remove a raiz e termina. * Caso contrário, testa se o valor está presente. Se não estiver, termina. * O nodo "n" é o nodo encontrado que contém o valor. * Obtém os filhos esquerdo e direito de "n" * Se um deles for nulo, temos o caso mais simples, em que basta remover "n" e * fazer o único filho "subir", atualizando o pai de "n". * Caso existam os dois filhos, é necessário encontrar o nodo com valor * imediatamente superior ao nodo atual para tomar o seu lugar, indo até * o nodo mais à esquerda na subárvore direita abaixo de "n". } */}

[Giancarlo Braga 0]

Olá amigo.

Posso lhe sugerir um algoritmo de busca em árvore binária?

 

- Supondo que o cada nó é um objeto da classe 'No' e a raiz(root) da árvore é definida pela variável de mesmo nome.

- E que a variável x é o que você quer achar.

 

Olha:

 

 

public void buscaArvoreBinaria(No raiz, int x){if(raiz != null){	   		   //se for igual diz que encontrou - esse é o ponto de parada da recursão!		   if(raiz.chave == x){						System.out.println("Encontrou!");			}else{					if(raiz.chave < x){					   //se for menor usa recursão com o lado esquerdo					   buscaArvoreBinaria(raiz.ponteiroEsquerdo, x);					}else{					   //se for maior usa recursão com o lado direito					   buscaArvoreBinaria(raiz.ponteiroDireito, x);					}		   }	 }else{  System.out.println("Não encontrou.");}//fim do if}//fim do método

Funcionou?

Eu acho ele bem simples.

Vi esses dias ainda na aula de estrutura de dados II.

 

Ele vai checar se a raiz é nula, se não for nula ele vai checar se é igual, isso será o ponto de parada. Se não for igual ele vai ao else e faz um novo if. Esse novo if que vai dar seguimento às recursões passando como valor os objetos(ponteiros) referentes ao lado a qual está seguindo.

 

Abraço.

[diogodejesus 0]

Beleza amigo show de bola, mas é que precisaria usar o método PESQUISAR, igual postei ontem, e tem que retornar um nodo, é que é um exercicio e teria que fazer naqueles moldes, será que dá para adaptar em cima desse que você colocou ??

 

Valeu

 

 

Olá amigo.

Posso lhe sugerir um algoritmo de busca em árvore binária?

 

- Supondo que o cada nó é um objeto da classe 'No' e a raiz(root) da árvore é definida pela variável de mesmo nome.

- E que a variável x é o que você quer achar.

 

Olha:

 

 

public void buscaArvoreBinaria(No raiz, int x){if(raiz != null){	   		   //se for igual diz que encontrou - esse é o ponto de parada da recursão!		   if(raiz.chave == x){						System.out.println("Encontrou!");			}else{					if(raiz.chave < x){					   //se for menor usa recursão com o lado esquerdo					   buscaArvoreBinaria(raiz.ponteiroEsquerdo, x);					}else{					   //se for maior usa recursão com o lado direito					   buscaArvoreBinaria(raiz.ponteiroDireito, x);					}		   }	 }else{  System.out.println("Não encontrou.");}//fim do if}//fim do método

Funcionou?

Eu acho ele bem simples.

Vi esses dias ainda na aula de estrutura de dados II.

 

Ele vai checar se a raiz é nula, se não for nula ele vai checar se é igual, isso será o ponto de parada. Se não for igual ele vai ao else e faz um novo if. Esse novo if que vai dar seguimento às recursões passando como valor os objetos(ponteiros) referentes ao lado a qual está seguindo.

 

Abraço.

[Giancarlo Braga 0]

Cara.Lendo seu algoritmo por cima eu achei que é a mesma coisa.Só que usando recursão.