Blog del sitio: Tecnológico

Página: ()  1 ...  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 ...110   ()
Imagen de VICTOR ALFONSO ALCALA QUINTANA
de VICTOR ALFONSO ALCALA QUINTANA - martes, 3 de junio de 2014, 15:09
Todo el mundo

            

Pre : Raiz, Izq, Der : A, B,D,E,C,F

In : Izq , Raiz, Der : D,B,E,A,F,C

Pos: Izq, Der, Raiz: D,E,B,F,C,A

 

 

Metodos Recursivos 

    Public static void PreOrden (NodoArbolBin r){

      if (r!=null){

      System.out.pritln(r.getDato () );                  A,B,D,E,C,F

    PreOrden (r.getIzq () );

    PreOrden (r.getDer () );

         }

   }

 

 

Public static void InOrden (NodoArbolBin r){

      if (r!=null){                  

    InOrden (r.getIzq () );

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

    InOrden (r.getDer () );

         }

   }

 

 

 

Public static void PosOrden (NodoArbolBin r){

      if (r!=null){                  

    PosOrden (r.getIzq () );

    PosOrden (r.getDer () );

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

         }

   }

 

Arboles Expresivos :

Arboles binarios completos que se usan para evaluar expresiones aritmeticas en estos arboles las hojas son los operandos y el resto de nodos los operadores.

Expresiones Aritmeticas :

1+2*3        Pos Fija

a+b*c       abc*+

 

Posibles Orden

 

 

El recorrido en preOrden da un arbol de expresivo produce la prefija 

In Orden = PosFija

 

 

 
Imagen de VICTOR ALFONSO ALCALA QUINTANA
de VICTOR ALFONSO ALCALA QUINTANA - martes, 3 de junio de 2014, 14:05
Todo el mundo

IMPLEMENTACION DE ARBOLES:

SubClasificacion:

Arboles Binarios : Tienen una restriccion , maximo dos hijos por nodo

Aplicaciones: Evaluacion de expresiones aritmeticas busqueda y ordenamiento , etc.

Terminologia: Un arbol binario siempre tiene un sub arbol a la izq y un sub arbol a la derecha y se diferencia por su inclinacion 

Arbol Binario Completo: Todo los nodos tienen dos hijos excepto los hijos

Arbol Binario Balanceado: para todos los nodos las diferencias entre las alturas del subárbol izquierdo y derecho es menor a dos.

Arbol Binario Lleno: Todos los niveles del árbol tienen el máximo de nodos -1 cantidad total de nodos del árbol.

Arbol Binario Degenerado: Todos los nodos tienen solo un hijo excepto las hojas.

Ejemplo:

 

Implementación de Arboles binarios: es posible hacerla con vectores o con Nodos.

Todo lo que tenga -1 son las hojas

public class NodoArbolBin <T> {

             private T dato;

             private NodoArbolBin izq;

             private NodoArbolBin der;

            

    public NodoArbolBin() { }

   

    public NodoArbolBin(T dato) {

             this.dato = dato;

             izq = der = null;

       }

   

    public void setIzq(NodoArbolBin izq){

             this.izq = izq;

        }

    public NodoArbolBin getIzq(){

             return izq;

         }

    public void setDer(NodoArbolBin der){

             this.der = der;

         }

    public NodoArbolBin getDer(){

             return der;

         }

    public void setDato(T dato){

             this.dato = dato;

         }

    public T getDato(){

             return dato;

           }

      }

 

 

public class Principal {

    public static void main (String [] arg){

             NodoArbolBin raiz;

             raiz = new NodoArbolBin("A");

             raiz.setIzq(new NodoArbolBin("B"));

             raiz.setDer(new  NodoArbolBin ("C"));

             NodoArbolBin a = raiz.getIzq();

             a.setIzq(new NodoArbolBin("D"));

             a = raiz.getDer();

             a.setIzq(new NodoArbolBin("E"));

             a.setDer(new NodoArbolBin("F"));

             -------------------

               --------------

               --------------

             // Otras Instrucciones-                

                    }   

             }

 Recorridos:

Combinacion de actividades para visitar todos los nodos y hacer las respectivas operaciones 

