Arbol binario

Un árbol binario es un árbol de orden 2, es decir tiene solo dos hijos. Se puede crear una estructura de árbol binario en Java y es lo que se va a explicar a continuación. El árbol binario tiene dos hijos (izquierda, y derecha), a su vez un árbol puede ser el conjunto de varios arboles por lo que se puede unir dos arboles, formando un árbol nuevo. Se va a tener tres clases, Arbol, Nodo y el Main


En la clase Nodo se empieza se declara 3 atributos de la clase: dato, izquierda y derecha.

  private Object dato;
    private Object value;
    private String key;
    private Nodo left;
    private Nodo right;
    
    public Nodo(String key,Object value){
        this.key = key;
        this.value = value;
        this.left = this.right = null;
    }

A continuación en la clase Arbol se declara un atributo raíz

  
  private Nodo raiz;

Los Nodos tiene los siguientes métodos:

    public void setIzq(String key, Object value) {
        this.setLeft(new Nodo(key, value));
    }

    public void setDer(String key, Object value) {
        this.setRight(new Nodo(key, value));
    }
    

El árbol puede de igual forma ingresar a la derecha o a la izquierda de la raíz:

    public void setIzq(String key, Object value) {
        this.raiz.setLeft(new Nodo(key, value));
    }

    public void setDer(String key, Object value) {
        this.raiz.setRight(new Nodo(key, value));
    }

Para imprimir el árbol de forma prefija, infija y postfija:

    private void prefijo(Nodo a) {
        if (a != null) {
            System.out.println(a.getValue());
            prefijo(a.getLeft());
            prefijo(a.getRight());
        }
    }

    public void prefijo() {
        prefijo(this.raiz);
    }
private void infijo(Nodo a) {
        if (a != null) {
            prefijo(a.getLeft());
            System.out.println(a.getValue());
            prefijo(a.getRight());
        }
    }

    public void infijo() {
        infijo(this.raiz);
    }

    private void postfijo(Nodo a) {
        prefijo(a.getLeft());
        prefijo(a.getRight());
        System.out.println(a.getValue());
    }

    public void postfijo() {
        postfijo(this.raiz);
    }

Y también puede unir dos árboles

    public Arbol joinDer(Arbol b) {
        Arbol nuevo = new Arbol("c", "raiz c");
        nuevo.raiz.setRight(b.raiz);
        nuevo.raiz.setLeft(this.raiz);
        return nuevo;
    }

    public Arbol joinIzq(Arbol b) {
        Arbol nuevo = new Arbol("c", "raiz c");
        nuevo.raiz.setRight(this.raiz);
        nuevo.raiz.setLeft(b.raiz);
        return nuevo;
    }

La clase nodo quedaría de la siguiente manera:

/**
 *
 * @author robertoarmas
 */
public class Nodo {
    
    private Object value;
    private String key;
    private Nodo left;
    private Nodo right;
    
    public Nodo(String key,Object value){
        this.key = key;
        this.value = value;
        this.left = this.right = null;
    }

    public Object getValue() {
        return value;
    }

    public void setValue(Object value) {
        this.value = value;
    }

    public Nodo getLeft() {
        return left;
    }

    public void setLeft(Nodo left) {
        this.left = left;
    }

    public Nodo getRight() {
        return right;
    }

    public void setRight(Nodo right) {
        this.right = right;
    }

    public String getKey() {
        return key;
    }

    public void setKey(String key) {
        this.key = key;
    }
    
    public void setIzq(String key, Object value) {
        this.setLeft(new Nodo(key, value));
    }

    public void setDer(String key, Object value) {
        this.setRight(new Nodo(key, value));
    }
    
}

La clase Arbol.java

/**
 *
 * @author robertoarmas
 */
public class Arbol {

    private Nodo raiz;

    public Arbol() {
        this.raiz = null;
    }
    
    private Arbol(Nodo nodo){
        this.raiz = nodo;
    }

    public Arbol(String key, Object value) {
        this.raiz = new Nodo(key, value);
    }

    private void prefijo(Nodo a) {
        if (a != null) {
            System.out.println(a.getValue());
            prefijo(a.getLeft());
            prefijo(a.getRight());
        }
    }

    public void prefijo() {
        prefijo(this.raiz);
    }

    private void infijo(Nodo a) {
        if (a != null) {
            prefijo(a.getLeft());
            System.out.println(a.getValue());
            prefijo(a.getRight());
        }
    }

    public void infijo() {
        infijo(this.raiz);
    }

    private void postfijo(Nodo a) {
        prefijo(a.getLeft());
        prefijo(a.getRight());
        System.out.println(a.getValue());
    }

    public void postfijo() {
        postfijo(this.raiz);
    }
    
    public Nodo getIzq(){
        return this.raiz.getLeft();
    }
    
    public Nodo getDer(){
        return this.raiz.getRight();
    }
    
    public Object getValueDer(){
        return this.raiz.getRight().getValue();
    }
    
    public Object getValueIzq(){
    return this.raiz.getLeft().getValue();
    }

    public void setIzq(String key, Object value) {
        this.raiz.setLeft(new Nodo(key, value));
    }

    public void setDer(String key, Object value) {
        this.raiz.setRight(new Nodo(key, value));
    }

    public Arbol joinDer(Arbol b) {
        Arbol nuevo = new Arbol("c", "raiz c");
        nuevo.raiz.setRight(b.raiz);
        nuevo.raiz.setLeft(this.raiz);
        return nuevo;
    }

