arboles

tipos de recorrido

Recorrido en preorden
En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha.
En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4

Recorrido en postorden
En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda, nodo derecha, nodo raiz. En el árbol de la figura el recorrido en postorden sería: 2, 5, 11, 6, 7, 4, 9, 5 y 2.

Recorrido en inorden
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo izquierda,nodo raiz,nodo derecha. En el árbol de la figura el recorrido en inorden sería: 2, 7, 5, 6, 11, 2, 5, 4, 9.

Recorridos en amplitud (o por niveles)
En este caso el recorrido se realiza en orden por los distintos niveles del árbol. Así, se comenzaría tratando el nivel 1, que sólo contiene el nodo raíz, seguidamente el nivel 2, el 3 y así sucesivamente. En el árbol de la figura el recorrido en amplitud sería: 2, 7, 5, 2, 6, 9, 5, 11 y 4.
Al contrario que en los métodos de recorrido en profundidad, el recorrido por niveles no es de naturaleza recursiva. Por ello, se debe utilizar una cola para recordar los subárboles izquierdos y derecho de cada nodo.
El esquema algoritmo para implementar un recorrido por niveles es exactamente el mismo que el utilizado en la versión iterativa del recorrido en preorden pero cambiando la estructura de datos que almacena los nodos por una cola

arbol genealogico

raiz:yo
padres: yo, mama, papa
hermanos: abuelap,abuelop, abuela, abuelom, mama,papa
hijos: mama, papa, abuelop, abuelap, abuelom, abuelam
hojas: abuelop, abuelap, abuelom, abuelam
nivel:3
LCI: 1*1+2*2+3*4=17
LCE:2*3=6
recorridos:
preorden: abuelam, mama, yo, abuelop, papa, abuelap, abuelop
postorden: abuelam, abuelom, mama, abuelap, abuelom, papa, yo
inorden: abuelam, mama, abuelom,yo, abuelap, papa, abuelop
arbol general a binario

raiz:A
padres: A,B,E,C,G,M,D,H,I,J
hermanos:E,C D,F O,K
hijos: B,C,D,E,F,G,H,I,J,K,L,M,N,O
hojas: D,F,N,O,K
nivel: 8
LCI: 1*1+2*1+3*2+4*4+5*2+6*2+7*1+8*2=70
LCE:10*2=20
recorridos:
preorden: A,B,E,L,F,C,G,M,N,D,H,I,J,O,K
postorden: L,F,E,B,N,M,G,C,O,K,J,I,JHD,A
inorden: L,E,F,B,A,M,N,G,C,O,J,K,I,H,D

de bosque a binario

raiz: A
padres: A,B,C,D,F,G,H,J,K,L,M,N,O,Q,R,T
hermanos: no hay
hijos: B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U
hojas:S,U,P,I,E
nivel:10
LCI:1*1+2*2+3*2+4*3+5*4+6*4+7*3+8*3+9*1+10*1=131

ejemplo de un programa de arboles

package javaapplication3;

