Arboles Binarios De Expresion (22-mayo-2015)

Se USAN para representar y evaluar Expresiones aritmeticas
Son arboles binarios completos, Donde las hojas hijos hijo operandos y El Resto de nodos los Operadores.

Aqui VEMOS Como la pila Contiene 3 Elementos a, b, c.
El ultimo Elemento es colocado en la parte Derecha del nodo y el siguiente en la parte izquierda.

Arboles Binarios (21-mayo-2015)

Arboles binarios: Árbol Que restringe ONU Máximo Dos Pilas Descendientes por Cada Nodo.

Aplicaciones:
Representación y Evaluación de Expresiones aritméticas, búsqueda y ordenamiento.

Terminología:

Completo: Todos los nodos Tienen 0 o 2 hijos.
Lleno: Todos los Niveles Tienen De El Máximo de nodos (2h - 1 nodos).
Balanceados:  Todos los nodos con baño La Diferencia de las alturas del subárbol izquierdo y derecho es 0 y 1.
Degenerado: Todos los nodos Tienen Solo Un hijo EXCEPTO La Hoja.

Implementacion:
Estatica (Arreglos)

Clase pública NodoArbolBin <T> {

         Dato T Privado;

         Privada Izq NodoArbolBin;

         NodoArbolBin der privada;

         NodoArbolBin Pública (T dato, NodoArbolBin izq, der NodoArbolBin) {

             This.dato = dato;

             This.iq = izq;

            This.der = der;

          }

          ___

}

Dinamica (Nodos)

'

Clase pública Principal {

    Public static void main (String ... arg) {

        NodoArbolBin raiz = null;

        raiz = new NodoArbolBin ("A", nuevo NodoArbolBin ("B", null, null), nuevo NodoArbolBin ("C", null, null));

        NodoArbolBin P = raiz.getIzq ();

        p.setIzq (nueva NodoArbolBin ("D", null, null));

        p = raiz.getDer ();

        p.setIzq (nueva NodoArbolBin ("E", null, null));

        p.setDer (nueva NodoArbolBin ("F", null, null));

        Recorre (raiz);

     }

Static public void Recorre (NodoArbolBin r) {

    Si (r! = Null) {

       System.out.println (r.getDato ());

       Recorre (r.getIzq ());

       Recorre (r.getDer ());

     }

  }

}


Recorridos:
Visitar todos los nodos para hacer operaciones requeridas.

Arboles (15-mayo-2015)

Arboles: Son estructuras no lineales de tipo jerárquico.

Utilidad:
Aplican cuando se requiere representar estructuras con niveles y se pueda distinguir entre datos con mayor o menor valor.

Aplicaciones:
Organigramas, directorios, arboles geneologicos, etc.

Terminología:

Nodo: Cada elemento del arbol, solo tienen un padre, solo conocen la direccion de sus decendientes.

altura: cantidad de niveles: 3
peso: cantidad de hojas: 7
orden: cantidad de nodos: 10


Implementacion

Estática (Arreglos):

Dinamica (Nodos):

Recursividad (7-Mayo-27512015)

Propiedad de las funciones (Metodos), para autollamarse.

Utilidad:  Como alternativa a procesos interativos->(for,while,do.while), muy complejos.

Aplicaciones:  Recorrido de estructuras no lineales.

Ventajas:

Recursividad

* Reduce codigo

* Simplifica la logica

* Se da en metodos

* Consumo excesivo de memoria (Por cada autollamado se hace una copia del metodo y se guarda en la pila de llamado a subprogramas del sistema operativo).

Iteracion:

* No reduce codigo

* No simplifica, sino que tiene logica compleja

* No necesariamente en metodos con uso de (for,while,do-while)

* Muy bajo consumo de memoria.

Implementacion:

Iterativo:

Public static tipo nombreMetodo(args){

         _______

         _______

        for ( );

        _______

        _______

        while ( );

        _______

        _______

        do while( );

        _______

        _______

} 

Ejemplo:

factorial

5!= 1x2x3x4x5

public static long factorial (int n){

        long f=1; 

            for (int i=1; i<=n; i++){

                  f*=i;

            }

            return f;

}

Recursivo:

public static nombreMetodo (arg){

         if (condicion para autollamado){

         _______

         _______

         _______

        

         nombre Metodo(arg)

         _______

         _______

}

Ejemplo:

factorial
n!= n*(n-1)!

5! = 5*4! = 120
4! = 4*3! = 24
3! = 3*2! = 6
2! = 2*1! = 2
1! = 1*0! = 1
0! = 1

public static long factorial (int n){
           if (n==0){
                return 1;
           }else{
                    return n*factorial (n-1);
             }
}

Solucion Parcial #2 (7-mayo-2015)

1) Desarrole una funcion que intercambie los datos de los extremos de una pila (p).


Analisis:

Public static void intercambiarExtremos(Pila p){

      Pila q=new Pila( );

      Object aux  = p.quitar( );

      while (! p.vacia( )){

                q.poner(q.quitar( ));

      }

      p.poner(aux);

      aux=q.quitar( );

      while (! q.vacia( )){

                p.poner(q.quitar( ));

      }

      p.poner(aux);

}

Nota: aqui vemos como solamente cambian los extremos de la pila, notando que la parte del centro que igual.

2) Defina la clase pila en base a la grafica a continuacion

Nota: recuerde que las operaciones de pila son poner(por el fin), quitar(por el fin), cima(consulta fin), y vacia(no elementos).

Public class pilaNodoDoble <T> {

       private NodoDoble <T> tope;

       public boolean vacia( ) {  return tope==null; {

       public void poner (T dato) {

                  if (vacia( )){

                       tope=new NodoDoble(dato,null,null);

                  }else{ 

                           tope.setSig(new NodoDoble(dato,tope,null));

                           tope=tope.getSig( );

                    }

       }

       public T quitar( ){

                  T dato==null;

                  if (! vacia( )){

                       dato=tope.getDato( );

                       tope=tope.getAnt( );

                       if(tope != null){

                           tope.setSig(null);

                       }

                  }else{

                           System.out.print("Pila Vacia...!!!");

                    }

}       

Implementacion De La Cola (17-abril-2015)

Cola: Se realiza por extremos contrarios.

Operaciones: 
* Poner
* Quitar

VERSIÓN ESTATICA. (Arreglo)

 

VERSION DINAMICA. (Arreglo)

Implementacion De La Pila (16-abril-2015)

Pila: Restringe a un Extremo de la Estructura lineal-

Operaciones: 
* Poner (Almacenar un dato en la Estructura)
* Quitar (Recuperar el dato y eliminarlo de la Estructura)
cima
vacia
llena

VERSIÓN ESTATICA. (Base Vector)

tope: de control variable

                         

VERSIÓN DINAMICA. (Listas enlazadas)

Pilas Y Colas (16-abril-2015)

Son reglas Para La restriccion de Operaciones en ESTRUCTURAS lineales Como lo son (Arreglos, Listas enlazadas)

PILA : Se utilizan CUANDO Orden heno inverso.
EE.UU. la forma LIFO (último en el primero en salir), ultimo Elemento almacenado, Primero en Ser Procesado.

COLA : Almacenamiento temporal, MIENTRAS SE Hace un Proceso con la cola.
EE.UU. la forma FIFO (primero en firdt fuera), imprimación Elemento almacenado, Primero en Ser Procesado.

Utilidad 

Pila : Realizar Operaciones En Forma invertida, retroceder pendientes En Un Proceso Parr OPERACIONES Completar.
Cola: Cuando Los Recursos de Procesamiento HIJO Menos Que las Demandas de su USO. 

Aplicaciones 

Pila:  SO, Llamado un subprogramas, compiladores, párr evaluation de Expresiones aritméticas.
Cola: Cola de Procesos, cola de impresión, simulación.

Nota: Las Pilas Pecado no podria Existir modular la programacion.

EJERCICIO

1. CREAR Una Lista (a) de (n) con Nodos Datos Enteros Que contenga Números Positivos y Negativos pedidos desde el teclado y dividir La Lista en dos Nuevas Listas Una (b) Con Los numeros Positivos y Una (c) Con Los numeros 

Real = A;
mientras que (real! = null) {
      si (Actual.getDato> = 0) {
         si (b == null) {
            b = Actual;
            Real = Actual.getSig ();
            b.setSig (null);
            b1 = b;
          } Else {
              b.getSig (real);
              b = b.getsig (); 
              Real = Actual.getSig ();
              b.setSig (null);
            } Else {
                si (Actual.getDato <0) {
                   si (c == null)
                      c = Actual;
                      Real = Actual.getSig ();
                      c.setSig (null);
                      c1 = c;
                    } Else {
                        c.getSig (real);
                        c = c.getSig ();
                        Real = Actual.getSig ();
                        c.setSig (null);
                      }
             }
        }
   }