    public Arbol joinIzq(Arbol b) {
        Arbol nuevo = new Arbol("c", "raiz c");
        nuevo.raiz.setRight(this.raiz);
        nuevo.raiz.setLeft(b.raiz);
        return nuevo;
    }

}

Y la clase Main.java

 Arbol b = new Arbol("a2", "raiz b");
        
        Arbol a = new Arbol("a","raiz a");
        a.setIzq("b", "hola");
        a.setDer("d", "mundo");
        a.getIzq().setIzq("c", "hijo de b");
        System.out.println(" ++++++++++++++++++++++++++++++PREFIJO ++++++++++++++++++++++++++++++");
        a.prefijo(); // Imrpimira
        System.out.println(" ++++++++++++++++++++++++++++++INFJO  ++++++++++++++++++++++++++++++");
        a.infijo();
        System.out.println(" ++++++++++++++++++++++++++++++POSTFIJO  ++++++++++++++++++++++++++++++");
        a.postfijo();
        System.out.println(" ++++++++++++++++++++++++++++++");
        System.out.println(a.getValueIzq()); // hola
        System.out.println(" ++++++++++++++++++++++++++++++");
        Arbol c = a.joinDer(b);
        c.prefijo();

De este modo nos da una salida:

 ++++++++++++++++++++++++++++++PREFIJO ++++++++++++++++++++++++++++++
raiz a
hola
hijo de b
mundo
 ++++++++++++++++++++++++++++++INFJO  ++++++++++++++++++++++++++++++
hola
hijo de b
raiz a
mundo
 ++++++++++++++++++++++++++++++POSTFIJO  ++++++++++++++++++++++++++++++
hola
hijo de b
mundo
raiz a
 ++++++++++++++++++++++++++++++
hola
 ++++++++++++++++++++++++++++++
raiz c
raiz a
hola
hijo de b
mundo
raiz b

Colas en Java

¿Qué es una cola?

Una cola es una estructura de datos que permite ingresar los datos en nodos, estructurados en forma de una cola.

Como se observa en la figura, el primer nodo en entrar es el primero en salir (FIFO: First In First Out)

Para implementarlo en Java, se crea una clase Cola y una clase Nodo, en donde nodo tiene un Nodo siguiente y un Objeto dato. La clase Cola tiene base(Nodo) = ultimo y cima(Nodo) = primero, y los métodos: push(insertar al final), pop(sacar primero) y peek(mostar primero).

Insertar a la cola:

1. Se crea un nuevo nodo con el dato.
2. Si primero esta vacío entonces primero y último es igual nuevo nodo y continuar con paso 4.
3. Si la cola no esta vacía entonces el siguiente del último es igual al nuevo nodo y nuevo último es igual al nuevo nodo.
4. Fin.

Sacar primero:

1. Nodo auxiliar es igual a primero.
2. Primero es igual al siguiente del primero.
3. Retornar primero.
4. Fin.

Mostar primero

1. Retornar primero.
2. Fin.

Nodo.java

/**
 *
 * @author robertoarmas
 */
public class Nodo{
    
    private Object dato;
    private Nodo siguiente;
     
    public Nodo(Object dato){
        this.dato = dato;
        this.siguiente = null;
    }

    public Object getDato() {
        return dato;
    }

    public void setDato(Object dato) {
        this.dato = dato;
    }

    public Nodo getSiguiente() {
        return siguiente;
    }

    public void setSiguiente(Nodo siguiente) {
        this.siguiente = siguiente;
    }
    
}

Cola.java

/**
 *
 * @author robertoarmas
 */
public class Cola{
 
     private Nodo cima;
     private Nodo base;
      
     public Cola(){
          this.cima = null;
     }
     
     public void push(Object dato){
        Nodo nuevo = new Nodo(dato);
        if(this.cima == null){
            this.cima = this.base = nuevo;
            return;
        }
        this.base.setSiguiente(nuevo);
        this.base = nuevo;
     }
     
     public Object peek(){
         return this.cima.getDato();
     }
     
     public Object pop(){
        Nodo aux = this.cima;
        this.cima = aux.getSiguiente();
        return aux.getDato();
     }
     
     public void print(){
         Nodo aux = this.cima;
         while(aux != null){
             System.out.println(aux.getDato());
             aux = aux.getSiguiente();
         }
     }
     
 }
 

Main.java

/**
 *
 * @author robertoarmas
 */
public class Main {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        Cola c = new Cola();
        c.push("Primero en entrar Primero en salir");
        c.push("Otro dato despues");
        c.push("ultimo dato");
        c.print();
        System.out.println("+++++++++++++++++++++++++");
        System.out.println("Mostrar cima:" + c.peek());
        System.out.println("+++++++++++++++++++++++++");
        System.out.println("Sacar cima:" + c.pop());
        System.out.println("Nueva cima:" + c.peek());
        System.out.println("+++++++++++++++++++++++++");
        System.out.println("Sacar:" + c.pop());
        System.out.println("--------------------------");
        System.out.println("Imprimir cola");
        c.print();
       
    }
    
}

Salida:

Primero en entrar Primero en salir
Otro dato despues
ultimo dato
+++++++++++++++++++++++++
Mostrar cima:Primero en entrar Primero en salir
+++++++++++++++++++++++++
Sacar cima:Primero en entrar Primero en salir
Nueva cima:Otro dato despues
+++++++++++++++++++++++++
Sacar:Otro dato despues
--------------------------
Imprimir cola
ultimo dato

Descargar el proyecto en GitHub