import java.awt.*;
import java.awt.event.*;
import javax.swing.*;
import javax.swing.tree.*;
import java.util.*;
public class SimpleTree
{  public static void main(String[] args)
   {  JFrame frame = new SimpleTreeFrame();
      frame.show();
   }
}
class SimpleTreeFrame extends JFrame
{
   DefaultMutableTreeNode root = new DefaultMutableTreeNode("Mundo");
   DefaultMutableTreeNode arge = new DefaultMutableTreeNode("Argentina");
   DefaultMutableTreeNode sant = new DefaultMutableTreeNode("Santa Fe");
   DefaultMutableTreeNode rafa = new DefaultMutableTreeNode("Rafaela");
   DefaultMutableTreeNode rosa = new DefaultMutableTreeNode("Rosario");
   DefaultMutableTreeNode safe = new DefaultMutableTreeNode("Santa Fe");
   DefaultMutableTreeNode vena = new DefaultMutableTreeNode("Venado Tuerto");
   DefaultMutableTreeNode vill = new DefaultMutableTreeNode("Villa Constitucion");
   DefaultMutableTreeNode cord = new DefaultMutableTreeNode("Cordoba");
   DefaultMutableTreeNode codo = new DefaultMutableTreeNode("Cordoba");
   DefaultMutableTreeNode cbro = new DefaultMutableTreeNode("Cura Brochero");
   DefaultMutableTreeNode rcua = new DefaultMutableTreeNode("Rio Cuarto");
   DefaultMutableTreeNode chac = new DefaultMutableTreeNode("Chaco");
   DefaultMutableTreeNode resi = new DefaultMutableTreeNode("Resistencia");
   DefaultMutableTreeNode vang = new DefaultMutableTreeNode("Villa Angela");
   DefaultMutableTreeNode chil = new DefaultMutableTreeNode("Chile");
   DefaultMutableTreeNode regi = new DefaultMutableTreeNode("Region Metropolitana");
   DefaultMutableTreeNode schi = new DefaultMutableTreeNode("Santiago de Chile");
   public SimpleTreeFrame()
   {  setTitle("SimpleTree");
      setSize(300, 200);
      addWindowListener(new WindowAdapter()
         {  public void windowClosing(WindowEvent e)
            {  System.exit(0);
            }
         } );
      root.add(arge);                                                   // Enlazado de nodos
      arge.add(sant);                                                   // Enlazado de nodos
      sant.add(rafa);                                                   // Enlazado de nodos
      sant.add(rosa);                                                   // Enlazado de nodos
      sant.add(safe);                                                   // Enlazado de nodos
      sant.add(vena);                                                   // Enlazado de nodos
      sant.add(vill);                                                   // Enlazado de nodos
      arge.add(cord);                                                   // Enlazado de nodos
      cord.add(codo);                                                   // Enlazado de nodos
      cord.add(cbro);                                                   // Enlazado de nodos
      cord.add(rcua);                                                   // Enlazado de nodos
      arge.add(chac);                                                   // Enlazado de nodos
      chac.add(resi);                                                   // Enlazado de nodos
      chac.add(vang);                                                   // Enlazado de nodos
      root.add(chil);                                                   // Enlazado de nodos
      chil.add(regi);                                                   // Enlazado de nodos
      regi.add(schi);                                                   // Enlazado de nodos
      JTree tree = new JTree(root);
      Container contentPane = getContentPane();
      contentPane.add(new JScrollPane(tree));
      Enumeration hijos = sant.children();                              // Enumeracion de hijos
      while ( hijos.hasMoreElements() )                                 // Enumeracion de hijos
      {                                                                 // Enumeracion de hijos
        System.err.println("Hijos de Santa Fe : "+hijos.nextElement()); // Enumeracion de hijos
      }                                                                 // Enumeracion de hijos
      boolean hoja = vena.isLeaf();                                     // Consulta Hoja
      System.err.println("Es Venado Tuerto hoja : "+hoja);              // Consulta Hoja
      Enumeration breadth = root.breadthFirstEnumeration();             // Enumeracion Nodos
      while ( breadth.hasMoreElements() )                               // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Breadth First : "+breadth.nextElement());   // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
      Enumeration depth = root.depthFirstEnumeration();                 // Enumeracion Nodos
      while ( depth.hasMoreElements() )                                 // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Depth First : "+depth.nextElement());       // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
      Enumeration preorder = root.preorderEnumeration();                // Enumeracion Nodos
      while ( preorder.hasMoreElements() )                              // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Pre Order : "+preorder.nextElement());      // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
      Enumeration postorder = root.postorderEnumeration();              // Enumeracion Nodos
      while ( postorder.hasMoreElements() )                             // Enumeracion Nodos
      {                                                                 // Enumeracion Nodos
        System.err.println("Post Order : "+postorder.nextElement());    // Enumeracion Nodos
      }                                                                 // Enumeracion Nodos
   }
}

bibliografia
arboles
tipos de recorridos

colas

Una cola es una estructura de datos, caracterizada por ser una secuencia de elementos en la que la operación de inserción push se realiza por un extremo y la operación de extracción pop por el otro. También se le llama estructura FIFO (del inglés First In First Out), debido a que el primer elemento en entrar será también el primero en salir.
Las colas se utilizan en sistemas informáticos, transportes y operaciones de investigación (entre otros), dónde los objetos, personas o eventos son tomados como datos que se almacenan y se guardan mediante colas para su posterior procesamiento. Este tipo de estructura de datos abstracta se implementa en lenguajes orientados a objetos mediante clases, en forma de listas enlazadas.

La particularidad de una estructura de datos de cola es el hecho de que sólo podemos acceder al primer y al último elemento de la estructura. Así mismo, los elementos sólo se pueden eliminar por el principio y sólo se pueden añadir por el final de la cola.

Ejemplos de colas en la vida real serían: personas comprando en un supermercado, esperando para entrar a ver un partido de béisbol, esperando en el cine para ver una película, una pequeña peluquería, etc. La idea esencial es que son todos líneas de espera.

operaciones con colas

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.