Actividades (Recursivas)                                                  Combinaciones                          Recorridos

1) Visitar Raiz                                                                   1   2    3                                  Pre Orden

2) Recorrer SubArbol Izq (R)                                               2   1    3                                  In Orden

3) Recorrer SubArbol Der (R)                                              2   3     1                                 Pos Orden

 

Opinion Personal

 A mi concepto los arboles se pueden implementar en vectores , nodos , arreglos , tambien puedo decir que los arboles tienen una subclasificacion en la cual se ven los arboles binarios , arboles de expresion y arboles binaros de busqueda ABB , en los cuales los arboles binarios tienen una restriccion y solamente puede tener dos hijos maximos por nodo , este tiene aplicaciones como lo son las expresiones aritmeticas , debemos tambien tener en cuenta que los arboles tienen un sub arbol a la derecha y un sub arbol a la izq para que la restriccion pueda cumplirse de lo contrario la restriccion no se cumpliria.

 

 

 

 

[ Modificado: martes, 3 de junio de 2014, 14:38 ]
 
Imagen de Simon Way Esalas Young
de Simon Way Esalas Young - martes, 3 de junio de 2014, 13:07
Todo el mundo

ÁRBOLES

ESTRUCTURA DE DATOS

 

Un árbol es una estructura de datos no lineal, la cual es útil para la búsqueda y ordenamiento de datos de tipo jerárquico; y manejo de expresiones aritméticas.

 

La implementación puede hacerse de manera estática y dinámica, y pueden éstos ser de tipo general o binario, destacándose dentro de los binarios los ABB y los AVL.

 

  TERMINOLOGÍA

 

 

El árbol graficado tiene como raíz el nodo A, 11 nodos, una altura de 3 y peso de 6.

 

ÁRBOL BINARIO

 

En esta estructura, cada nodo tiene máximo dos (2) hijos, llamándose el de la izquierda subárbol izquierdo y el otro subárbol derecho.

 

TIPOS DE ÁRBOLES BINARIOS

  • Lleno: tiene el máximo de nodos en cada nivel. Se comprueba a través de
  • Completo: tiene cero o dos hijos.
  • Balanceado: en todos los nodos la diferencia de altura entre el subárbol izquierdo y derecho es cero o uno.
  • Degenerado: todos los nodos tienen un hijo, excepto la hoja.

 

El árbol graficado:

-          No es lleno pues debería tener  nodos para cumplir con el máximo número de nodos por nivel, y tan sólo tiene 11 nodos.

-          Es completo, pues el nodo A tiene 2 hijos (B,C) , el B tiene 2 hijos (D,E), el E tiene 0 hijos, el D tiene 2 hijos (H, I), el C tiene 2 nodos (F,G), el nodo F tiene 2 hijos (J,K) y finalmente el nodo G tiene 0 hijos.

-          Es balanceado.

-          No es degenerado.

 

    

Los árboles tienen unos recorridos en los que se realizan 3 actividades en diverso orden; éstos pueden recorrerse de manera preorden, inorden y posorden.

Las actividades del recorrido son: 

1. Visitar la raíz

2. Recorrer el subárbol izquierdo

3. Recorrer el subárbol derecho

 Y la combinación de actividades se da como se muestra a continuación:

Recorrido

Combinación Actividades

Preorden

1, 2, 3

Inorden

2, 1, 3

Posorden

2, 3, 1

 

 Para realizar cualquiera de los recorridos se toma como apoyo una pila. En el siguiente recorrido preorden se analizará la interacción con la pila

 

                                           

 public static void preOrden(NodoArbolBin r){

             if(r != null){

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

                      preOrden(r.getIzq());

                      preOrden(r.getDer());

             }

}

 

 public static void inOrden(NodoArbolBin r){

             if(r != null){

                      inOrden(r.getIzq());

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

                      inOrden(r.getDer());

             }

}

 

 public static void posOrden(NodoArbolBin r){

             if(r != null){

                      posOrden(r.getIzq());

                      posOrden(r.getDer());

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

             }

}

              

