Enunciado:
• 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
Ivan Barrera Olivares
package busqueda_2;
import com.sun.accessibility.internal.resources.accessibility;
public class NodoBinario {
int dato;
NodoBinario Hizq,Hder;
//Constructores
NodoBinario (int Elem){
dato=Elem;
NodoBinario Hizq, Hder = null;
}
//Insercion de un elemento
public void InsertaBinario (int Elem){
if(Elem < dato){
if (Hizq==null)
Hizq = new NodoBinario(Elem);
else
Hizq.InsertaBinario(Elem);
}
else {
if (Elem>dato){
if (Hder == null)
Hder = new NodoBinario(Elem);
else
Hder.InsertaBinario(Elem);
}
}
}
}
//Derfinicion de la clase Arbol
class Arbol{
Cola Cola = new Cola();
NodoBinario Padre;
NodoBinario Raiz;
//Constructor
public Arbol(){
Raiz=null;
}
//Insercion de un elemento en el arbol
public void InsertaNodo(int Elem){
if (Raiz ==null)
Raiz=new NodoBinario(Elem);
else
Raiz.InsertaBinario(Elem);
}
//Preorden Recursivo del arbol
public void Preorden (NodoBinario Nodo){
if (Nodo == null)
return;
else{
System.out.print(Nodo.dato+"");
Preorden(Nodo.Hizq);
Preorden(Nodo.Hder);
}
}
//PostOrden recursivo del arbol
public void PostOrden (NodoBinario Nodo){
if (Nodo==null)
return;
else{
PostOrden(Nodo.Hizq);
PostOrden(Nodo.Hder);
System.out.print(Nodo.dato + "");
}
}
//Inorden Recursivo del arbol
public void Inorden (NodoBinario Nodo){
if (Nodo==null)
return;
else{
Inorden(Nodo.Hizq);
System.out.print(Nodo.dato + "");
Inorden(Nodo.Hder);
}
}
//Busca un elemento en el arbol
void Busqueda (int Elem, NodoBinario A){
if((A==null)|(A.dato==Elem)){
System.out.print(A.dato + "Elelemnto buscado:");
return;
}
else{
if (Elem>A.dato)
Busqueda(Elem, A.Hder);
else
Busqueda(Elem, A.Hizq);
}
}
//Altura del arbol
public int Altura (NodoBinario Nodo){
int Altder = (Nodo.Hder==null? 0:1 + Altura(Nodo.Hder));
int Altizq = (Nodo.Hizq==null? 0:1 + Altura (Nodo.Hizq));
return Math.max(Altizq, Altizq);
}
//Recorrido en anchura del arbol
public void Anchura(NodoBinario Nodo){
Cola cola = new Cola();
NodoBinario T = null;
//System.out.print("El recorrido en anchura es:");
if (Nodo !=null){
cola.InsertaFinal (Nodo);
while (!(cola.VaciaLista())){
T=cola.PrimerNodo.datos;
cola.EliminaInicio();
System.out.print(T.dato + "");
if (T.Hizq!=null)
cola.InsertaFinal(T.Hizq);
if(T.Hder!=null)
cola.InsertaFinal (T.Hder);
}
}
System.out.println();
}
}
//Definicion de la Clase NodoLista
class NodosListaA{
NodoBinario datos;
NodosListaA siguiente;
//Constructor Crea un nodo del tipoObject
NodosListaA(NodoBinario valor) {
datos=valor;
siguiente=null; //siguiente con valor de nulo
}
//Constructor crea unnodo del tipo object y al siguiente nodo de la lista
NodosListaA (NodoBinario valor, NodosListaA signodo){
datos=valor;
siguiente=signodo;//siguiente se refiere al siguiente nodo
}
}
//Definicion de la clase Lista
class Cola{
NodosListaA PrimerNodo;
NodosListaA UltimoNodo;
String Nombre;
//constructor construye una lista vacia conun anombre de List
public Cola (){
this("Lista");
}
//Cosntructor
public Cola (String s){
Nombre = s;
PrimerNodo=UltimoNodo=null;
}
//retorna True si Lista Vacia
public boolean VaciaLista(){
return PrimerNodo==null;
}
//inserta un elemento al frente de la lista
public void InsertaInicio (NodoBinario ElemInser){
if (VaciaLista())
PrimerNodo=UltimoNodo=new NodosListaA(ElemInser);
else
PrimerNodo= new NodosListaA(ElemInser, PrimerNodo);
}
//inserta al final de la lista
public void InsertaFinal(NodoBinario ElemInser){
if (VaciaLista())
PrimerNodo=UltimoNodo=new NodosListaA(ElemInser);
else
UltimoNodo=UltimoNodo.siguiente=new NodosListaA(ElemInser);
}
//eliminar al inicio
public void EliminaInicio(){
if (VaciaLista())
System.out.println("No hay elementos");
//restablecer las referencias de primernodo y ultimonodo
if (PrimerNodo.equals(UltimoNodo))
PrimerNodo=UltimoNodo=null;
else
PrimerNodo=PrimerNodo.siguiente;
}
//elimina Final
public void EliminaFinal(){
if (VaciaLista())
System.out.println("No hay elementos");
//Restablecer las referencias de PrimerNodo y UltimoNodo
if (PrimerNodo.equals(UltimoNodo))
PrimerNodo=UltimoNodo=null;
else{
NodosListaA Actual=PrimerNodo;
while (Actual.siguiente != UltimoNodo)
Actual=Actual.siguiente;
UltimoNodo=Actual;
Actual.siguiente=null;
}
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package busqueda_2;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
/**
*
* @author Ivan
*/
public class Busqueda_2 {
/**
* @param args the command line arguments
*/
public static void main(String[] args) throws IOException {
java.util.Scanner leer = new Scanner(System.in);
BufferedReader entrada = new BufferedReader(new InputStreamReader(System.in));
//creando objeto del arbolito
Arbol A = new Arbol();
int b;
for (int j=0;j<6;j++)
{
System.out.println("Ingresar Datos");
b=Integer.parseInt(entrada.readLine());
A.InsertaNodo(b);
}
System.out.print("Preorden es: ");
A.Preorden(A.Raiz);
System.out.println();
System.out.print("Inorden es: ");
A.Inorden(A.Raiz);
System.out.println();
System.out.print("Postorden es: ");
A.PostOrden(A.Raiz);
System.out.println();
System.out.print("La Altura del arbol es: " + A.Altura(A.Raiz));
A.Anchura(A.Raiz);
// TODO code application logic here
}
}
No hay comentarios:
Publicar un comentario