Arbol en java

package Principal;

public class Arbol {
 class Nodo
      {
        int info;
        Nodo izq, der;
      }
      Nodo raiz;

      public Arbol() {
          raiz=null;
      }
      
      public void insertar (int info)
      {
          Nodo nuevo;
          nuevo = new Nodo ();
          nuevo.info = info;
          nuevo.izq = null;
          nuevo.der = null;
          if (raiz == null)
              raiz = nuevo;
          else
          {
              Nodo anterior = null, reco;
              reco = raiz;
              while (reco != null)
              {
                  anterior = reco;
                  if (info < reco.info)
                      reco = reco.izq;
                  else
                      reco = reco.der;
              }
              if (info < anterior.info)
                  anterior.izq = nuevo;
              else
                  anterior.der = nuevo;
          }
      }


      private void imprimirPre (Nodo reco)
      {
          if (reco != null)
          {
              System.out.print(reco.info + " ");
              imprimirPre (reco.izq);
              imprimirPre (reco.der);
          }
      }

      public void imprimirPre ()
      {
          imprimirPre (raiz);
          System.out.println();
      }

      private void imprimirEntre (Nodo reco)
      {
          if (reco != null)
          {    
              imprimirEntre (reco.izq);
              System.out.print(reco.info + " ");
              imprimirEntre (reco.der);
          }
      }

      public void imprimirEntre ()
      {
          imprimirEntre (raiz);
          System.out.println();
      }


      private void imprimirPost (Nodo reco)
      {
          if (reco != null)
          {
              imprimirPost (reco.izq);
              imprimirPost (reco.der);
              System.out.print(reco.info + " ");
          }
      }


      public void imprimirPost ()
      {
          imprimirPost (raiz);
          System.out.println();
      }

      public static void main (String [] ar)
      {
          Arbol abo = new Arbol ();
          abo.insertar (100);
          abo.insertar (50);
          abo.insertar (25);
          abo.insertar (75);
          abo.insertar (150);
          System.out.println ("Impresion preorden: ");
          abo.imprimirPre ();
          System.out.println ("Impresion entreorden: ");
          abo.imprimirEntre ();
          System.out.println ("Impresion postorden: ");
          abo.imprimirPost ();        
      }      
}

Explicación

public void insertar (int info)
      {
          Nodo nuevo;
          nuevo = new Nodo ();
          nuevo.info = info;
          nuevo.izq = null;
          nuevo.der = null;
          if (raiz == null)
              raiz = nuevo;
          else
          {
              Nodo anterior = null, reco;
              reco = raiz;
              while (reco != null)
              {
                  anterior = reco;
                  if (info < reco.info)
                      reco = reco.izq;
                  else
                      reco = reco.der;
              }
              if (info < anterior.info)
                  anterior.izq = nuevo;
              else
                  anterior.der = nuevo;
          }
      }

Creamos un nodo y disponemos los punteros izquierda y derecho a null, guardamos la información que llega al método en el nodo. Si el árbol está vacío, apuntamos raíz al nodo creado; en caso de no estar vacío, dentro de una estructura repetitiva vamos comparando info con la información del nodo, si info es mayor a la del nodo descendemos por el subárbol derecho en caso contrario descendemos por el subárbol izquierdo. Cuando se encuentra un subárbol vacío insertar el nodo en dicho subárbol. Para esto llevamos un puntero anterior dentro del while

private void imprimirPre (Nodo reco)
      {
          if (reco != null)
          {
              System.out.print(reco.info + " ");
              imprimirPre (reco.izq);
              imprimirPre (reco.der);
          }
      }

      public void imprimirPre ()
      {
          imprimirPre (raiz);
          System.out.println();
      }

El método imprimirPre(), es decir el no recursivo se encarga de llamar al método recursivo pasando la dirección del nodo raiz. El método recursivo void imprimirPre (Nodo reco) lo primero que verifica con un if si reco está apuntando a un nodo (esto es verdad si reco es distinto a null), en caso afirmativo ingresa al bloque del if y realiza: - Visitar la raiz. - Recorrer el subárbol izquierdo en pre-orden. - Recorrer el subárbol derecho en pre-orden. La visita en este caso es la impresión de la información del nodo y los recorridos son las llamadas recursivas pasando las direcciones de los subárboles izquierdo y derecho. Los algoritmos de los recorridos en entreorden y postorden son similares. La diferencia es que la visita la realizamos entre las llamadas recursivas en el recorrido en entre orden:

 private void imprimirEntre (Nodo reco)
      {
          if (reco != null)
          {    
              imprimirEntre (reco.izq);
              System.out.print(reco.info + " ");
              imprimirEntre (reco.der);
          }
      }