[ Modificado: lunes, 9 de junio de 2014, 12:30 ]
 
Imagen de Simon Way Esalas Young
de Simon Way Esalas Young - martes, 3 de junio de 2014, 12:39
Imagen de JAIRO ALFONSO ROJAS LEDESMA
de JAIRO ALFONSO ROJAS LEDESMA - martes, 3 de junio de 2014, 12:16
Imagen de HEYNIS BARROSO JIMENEZ_12217065
de HEYNIS BARROSO JIMENEZ_12217065 - martes, 3 de junio de 2014, 09:58
Todo el mundo

Clase 27 de Mayo de 2014

 

Subclasificacion:

ARBOLES BINARIOS: Arboles restringidos a máximo dos descendientes. Máximo debe tener dos hijos.

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

2.1 Completo: Todos los nodos excepto las hojas tienen dos hijos.

2.2 Balanceado: Para todos los nodos la diferencia entre las alturas del subárbol izquierdo y derecho es menor de 2.

2.3. Degenerados: Todos los nodos excepto las hojas tienen un solo hijo.

2.4. Llenos: Todos los niveles (altura) tienen el máximo de nodos donde la cantidad de nodos es 2h-1 es la cantidad total de nodos del árbol. 

24-1 = 16-1=15 

ARBOL

A

B

C

D

Completo

si   

x

si   

x

Balanceado

si   

x

si   

si   

Degenerado

x

si   

x

x

Lleno

si   

x

x

x

Clase Nodo Arbol Binario

public class NodoArbolBin <T>{

      private T dato;

      private NodoArbolBin izq;

      private NodoArbolBin der;

}

public class Principal{

   public static void main (String[]arg){

      NodoArbolBin a;

      a = new NodoArbolBin (“A”);

      a.setIzq (new NodoArbolBin (“B”));

      a.setDer (new NodoArbolBin (“C”));

      NodoArbolBin b = a.getIzq ();

      b.setIzq (new NodoArbolBin (“D”));

      b.a.getDer ();

      b.setIzq (new NodoArbolBin (”E”));

      b.setDer (new NodoArbolBin (”F”));

   }

}

Recorridos: Visita de todos los nodos para hacer las respectivas operaciones.

ACTIVIDADES

COMBINACIONES

RECORRIDO

1. Visitar raíz

1, 2, 3

Pre-orden

2. Recorrer sub Arbol Izq.

2, 1, 3

Inorden

3. Recorrer sub Arbol Der.

2, 3, 1

Posorden

 Nota: Empieza en 1 y se va saltando un puesto hasta quedar de último. 

[ Modificado: martes, 3 de junio de 2014, 10:52 ]
 
Todo el mundo

Reflexion:

Destruccion de sodoma y gomorra: creo que este relato todos lo hemos visto o escuchado, pero que quiza no se habia profundizado mas de lo normal en el. Sabemos que esta cuidad estaba undida en el pecado sexual del cual aun en estos tiempo se esta viviendo. De cierta forma Dios mando a destruir esta cuidad por este pecado; pero en esa cuidad habia una persona que creia en Dios ese era lot el cual era sobrino de Abraham, Dios tuvo compacion de el y lo saco con su famia, auque su mujer no conto con esa suerte ya que anhelaba mas los placeres y comunidades que tenia en esa tierra que ser liberada del pecado. Viendo este pasaje desde este punto podemos observar y hacer una comparacion con la vida actual del hombre actual, muchas veces vivimos vendados sin saber la verdadera verdad de lo que para que fuimos llamado Dios es un Dios bondaso pero tambien es fuego que consume, el hombre seimpre queire estar en lujos, placeres, o sea amarado a lo material y se olvidan de lo mas importante y es su vida y comunion con Dios. Dios quiere hombre que miren hacia delante que no le de miedo dejarlo todo por el.

En el anterior blog habíamos expuesto o comenzado el tema de Árboles, en el cual se viola utilidad, las aplicaciones y su terminología. En esta nueva entrada se continuará con el tema de árboles pero ahora con el caso de su implementación.

Implementación:

En este punto se realizara la implementación atreves de arreglos y de nodos.

 