Aplicaciones de las Colas

Las Colas también se utilizan en muchas maneras en los sistemas operativos para planificar el uso de los distintos recursos de la computadora. Uno de estos recursos es la propia CPU (Unidad Central de Procesamiento).
Si esta trabajando en una sistema multiusuario, cuando le dice a la computadora que ejecute un programa concreto, el sistema operativo añade su petición a su "cola de trabajo".
Cuando su petición llega al frente de la cola, el programa solicitado pasa a ejecutarse. Igualmente, las colas se utilizan para asignar tiempo a los distintos usuarios de los dispositivos de entrada/salida (E/S), impresoras, discos, cintas y demás. El sistema operativo mantiene colas para peticiones de imprimir, leer o escribir en cada uno de estos dispositivos.

programa de colas
este programa es un ejemplo de una cola
import javax.swing.*;
public class ColaJava {
static Cola accion=new Cola();
public static void main(String[] args) {
int opc=0; while(true){ opc=Integer.parseInt(JOptionPane.showInputDialog(null, "---------------------------------------\n" + "Cola en Java\n" + "---------------------------------------\n" + "1. Introducir dato\n" + "2. Sacar dato\n" + "3. Ver datos introducidos\n" + "4. Borrar los datos de la cola\n" + "---------------------------------------\n" + "5. Salir\n" + "---------------------------------------\n" +
"Teclea el numero de la accion a relizar:"
));
switch(opc){ case 1: accion.Introducir(); break;
case 2: accion.Sacar();
break;
case 3: accion.Mostrar();
break;
case 4: accion.Borrar();
break;
case 5: System.exit(0);
break;
default: JOptionPane.showMessageDialog(null,"No se realizo ningunaaccion\nOpcion no valida"); break; } } } }class Cola{ int tamaño=5;
String cola[]=new String [tamaño];
int frente=0;
int ultimo=-1;
public void Introducir(){
if(ultimo==cola.length-1){
JOptionPane.showMessageDialog(null,"No se realizo ninguna accion");
JOptionPane.showMessageDialog(null,"La cola esta llena\nSaca un datopara poder introducir uno nuevo"); }else{ ultimo++; cola[ultimo]=JOptionPane.showInputDialog(null,"Que dato deseas introducir:"); } }public void Sacar(){ if(ultimo==-1){
JOptionPane.showMessageDialog(null,"No se realizo ninguna accion");
JOptionPane.showMessageDialog(null,"La cola esta vacia\nIntroduce unnuevo dato para poder sacar uno"); }else{ JOptionPane.showMessageDialog(null,"Se saco el dato ( "+cola[frente]+" )"); for(int i=frente;i<ultimo;i++){ cola[i]=cola[i+1]; }cola[ultimo]=null; ultimo--; } }public void Mostrar(){ if(ultimo==-1){ JOptionPane.showMessageDialog(null,"La cola esta vacia\nNo hay datos que mostrar"); } else{ String mostrar=""; for(int i=frente;i<=ultimo;i++){ mostrar=mostrar+cola[i]; }JOptionPane.showMessageDialog(null,"El dato frente es: "+cola[frente]); JOptionPane.showMessageDialog(null,"El dato ultimo es: "+cola[ultimo]); JOptionPane.showMessageDialog(null,"Los datos almacenados son:\n"+mostrar); } }public void Borrar(){ frente=0;
ultimo=-1;
JOptionPane.showMessageDialog(null,"Todos los datos fueron borrados:\n");
}
}
bibliografia
colas

PILAS

concepto
pila es una estructura de datos en la que la inserción y la extracción de elementos se realiza sólo por un extremo que se denomina cabeza. como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. es decir, el último elemento que se metió en la pila será el primero en salir de ella.

debido al orden en que se insertan y eliminan los elementos en una pila, también se le conoce como estructura lifo (last in, first out: último en entrar, primero en salir).

ejemplo grafico:

en resumen: una pila es una estructura de datos homogénea (elementos del mismo tipo), secuencial y de tamaño variable. sólo es

posible un modo de acceso a esta estructura: a través de la cabeza de la pila.

en donde se logran a través de funciones como:

*insertar

*mostrar

*extraer

*mostrar

Operaciones

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

• Crear: se crea la pila vacía.
• Apilar: se añade un elemento a la pila.(push)
• Desapilar: se elimina el elemento frontal de la pila.(pop)
• Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)
• Vacía: devuelve cierto si la pila está vacía o falso en caso contrario.

tres programas de pilas
1) pila estatica
package estructuradedatos;
import java.util.Scanner;
/**
 *
 * @author EDDY
 */
