Presiso de um metodo para fazer busca nessa arvore binaria!

3 respostas
IFMT
preciso de um agoritimo que faça uma busca em uma arvore binaria!!!
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package arvorebin;

/**
 *
 * @author Joabe
 */
// definição da classe TreeNode
class TreeNode
{
   // membros de acesso de pacote
   TreeNode leftNode; // nó esquerdo
   int data; // valor do nó
   TreeNode rightNode; // nó direito

   // construtor inicializa os dados e os torna um nó-folha
   public TreeNode( int nodeData )
   {
      data = nodeData;
      leftNode = rightNode = null; // o nó não tem nenhum filho
   } // fim construtor sem argumento TreeNode

   // localiza ponto de inserção e insere novo nó; ignora os valores duplicados
   public void insert( int insertValue )
   {
      // insere na subárvore esquerda
      if ( insertValue < data )
      {
         // insere novo TreeNode
         if ( leftNode == null )
            leftNode = new TreeNode( insertValue );
         else // continua percorrendo subárvore esquerda
            leftNode.insert( insertValue );
      } // fim do if
      else if ( insertValue > data ) // insere na subárvore direita
      {
         // insere novo TreeNode
         if ( rightNode == null )
            rightNode = new TreeNode( insertValue );
         else // continua percorrendo subárvore direita
            rightNode.insert( insertValue );
      } // fim de else if
   } // fim do método insert
} // fim da classe TreeNode

// definição da classe Tree
  class Tree
{
   private TreeNode root;
   private  int cont;

   // construtor inicializa uma Tree de inteiros vazia
   public Tree()
   {
      root = null;
      cont=0;
   } // fim construtor sem argumento Tree

   // insere um novo nó na árvore de pesquisa binária
   public void insertNode( int insertValue )
   {
      if ( root == null )
         root = new TreeNode( insertValue ); // cria o nó raiz aqui
      else
         root.insert( insertValue ); // chama o método insert
   } // fim do método insertNode

   // inicia percurso na pré-ordem
   public void preorderTraversal()
   {
      preorderHelper( root );
      System.out.println("  A quantidade de nós: "+cont);
   } // fim do método preorderTraversal

   // método recursivo para realizar percurso na pré-ordem
   private void preorderHelper( TreeNode node )
   {
      if ( node == null )
         return;
      System.out.printf( "%d ", node.data ); // gera saída de dados do nó
      preorderHelper( node.leftNode );       // percorre subárvore esquerda
      preorderHelper( node.rightNode );      // percorre subárvore direita
      cont++;
   } // fim do método preorderHelper

   // inicia percurso na ordem
   public void inorderTraversal()
   {
      inorderHelper( root );
   } // fim do método inorderTraversal

   // método recursivo para realizar percurso na ordem
   private void inorderHelper( TreeNode node )
   {
      if ( node == null )
         return;

      inorderHelper( node.leftNode );        // percorre subárvore esquerda
      System.out.printf( "%d ", node.data ); // gera saída de dados do nó
      inorderHelper( node.rightNode );       // percorre subárvore direita
   } // fim do método inorderHelper

   // inicia percurso na pós-ordem
   public void postorderTraversal()
   {
      postorderHelper( root );
   } // fim do método postorderTraversal

   // método recursivo para realizar percurso na pós-ordem
   private void postorderHelper( TreeNode node )
   {
      if ( node == null )
         return;

      postorderHelper( node.leftNode );      // percorre subárvore esquerda
      postorderHelper( node.rightNode );     // percorre subárvore direita
      System.out.printf( "%d ", node.data ); // gera saída de dados do nó
   } // fim do método postorderHelper
} // fim da classe Tree

A classe que testa a arvore é essa!!

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package arvorebin;

import java.util.Random;

/**
 *
 * @author Joabe
 */
public class TreeTest
{
   public static void main( String args[] )
   {
      Tree tree = new Tree();
      int value;
      Random randomNumber = new Random();

      System.out.println( "Inserindo valores Aleatórios: " );

      // insere 10 inteiros aleatórios de 0-99 na árvore
      for ( int i = 1; i <= 10; i++ )
      {
         value = randomNumber.nextInt( 100 );
         System.out.print( value + " " );
         tree.insertNode( value );
      } // fim do for

      System.out.println ( "\n\nPreorder traversal" );
      tree.preorderTraversal(); // realiza percurso na pré-ordem da árvore

      System.out.println ( "\n\nInorder traversal" );
      tree.inorderTraversal(); // realiza percurso na ordem da árvore

      System.out.println ( "\n\nPostorder traversal" );
      tree.postorderTraversal(); // realiza percurso na pós-ordem da árvore
      System.out.println();
   } // fim de main
} // fim da classe TreeTest

3 Respostas

ViniGodoy

Legal, então mãos à obra…

walissongpi

well, well, well.
Parabens! Na minha época a minha árvore foi feita em C e o código ficou horrível. 8)
Para a função de busca vc pode utilizar a pre-ordem como modelo, bastando passar apenas um parametro a ela e verificar se o nó possui o nó possui o valor procurado. Se sim, retorne-o. Existem diversos algorítmos de busca em arvores binárias. Boa sorte.

fantomas

kkkkkkkkkk!

É isso ai.

IFMT, tente fazer e relate suas dúvidas.

flws

Criado 12 de maio de 2010
Ultima resposta 13 de mai. de 2010
Respostas 3
Participantes 4