Implementacion con Arreglos:

 

Implementacion con Nodos:

Sub Clasificación de Arboles:

Arboles Binarios: Tienen una restricción y es que deben de haber máximo dos hijos por nodos.

Aplicaciones: Evaluaciones de Expresiones aritméticas, búsqueda y ordenamiento entre otros.

Terminología:

 

Como estan los arboles:

Completo: Todo los nodos tienen dos hijos excepto los hijos

Balanceado: para todos los nodos las diferencias entre las alturas del subárbol izquierdo y derecho es menor a dos.

Lleno: Todos los niveles del árbol tienen el máximo de nodos -1 cantidad total de nodos del árbol.

Degenerado: Todos los nodos tienen solo un hijo excepto las hojas.

 

He aqui un pequeño Ejercicio para saber identificarlos dependiendo lo dicho anteriormente:

 

Arboles

A

B

C

D

Completo

No

No

Si

Si

Lleno

No

No

No

Si

Degenerado

Si

No

No

No

Balanceado

No

Si

Si

Si

 

La implementación de Arboles binarios es posible hacerla con vectores o con Nodos.

Implementación con Vectores:

 

Implementación con Nodos:

A modo de codificacon se haria de esta manera

Clase NodoArbolBinario

 

public class NodoArbolBin {

 

             private T dato;

             private NodoArbolBin izq;

             private NodoArbolBin der;

            

    public NodoArbolBin() { }

   

    public NodoArbolBin(T dato) {

             this.dato = dato;

             izq = der = null;

    }

   

    public void setIzq(NodoArbolBin izq){

             this.izq = izq;

    }

    public NodoArbolBin getIzq(){

             return izq;

    }

    public void setDer(NodoArbolBin der){

             this.der = der;

    }

    public NodoArbolBin getDer(){

             return der;

    }

    public void setDato(T dato){

             this.dato = dato;

    }

    public T getDato(){

             return dato;

    }

 }

 

Clase Principal

 

public class Principal {

    public static void main (String [] arg){

             NodoArbolBin raiz;

             raiz = new NodoArbolBin("A");

             raiz.setIzq(new NodoArbolBin("B"));

             raiz.setDer(new  NodoArbolBin ("C"));

             NodoArbolBin a = raiz.getIzq();

             a.setIzq(new NodoArbolBin("D"));

             a = raiz.getDer();

             a.setIzq(new NodoArbolBin("E"));

             a.setDer(new NodoArbolBin("F"));

             //Otras Instrucciones                   

    }   

}

 

Recorridos:

Son una combinación de actividades para visitar todos los nodos y hacer las respectivas operaciones.

 

Actividades (Recursivas)

Combinaciones

Recorridos

Visita raíz

1

2

3

Preorden

Recorrer subárbol Izq ( R )

2

1

3

InOrden

Recorrer subárbol Der ( R )

2

3

1

PosOrden

 

Pre: A, B, D, C, E, F

Int: D, B, A, E, C, F            IZQ – RAIZ - DER

Pos: D, B, E, F, C, A           IZQ -  DER – RAIZ

 

 

A modo de resumen podemos decir que los árboles son posible implementarlos atreves de vectores, arreglos o nodos. Además podemos afirmar que los arboles tienen una subclasificación en la cual se pueden ver los arboles binarios, los cuales tienen una restricción y es solamente pueden tener máximamente dos hijos por nodos, estos además tiene ciertas aplicaciones como por ejemplo al momento de evaluar expresiones aritméticas, por ser árbol binario de obvio tener en cuenta que este debe tener por decir así una partición a la derecha y otra a la izquierda para que la restricción se pueda cumplir. Los arboles binarios tienen a su vez una genealogía o característica que es el ver si está completo, balanceado, degenerado, o lleno.

 

[ Modificado: domingo, 1 de junio de 2014, 14:48 ]
 
Imagen de Cindy Paola Castilla Bahoque
de Cindy Paola Castilla Bahoque - sábado, 31 de mayo de 2014, 18:52
Todo el mundo

los arboles son estructura de datos no lineal para organizar  la información por niveles

 

