sábado, 20 de abril de 2013

Tarea 3 - Algoritmo básico de búsqueda en Java (Carlos Melo)

Se define un árbol binario como un conjunto finito de elementos (nodos) que bien esta vacío o esta formado por una raíz con dos arboles binarios disjuntos, es decir, dos descendientes directos llamados subarbol izquierdo y subarbol derecho.
Los árboles binarios (también llamados de grado 2 )tienen una especial importancia.
Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.

Arbol binario de búsqueda

Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subarbol izquierdo, y menor que todas las claves del subarbol derecho se dice que este árbol es un árbol binario de búsqueda.


/************************************ 
// clase NodoArbolBinario 
//************************************ 

public class NodoArbolBinario { 
private int info = 0; 
private NodoArbolBinario derecho = null; 
private NodoArbolBinario izquierdo = null; 

public NodoArbolBinario ( int x ) { 
this.info = x; 
this.derecho = null; 
this.izquierdo = null; 
} 

public NodoArbolBinario getDerecho(){ 
return this.derecho; 
} 

public void setDerecho(NodoArbolBinario derecho){ 
this.derecho = derecho; 
} 


public int getInfo(){ 
return this.info; 
} 

public void setInfo(int info){ 
this.info = info; 
} 


public NodoArbolBinario getIzquierdo(){ 
return this.izquierdo; 
} 

public void setIzquierdo(NodoArbolBinario izquierdo){ 
this.izquierdo = izquierdo; 
} 
} 

//************************************ 
// clase ArbolBinario 
//************************************ 

public class ArbolBinario { 
private NodoArbolBinario raiz = null; 
private NodoArbolBinario padre = null; 
private boolean centinela = false, sw = false; 

public ArbolBinario () { 
} 

public NodoArbolBinario adicionar( int x ) { 
NodoArbolBinario p = new NodoArbolBinario ( x ), r = null; 
if ( this.raiz == null ) { 
this.raiz = p; 
} 
else { 
NodoArbolBinario q = raiz; 
while ( q != null ) { 
r = q; 
if ( x >= q.getInfo() ) { 
q = q.getDerecho(); 
} 
else { 
q = q.getIzquierdo(); 
} 
} 
} 
if ( x >= r.getInfo() ) { 
r.setDerecho( p ); 
} 
else { 
r.setIzquierdo( p ); 
} 
return p; 
} 

public ArbolBinario arbolSuma(ArbolBinario tree){ 
ArbolBinario res = new ArbolBinario(); 
arbolSuma(res,tree.raiz); 
return res; 
} 

private int arbolSuma(ArbolBinario res, NodoArbolBinario p){ 
if ( p == null ){ 
return 0; 
} 
else { 
int sum = p.getInfo(); 
NodoArbolBinario aux = res.adicionar(sum); 
sum += arbolSuma(res, p.getIzquierdo() ); 
sum += arbolSuma(res, p.getDerecho() ); 
aux.setInfo(sum); 
return sum; 
} 
} 
} 
Publicado por en No hay comentarios:

viernes, 19 de abril de 2013

Tarea - Algoritmo básico de búsqueda en Java



lProblema de la aspiradora: 

»Se dispone de una aspiradora con acceso a dos habitaciones y con la capacidad de aspirar basura

  • »8 posibles estados
  • –2 estados objetivo
  • »3 posibles acciones
  • »Mundo: 2 posibles posiciones
  • –Sucio - limpio 


lEstado inicial: multiestado

lCada operador obtiene un multiestado a partir de otro multiestado.



 
Solución:
package com.carlos.algoritmo;

/**
 *
 * @author principal
 */
//Se define el nodo de un arbol, este tiene un valor y puede tener 1 nodo derecho y/o 1 nodo izquierdo
 public class Estado {
    private boolean suciedadHabitacionIzq; //se define true si esta sucio en la habitacion
    private boolean suciedadHabitacionDer;
    private int posAspiradora; // si es 0 habitacion izq. si es 1 esta en habitaciòn der.
    //public Estado() { //constructor
    //}
   
    public Estado() { //Se define un estado segun los valores
        this.suciedadHabitacionIzq = true;
        this.suciedadHabitacionDer = true;
        this.posAspiradora = 0;
    }
   
    public Estado(boolean suciedadHabitacionIzq, boolean suciedadHabitacionDer, int posAspiradora) { //Se define un estado segun los valores
        this.suciedadHabitacionIzq = suciedadHabitacionIzq;
        this.suciedadHabitacionDer = suciedadHabitacionDer;
        this.posAspiradora = posAspiradora;
    }

    public void setSuciedadHI(boolean sucio){ //Def. suciedad habitaciòn inquierda
        this.suciedadHabitacionIzq=sucio;
    }
   
    public void setSuciedadHD(boolean sucio){
        this.suciedadHabitacionDer=sucio;
    }
   
    public boolean getSuciedadHI() {
        return suciedadHabitacionIzq;
    }
   
    public boolean getSuciedadHD() {
        return suciedadHabitacionDer;
    }
   
    public void setPosAspiradora(int valor) {
        this.posAspiradora = valor;
    }

    public void succiona(){ //succiona la posicion actual
       if (this.posAspiradora==0)
         {  this.suciedadHabitacionIzq=false; //limpia habitacion izquierda
        
             System.out.println("Limpia habitaciòn izquierda");        
         }
       else
         {  this.suciedadHabitacionDer=false; //limpia hab. derecha
             System.out.println("Limpia habitaciòn derecha");
         }
    }
   
    public void insertar() //q es esl estado inicial
        {
            System.out.println("Comienza metodo insertar");
         while((this.suciedadHabitacionIzq==true)||(this.suciedadHabitacionDer==true)){ //Mientras no sea estado final
             if  (this.posAspiradora==0) {  //si esta en la habitacion 0-izquierda
                 if (this.suciedadHabitacionIzq==true) { //si esta sucia la habitacion izquierda..
                     this.succiona(); //limpia habitacion
                     //mover hacia la derecha
                     this.setPosAspiradora(1);
                     System.out.println("Aspiradora se mueva a la habitaciòn de la derecha");
                     //this.insertar();
                 }  
             } 
             else {
               
                 if (this.suciedadHabitacionDer==true) { //si esta sucia la habitacion derecha..
                     this.succiona(); //limpia habitacion
                     //mover hacia la izquierda
                     //mover hacia la derecha
                     this.setPosAspiradora(0);
                     System.out.println("Aspiradora se mueva a la habitaciòn de la izquierda");
                     //this.insertar();
                 }  
             }
         } //fin while
       
            System.out.println("Se ha llegado al estado final, las habitaciones estan limpias");
        }
}
/////FIN CLASE
////
package com.carlos.algoritmo;

