• En forma individual, investigar e implementar en Java un algoritmo de búsqueda. Se recomienda que desarrolle un programa que permita crear un árbol binario, recorrerlo en diferente orden, y haber búsqueda de un elemento dentro del árbol. También puede usar otra estructura de datos.
• Publicar en su blog y responder esta entrada, indicando su nombre y la url de su tarea en el blog de su grupo. Este trabajo debe quedar publicado para la clase del día sábado 20 de abril.
------------------------------------------------------------------------------------------------------------
Implementación de un Arbol binario
Por Rodrigo Lagos Lagos.
Nota: Blogspot no permite mas de 4000 caracteres por comentario , se crea nueva entrada.
/*
* RODRIGO LAGOS LAGOS
* Arbol Binario en JAVA.
*/
package arbolbinariorll;
import java.io.*;
/**
*
* @author rodrigo.lagos
* @version 1.0
*/
public class ArbolBinarioRLL {
/**
* @param args the command line arguments
*/
private Boolean existeNumero=false;
public static void main(String[] args) {
// TODO code application logic here
new ArbolBinarioRLL().ejecutarArbolBinario();
}
private static class Nodo
{
Nodo izquierda;
Nodo derecha;
int numero;
int posicion;
public Nodo() {
}
public Nodo(int numeroEntero) {
this.numero = numeroEntero;
}
public Nodo(int numeroEntero, int numeroPos) {
this.numero = numeroEntero;
this.posicion = numeroPos;
}
}
public void ejecutarArbolBinario()
{
BufferedReader teclado=new BufferedReader(new InputStreamReader(System.in));
int totalNodos = 0;
Boolean correcto=false;
do{
String entrada=null;
try
{
System.out.print("\nIngrese la cantidad de nodos que tendrá el árbol: ");
try{entrada = teclado.readLine();}catch(IOException e){entrada = null;}
totalNodos=Integer.parseInt(entrada);
if(totalNodos <= 2)
{
System.out.println("\nLa cantidad debe ser mayor que 2.");
}
else
{
correcto = true;
}
}
catch(NumberFormatException e)
{
System.out.println("\nValor ingresado no es entero.");
}
}while(correcto == false);
// Declarando el arbol
Nodo raiz = null;
System.out.println("\n========================================");
for(int indice=1; indice<=totalNodos; indice++)
{
int numero = 0;
Boolean salir = false;
do{
String entrada=null;
try
{
System.out.print("\nIngrese número entero para nodo [" + indice + "] : ");
try{entrada = teclado.readLine();}catch(IOException e){entrada = null;}
numero=Integer.parseInt(entrada);
VerificarExistencia(raiz, numero);
if(this.existeNumero == true)
{
System.out.println("\nValor ingresado ya existe.");
this.existeNumero = false;
}
else
{
salir = true;
}
}
catch(NumberFormatException e)
{
System.out.println("\nValor ingresado no es entero.");
}
}while(salir==false); // para asegurarme que ingresó un número.
if(raiz==null)
{
raiz=new Nodo(numero, indice );
}else{
// Insertando número en el nodo
insertarNumero(raiz, numero, indice);
}
}//fin ciclo FOR
System.out.println("\n=================================");
System.out.println("\nOrdenando el árbol:");
System.out.println("\n=================================");
imprimirEnOrden(raiz);
System.out.println("\n=================================");
int numero = 0;
Boolean salir = false;
do{
String entrada=null;
try
{
System.out.print("\nIngrese número a buscar: ");
try{entrada = teclado.readLine();}catch(IOException e){entrada = null;}
numero=Integer.parseInt(entrada);
salir = true;
}
catch(NumberFormatException e)
{
System.out.println("\nValor ingresado no es entero.");
}
}while(salir==false); // para asegurarme que ingresó un número.
VerificarExistencia(raiz, numero);
if(this.existeNumero)
{
ImprimeBusqueda(raiz, numero);
}
else
{
System.out.println(" El número # " + numero + " No esta ingresado.");
}
}
public void insertarNumero(Nodo rama, int numeroIngresado, int numeroPos) {
if (numeroIngresado < rama.numero) {
if (rama.izquierda != null) {
insertarNumero(rama.izquierda, numeroIngresado, numeroPos);
}
else
{
System.out.println(" Se inserta el # " + numeroIngresado +
" a la izquierda del nodo #" + rama.numero);
rama.izquierda = new Nodo(numeroIngresado, numeroPos);
}
}
else if (numeroIngresado > rama.numero)
{
if (rama.derecha != null) {
insertarNumero(rama.derecha, numeroIngresado, numeroPos);
} else {
System.out.println(" Se inserta el # " + numeroIngresado +
" a la derecha del nodo # " + rama.numero);
rama.derecha = new Nodo(numeroIngresado, numeroPos);
}
}
}
public void imprimirEnOrden(Nodo rama) {
if (rama != null) {
imprimirEnOrden(rama.izquierda);
System.out.println(" Orden # " + rama.numero);
imprimirEnOrden(rama.derecha);
}
}
public void ImprimeBusqueda(Nodo rama, int valorBuscado) {
if (rama != null) {
ImprimeBusqueda(rama.izquierda, valorBuscado );
if(valorBuscado == rama.numero){
System.out.println(" El número # " + valorBuscado + " existe en "
+ "la posicion [" + rama.posicion + "]");
}
ImprimeBusqueda(rama.derecha, valorBuscado);
}
}
public void VerificarExistencia(Nodo rama, int valorBuscado) {
if (rama != null) {
VerificarExistencia(rama.izquierda, valorBuscado);
if(valorBuscado == rama.numero){
this.existeNumero = true;
}
VerificarExistencia(rama.derecha, valorBuscado);
if(valorBuscado == rama.numero){
this.existeNumero = true;
}
}
}
}
// run:
// Ingrese la cantidad de nodos que tendrá el árbol: 8
// ========================================
// Ingrese número entero para nodo [1] : 6
// Ingrese número entero para nodo [2] : 8
// Se inserta el # 8 a la derecha del nodo # 6
// Ingrese número entero para nodo [3] : 8
// Valor ingresado ya existe.
// Ingrese número entero para nodo [3] : 6
// Valor ingresado ya existe.
// Ingrese número entero para nodo [3] : 5
// Se inserta el # 5 a la izquierda del nodo #6
// Ingrese número entero para nodo [4] : 4
// Se inserta el # 4 a la izquierda del nodo #5
// Ingrese número entero para nodo [5] : 3
// Se inserta el # 3 a la izquierda del nodo #4
// Ingrese número entero para nodo [6] : 2
// Se inserta el # 2 a la izquierda del nodo #3
// Ingrese número entero para nodo [7] : 99
// Se inserta el # 99 a la derecha del nodo # 8
// Ingrese número entero para nodo [8] : 77
// Se inserta el # 77 a la izquierda del nodo #99
// =================================
// Ordenando el árbol:
// =================================
// Orden # 2
// Orden # 3
// Orden # 4
// Orden # 5
// Orden # 6
// Orden # 8
// Orden # 77
// Orden # 99
// =================================
// Ingrese número a buscar: 6
// El número # 6 existe en la posicion [1]
// BUILD SUCCESSFUL (total time: 53 seconds)
No hay comentarios:
Publicar un comentario