public class pila_estatica {
    int pila[]=new int[10];
    int pilai[]=new int[10];
    public void agregar(int dato)
    {
        Scanner cap = new Scanner (System.in);
        Scanner cap1 = new Scanner (System.in);
        String resp;
        System.out.println("desea agregar datos?");
        resp=cap.nextLine();
        System.out.println("ingrese los datos");
        for(int t=0;t<10;t++)
        {
        if(resp.equalsIgnoreCase("si"))
            {       
                dato=cap1.nextInt();
        }
            pila[t]=dato;
            pilai[t]=pila[t];
        }
    }
    public void imprimir ()
    {
        for(int s=9;s>0;s--)
        {
            System.out.println("dato "+s+" "+ pila[s]);
        }
    }
    public static void main(String[] args) {
        pila_estatica p = new pila_estatica();
        int dato=0;
        p.agregar(dato);
        p.imprimir();
    }
}

2) pila estatica con menu

package estructuradedatos;
import java.util.Scanner;
/**
 *
 * @author EDDY
 */
public class pila_pushpop {
    int pila[]=new int[10];
    int tope;
    int x=-1;
    public void tamaño()
    {
        System.out.println("¿de que tamaño quieres que sea la pila?");
        System.out.println("ten en cuenta que el valor 0 es una pila de un elemento");
        Scanner cap = new Scanner (System.in);
        tope=cap.nextInt();
    }
    void push()
    {
        x++;
        if (x==tope){
            System.err.println("la pila esta llena");
        }
        else{
        System.out.println("¿que valor desea ingresar?");
        Scanner cap1=new Scanner(System.in);
        int dato=cap1.nextInt();
        pila[x]=dato;
        }
    }
    void pop()
    {
        if (x==-1){
            System.err.println("la pila esta vacia");
        }
        else{
            x--;
            System.err.println("dato borrado");
        }
    }
    public void imprimir ()
    {
        if (x==-1){
            System.err.println("la pila esta vacia");
        }
        else{
        for(int s=x;s>=0;s--)
        {
            System.out.println("dato "+s+" "+ pila[s]);
        }
        }
    }
    void vaciar(){
        x=-1;
        System.err.println("la pila esta vacia");
    }
    public static void main(String[] args) {
        pila_pushpop p = new pila_pushpop();
        int menu=0;
        p.tamaño();
        Scanner cap1= new Scanner (System.in);
        do{
            System.out.println("1.-ingresar un dato");
            System.out.println("2.-borrar un dato");
            System.out.println("3.-mostrar pila");
            System.out.println("4.-vaciar pila");
            System.out.println("5.-salir");
            menu=cap1.nextInt();
            switch (menu){
                case 1:
                    p.push();
                    break;
                case 2:
                    p.pop();
                    break;
                case 3:
                    p.imprimir();
                    break;
                case 4:
                    p.vaciar();
                    break;
                case 5:
                    System.out.println("adios");
                    break;
                default:
                    System.out.println("la opcion no es correcta");
                    break;
        }
    }
        while (menu!=5);
}
}

3) pila dinamica (editada de un programa de lista)

package estructuradedatos;
import java.util.*;
/**
 *
 * @author EDDY
 */
public class pilaDinamica {
    public static void main(String[] args) {
        Scanner leer = new Scanner(System.in);
        int num, op;
        LinkedList lista = new LinkedList();
        do{
            System.out.println("\t menu\t");
            System.out.println("operaciones con pilas");
            System.out.println("1.- insertar al final");
            System.out.println("2.- borrar al final");
            System.out.println("3.- mostrar pila");
            System.out.println("4.- borrar toda la pila");
            System.out.println("5.- salir");
            System.out.println("\n");
            System.out.println("elija la operacion que desee");
            op=leer.nextInt();
            switch (op){
                case 1:
                    System.out.println("inserte numero");
                    num = leer.nextInt();
                    lista.addLast(num);
                    break;
                case 2:
                    System.out.println("se borrara el noso final");
                    lista.removeLast();
                    break;
                case 3:
                    System.out.println("la lista es la siguiente");
                    List lista2 = new ArrayList(lista);
                    Iterator it = lista2.iterator();
                    while (it.hasNext()){
                        System.out.println(it.next());
                    }
                    break;
                case 4:
                    System.out.println("se borraran todos los elementos");
                    lista.clear();
                    break;
                case 5:
                    System.out.println("al rato");
                    break;
            }
        }
        while (op !=5);
    }
}



bibliografia
concepto
operaciones