y por último en el recorrido en postorden la visita la realizamos luego de las dos llamadas recursivas:

  private void imprimirPost (Nodo reco)
      {
          if (reco != null)
          {
              imprimirPost (reco.izq);
              imprimirPost (reco.der);
              System.out.print(reco.info + " ");
          }
      }

Colas (FIFO)

La Cola es una estructura de datos donde la inserción de ítem se hace en un final (el fin de la cola) y la recuperación/borrado de elementos se hace en el otro final (el inicio de la cola). Como el primer elemento insertado es el primero en ser recuperado, los desarrolladores se refieren a estas colas como estructuras FIFO (first-in, first-

).

Las colas son muy útiles en varios escenarios de programación, entre los que se encuentran:

• Temporización de Threads: 
  Una JVM o un sistema operativo subyacente podrían establecer varias colas para coincidir con diferentes prioridades de los threads. La información del thread se bloquea porque todos los threads con una prioridad dada se almacenan en una cola asociada.
• Trabajos de impresión: 
  Como una impresora normalmente es más lenta que un ordenador, un sistema operativo maneja los trabajos de impresión en un subsistema de impresión, que inserta esos trabajos de impresión en una cola. El primer trabajo en esa cola se imprime primero, y así sucesivamente.

• Operaciones Básicas
• Crear: se crea la cola vacía.
• Encolar: (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
• Desencolar: (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
• Frente: (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.

Tipos de colas

• Colas circulares (anillos): en las que el último elemento y el primero están unidos.

• Colas de prioridad: En ellas, los elementos se atienden en el orden indicado por una prioridad asociada a cada uno. Si varios elementos tienen la misma prioridad, se atenderán de modo convencional según la posición que ocupen. Hay 2 formas de implementación:

1. Añadir un campo a cada nodo con su prioridad. Resulta conveniente mantener la cola ordenada por orden de prioridad.
2. Crear tantas colas como prioridades haya, y almacenar cada elemento en su cola.

• Bicolas: son colas en donde los nodos se pueden añadir y quitar por ambos extremos; se les llama DEQUE (Double Ended QUEue). Para representar las bicolas lo podemos hacer con un array circular con Inicio y Fin que apunten a cada uno de los extremos. Hay variantes:

• Bicolas de entrada restringida: Son aquellas donde la inserción sólo se hace por el final, aunque podemos eliminar al inicio ó al final.

• Bicolas de salida restringida: Son aquellas donde sólo se elimina por el final, aunque se puede insertar al inicio y al final.
• 
• Ejemplo:

public class Cola 
{
    private Object[] cola;
    private int frente;
    private int fin;
    
    public Cola(int tamanio)
    {
        cola = new Object[tamanio];
        frente = fin = -1;
    }
    
    public boolean isEmpty()
    {
        return frente == fin;
    }
    
    public boolean isFull()
    {
        return fin == cola.length-1;
    }
    
    
    public void insert(Object elemento)
    {
        if(isFull())
            System.out.println("La cola esta llena, elimine datos!");
        else
            cola[++fin] = elemento;
    }
    
    public Object remove()
    {
        if(isEmpty())
        {
            System.out.println("La cola esta vacia, inserte datos!");
            return "Cola vacia";
        }
        else
            return cola[++frente];
    }
    
    
    public void print()
    {
        if(isEmpty())
            System.out.println("La cola esta vacia!");
        else if(frente == -1)
        {
            for(int i = 0; i <= fin; i++)
            {
                System.out.println(cola[i]);
            }
        }
        else
        {
            for(int j = frente; j <= fin; j++)
            {
                System.out.println(cola[j]);
            }
        }
    }
}

• Principal:

public static void main(String[] args)
    {
        Cola cola = new Cola(4);
        cola.print();
        cola.remove();
        cola.insert("Hola");
        cola.insert(3);
        cola.insert("java");
        cola.insert(5);
        cola.insert(8);
        cola.remove();
        cola.remove();
        cola.remove();
        cola.remove();
        cola.remove();
        
    }
}