pero como toda estructura esta tiene su aplicacion como lo son: organigramas, genealogía, directorio, expresiones aritméticas, ordenamientos y búsquedas.

las utilidades que los arboles tienes son: organizar estructuras jerárquicas (se diferencia entre elementos mayores y menores).

 

un arbol tiene una terminologia la cual se debe tener en cuenta árbol general compuesto por nodos Que pueden tener  una cantidad indeterminado de descendientes.

Implementación

 

los arboles tienen una clasificacion las cual es 

Arboles Binarios: este contiene maxiomo dos hijos por nodos que distingue entre izquierdo y derecho.

Terminologia:

completo: Todos los nodos o tienen dos hijos o cero.

 

Lleno: todos los niveles tienen el maximo de 2 nodosh   -1.

 

 Degenerado: Tdos los nodos solo tienen un hijo excepto hoja.

Balanceado:para todos los nodos la diferencia entre las alturas del subárbol izquierdo y derecho menor que 2 y mayor que -2

 

Implementacion

 

Recorrido

Actividades: 1. visitar raiz (mostrar datos)

2. recorrer subárbol izquierdo 

3. recorrer subárbol derecho

 

 
Imagen de STEPHANIE MARIa VALENCIA JIMENEz_12217061
de STEPHANIE MARIa VALENCIA JIMENEz_12217061 - sábado, 31 de mayo de 2014, 01:55
Todo el mundo

  

 

 

 

                                                           TIPOS DE ARBOLE BINARIOS

COMPLETO

TODOS LOS NODOS EXEPTO LA HOJAS TIENEN DOS HIJOS.

BALANCEADO

PARA TODO LOS NODOS LA DIFERENCIA ENTRE LAS ALTURAS DE SUB ARBOL IZQUIERDO Y EL SUB ARBOL DERECHO ES MENOR DE  DOS.

DEGENERADO

TODOS LOS NODOS EXEPTO LA HOJA TIENE UN SOLO HIJO.

LLENOS

TODOS LOS NIVELES TIENEN EL MAXIMO DE NODOS 2ʰ-1 ES LA CANTIDAD TOTAL DE NODOS DEL ARBOL.

 

 

 

 

 

 

 

  

                     

 

ARBOL

A

B

C

D

COMPLEJO                      

 

     X

ü 

     X

BALANCEADO

ü 

    X

ü 

ü 

DEGENERADO

    X

ü 

     X

ü 

LLENO

ü 

     X

     X

     X

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 IMPLEMENTACION

VECTOR

 

b.setIzq(new Nodo ArbolBin(“D”));

b=a.getDer();

b.setIzq(new Nodo ArbolBin(“E”));

b.setDer(new Nodo ArbolBin(“F”));

      }

}

Rrecorridos visita de todos los nodos para hacer las respectivas operaciones.

 

 

 

 

 
Imagen de Aldray Javier Narvaez Llamas
de Aldray Javier Narvaez Llamas - jueves, 29 de mayo de 2014, 22:23
Todo el mundo
Blog de apuntes estructura de datos
 

Principal

Clase 5

Recursividad y Arboles

Recursividad

¿Que es recursividad?

es la propiedad de las funciones paar autollamarse, los cuales tambien pueden utilizarse como una alternativa de iterarios.

Utilidad: se usan cuando la solucion iterativa (Ciclos for, do while, while) son muy complejos.

Aplicaciones: recorrido de estructuras no lineales, formulas matematicas complejas, programas con logica compleja, etc.

Recursividad vs Iteracion: -Metodos - Ciclos - Reduccion de Codigo min/considerable. - Consumo minimo/considerable de memoria.

Nota: la recursividad se caracteriza por ser un metodo, tener un ciclo de control y utilizar el mismo metodo en el metodo. Por ejemplo:

 


Arboles

Los árboles son estructuras de datos no lineales que permiten organizar datos de una forma jerarquica, es decir de mayor a menor. Cuya utilidad se puede ver reflejada en los arboles genealogiccos, expresiones aritmeticas, etc. Los arboles continenen niveles que van desde la raiz hasta las hojas.

Acontinuacion, tendremos una imagen de un arbol binario.

