preciso de um agoritimo que faça uma busca em uma arvore binaria!!!
[code]/*
- 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
[/code]
A classe que testa a arvore é essa!!
[code]/*
- 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 forSystem.out.println ( “\n\nPreorder traversal” );
tree.preorderTraversal(); // realiza percurso na pré-ordem da árvoreSystem.out.println ( “\n\nInorder traversal” );
tree.inorderTraversal(); // realiza percurso na ordem da árvoreSystem.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
[/code]