/**
 *
 * @author Carlos
 */ 
public class Algoritmo {
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Estado estadoinicial= new Estado(); //crea un nuevo estado con las habitaciones sucias
        System.out.println("Creado el estado incial");
        estadoinicial.insertar();
    }
}

SALIDA POR PANTALLA:

Publicado por en 1 comentario:

Tarea N°3 

·  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.  

Arbol Binario 

Un árbol binario es una estructura de datos en la que los nodos siempre tienen nodos hijos, tanto a su izquierda como su derecha, no pueden tener mas de dos hijos cada nodo, si un nodo no almacena ningún dato, es decir es null, se le llama nodo externo, en otro caso a este nodo hijo se le llamara nodo interno, uno de los usos comunes de un árbol binario es para búsquedas.

A continuacion se muestra un programa de árbol binario en java, compuesto por tres clases una llamada nodo en la cual se aloja la estructura de datos, otra llamada árbol la cual aloja los métodos a utilizar y una llamada main que sera la clase principal que aloje los métodos principales.

CLASE NODO 
class nodo
{
    int dato;
    nodo der;
    nodo izq;
    nodo(int dat)
    {
        this.dato=dat;
        this.der=null;
        this.izq=null;
    }
}

CLASE ARBOL

public class arbol
{
    nodo raiz=null;
    public boolean tieneraiz()
    {
        if(raiz==null) return false;
        else return true;
    }

    public arbol alta(int dat)
    {
        if(!tieneraiz())
        {
            nodo nuevo=new nodo(dat);
            raiz=nuevo;
        }
        else
        {
            boolean izq;
            nodo actual=raiz;
            while(true)
            {
                if(actual.dato<dat) izq=false;
                else izq=true;
                if(!izq)
                {
                    if(actual.der==null)
                    {
                        nodo nuevo=new nodo(dat);
                        actual.der=nuevo;
                        break;
                    }
                    else actual=actual.der;
                }
                else
                {
                    if(actual.izq==null)
                    {
                        nodo nuevo=new nodo(dat);
                        actual.izq=nuevo;
                        break;
                    }
                    else actual=actual.izq;
                }
            }
        }return this;
    }

    public boolean baja(int dat)
    {
        nodo actual=raiz, anterior=raiz, temp;
        while(true)
        {
            if(actual==null) break;
            if(actual.dato==dat) break;
            anterior=actual;
            if(actual.dato<dat) actual=actual.der;
            else actual=actual.der;
        }
        if(actual==null) return false;
        else
        {
            if(actual==raiz)
            {
                temp=actual.izq;
                raiz=raiz.der;
                anterior=raiz;
            }
            else
            if (anterior.der == actual)
            {
                temp=actual.izq;
                anterior=actual.der;
            }
            else
            {
             temp=actual.izq;
             anterior.der=actual.izq;
            }
            actual=new nodo();
            while(actual.izq!=null)
                actual=actual.izq;
            actual.izq=temp;
            return true;
        }
    }

    public void imprimirpreorden()
    {
        ayudantePreorden(raiz);
    }

    public void ayudantePreorden(nodo dat)
    {
        if(dat==null)
                return;
        System.out.printf("%d ",dat.dato);
        ayudantePreorden(dat.der);
        ayudantePreorden(dat.izq);
    }

    public void impririnorden(nodo dat)
    {
        if(dat!=null)
        {
            impririnorden(dat.izq);
            System.out.println(" "+dat.dato);
            impririnorden(dat.der);
        }
    }
}

CLASE MAIN

public class Main {

    
    public static void main(String[] args) {
        java.util.Scanner leer=new java.util.Scanner(System.in);
        arbol x=new arbol();
        int z;
        System.out.print("Ingrese el numero de Datos a capturar: ");
        z=leer.nextInt();
        for(int i=1; i<=z;i++){
        int m;
        System.out.println("Ingrese Dato "+i+":  ");m=leer.nextInt();
        x.alta(m);
        }
        System.out.println("Valores Capturados en PreOrden:");
     x.imprimirpreorden();
        int q;
        System.out.print("\nIngrese dato a borrar: ");q=leer.nextInt();
     x.baja(q);
        System.out.println("\nDespues de borrar el dato "+q+" :");
     x.imprimir();
    }

}

Publicado por en No hay comentarios:
Suscribirse a: Entradas (Atom)