Pero... ¿Que son Arboles binarios?


Como se muestra en la imagen, los arboles binarios son los que tienen como maximo 2 hijos por nodo, el cual se distingue por tener una derecha e izquierda.

Existen 4 tipos de árboles binarios.


Complejo: es un árbol donde todos los nodos que tienen dos o cero hijos. Por ejemplo;

Lleno: es cuando todos los niveles tienen un máximo de nodos 2^h-1; donde h = Altura del árbol. Por ejemplo:

Degenerado: Todos los nodos solo tienen un hijo, excepto las hojas que por obvias razones, no pueden tener hijos. Por ejemplo:

Balanceado: se presenta cuando todos los nodos contienen una diferencia entre las  alturas entre el árbol izquierdo y derecho de menor que 2 y mayor que -2. Por ejemplo:

Este árbol, se encuentra estrictamente balanceado ya que la diferencia de sus altura es = 0.

Estas son las actividades que se realizan para recorrer un árbol binario:

1- Visitar raíz

2- Recorrer subárbol izquierdo

3- Recorrer subárbol derecho y a continuación les presentare los recorridos existentes mas utilizados:

- Pre Orden == 1, 2, 3. 2

- InOrden == 2, 1, 3. 3

- Pos Orden == 2, 3, 1.  

*Algoritmo para recorrido preorden

Arboles de expresion: es un arbol binario completo para representar y evualuar expresiones aritmeticas, sus hijos son los operando y el reto de nodos sus operadores.

Arboles binarios de busqueda: proponen un algoritmo que genera una estructura y hace mas eficiente el proceso de busqueda que las otras estructuras visitan con anterioridad.

Eficiencia: Menor numero de comparaciones al buscar un elemento.

nota: por cada avance se descuenta un 80% de los elementos.

Criterio para crear arboles binarios de busqueda:


Para todos los nodos, los valores de las clases en el subarbol izquierdo son menores y en el subarbol derecho son mayores.

Los ABB contienen las siguientes operaciones:

Buscar: compara la clave buscada iniciando por la raiz, sino es igual pregunta si es mayor, siendo asi este se desplaza a la izquierda repitiendo el procso hasta encontrar coincidiencias o null.

Insetar: se busca la clave en caso que no exista se enlaza en el nodo adecuando.

Eliminar: se busca la clave, en caso de no encontrarla se analiza el caso, que puede ser de la siguinte manera:

*Si es una Hoja: simplemente se elimina.

*Si es un nodo con subarbol: se remplaza por su descendiente inmediato.

*Si es un nodo con 2 subarboles: se remplazan con el nodo mas a la derecha del subarbol izquierdo o con e lnodo mas a la izquierda del subarbol derecho.

Arboles Binarios de Busqueda Balanceados:

Lo Abb solo mantienen eficiencia en el proceso de busqueda si estos se encuentran balanceados, pero cuando tienen una tendencia degenerada, la eficiencia en el proceso de busqueda baja.

El destino AVL propone chequear en cada operacion de insercion o eliminacion, el balance del arbol y restructurarlo en caso de que este se pierda.

Como todo arbol, para que sea AVL debe cumplor que FE sea >-2 y < 2

Ejemplo:

Este Arbol cumple la condicion mencionada anteriormente. En cambio

 En los AVL hay que tener en cuenta que si uno de los arboles izquierdo o derecho se encuentran con tendencia degenerada, es decir NO BALANCEADO, posteriormente hay que balancearlo.

Operaciones:

1.Insertar: inicialmente se aplica a la misma regla ABB pero adicionalmente se calcula el FE(Factor de equilibrio), en cada rama de insercion comenzando por el nodo insertado.

2.Eliminar: se aplica incialmente la misma regla ABB, pero adicionalmente se calcula el FE, en la rama de eliminacion y se detecta el balance.

 

 

 


Aldray Javier Narvaez Llamas, Estudiante Tecnologico Comfenalco, Estructura de Datos.... Todos los derechos reservados ©2014

[ Modificado: miércoles, 11 de junio de 2014, 14:53 ]
 
Página: ()  1 ...  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 ...110   ()