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 ...112   ()
Imagen de Jose Antonio Acevedo San Martin
de Jose Antonio Acevedo San Martin - domingo, 8 de junio de 2014, 17:13
Todo el mundo

Arboles en Java: Recorrido Preorden, Inorden y Postorden

 

El recorrido de árboles refiere al proceso de visitar de una manera sistemática, exactamente una vez, cada nodo en una estructura de datos de árbol (examinando y/o actualizando los datos en los nodos).

Preorden: (raíz, izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden, hay que realizar las siguientes operaciones recursivamente en cada nodo, comenzando con el nodo de raíz:
  1. Visite la raíz
  2. Atraviese el sub-árbol izquierdo
  3. Atraviese el sub-árbol derecho
Inorden: (izquierdo, raíz, derecho). Para recorrer un árbol binario no vacío en inorden (simétrico), hay que realizar las siguientes operaciones recursivamente en cada nodo:
  1. Atraviese el sub-árbol izquierdo
  2. Visite la raíz
  3. Atraviese el sub-árbol derecho
Postorden: (izquierdo, derecho, raíz). Para recorrer un árbol binario no vacío en postorden, hay que realizar las siguientes operaciones recursivamente en cada nodo:
  1. Atraviese el sub-árbol izquierdo
  2. Atraviese el sub-árbol derecho
  3. Visite la raíz
En general, la diferencia entre preorden, inorden y postorden es cuándo se recorre la raíz. En los tres, se recorre primero el sub-árbol izquierdo y luego el derecho.
  • En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho
  • En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho, y
  • En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho

 

public class NodoArbol
{
    //miembros de acceso
    NodoArbol nodoizquierdo;
    int datos;
    NodoArbol nododerecho;
     
    //iniciar dato y hacer de este nodo un nodo hoja
    public NodoArbol(int datosNodo)
    {
        datos = datosNodo;
        nodoizquierdo = nododerecho = null; //el nodo no tiene hijos
    }
     
    //buscar punto de insercion e inserter nodo nuevo
    public synchronized void insertar(int valorInsertar)
    {
        //insertar en subarbol izquierdo
        if(valorInsertar < datos)
        {
            //insertar en subarbol izquierdo
            if(nodoizquierdo == null)
                nodoizquierdo = new NodoArbol(valorInsertar);
            else    //continua recorriendo subarbol izquierdo
                nodoizquierdo.insertar(valorInsertar);
        }
         
        //insertar nodo derecho
        else if(valorInsertar > datos)
        {
            //insertar nuevo nodoArbol
            if(nododerecho == null)
                nododerecho = new NodoArbol(valorInsertar);
            else
                nododerecho.insertar(valorInsertar);
        }
    } // fin del metodo insertar
}
 
class Arbol
{
    private NodoArbol raiz;
     
    //construir un arbol vacio
    public Arbol()
    {
        raiz = null;
    }
     
    //insertar un nuevo ndo en el arbol de busqueda binaria
    public synchronized void insertarNodo(int valorInsertar)
    {
        if(raiz == null)
            raiz = new NodoArbol(valorInsertar); //crea nodo raiz
        else
            raiz.insertar(valorInsertar); //llama al metodo insertar       
    }
     
    // EMPIEZA EL RECORRIDO EN PREORDEN
    public synchronized void recorridoPreorden()
    {
        ayudantePreorden(raiz);
    }
    //meoto recursivo para recorrido en preorden
     
    private void ayudantePreorden(NodoArbol nodo)
    {
        if(nodo == null)
            return;
         
        System.out.print(nodo.datos + " ");     //mostrar datos del nodo
        ayudantePreorden(nodo.nodoizquierdo);   //recorre subarbol izquierdo
        ayudantePreorden(nodo.nododerecho);     //recorre subarbol derecho
    }
     
    //EMPEZAR RECORRIDO INORDEN
    public synchronized void recorridoInorden()
    {
        ayudanteInorden(raiz);
    }
     
    //meoto recursivo para recorrido inorden
    private void ayudanteInorden( NodoArbol nodo)
    {
        if(nodo == null)
            return;
         
        ayudanteInorden(nodo.nodoizquierdo);
        System.out.print(nodo.datos + " ");
        ayudanteInorden(nodo.nododerecho);
    }
     
    //EMPEZAR RECORRIDO PORORDEN
    public synchronized void recorridoPosorden()
    {
        ayudantePosorden(raiz);       
    }
     
    //meotod recursivo para recorrido posorden
    private void ayudantePosorden(NodoArbol nodo)
    {
        if( nodo == null )
            return;
         
        ayudantePosorden(nodo.nodoizquierdo);
        ayudantePosorden(nodo.nododerecho);
        System.out.print(nodo.datos + " ");
    }
}


Clase controladora: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import javax.swing.JOptionPane;
 
public class PruebaArbol
{
    public static void main(String args [])
    {
        Arbol arbol = new Arbol();
        int valor;
        String Dato;
         
        System.out.println("Insertando los siguientes valores: ");
         
        Dato = JOptionPane.showInputDialog("Inserta el numero de nodos que desea ingresar");
        int n = Integer.parseInt(Dato);
         
        for(int i = 1; i <= n; i++ )
        {
            Dato = JOptionPane.showInputDialog("Dame el " + i + " valor para colocar en el Arbol");
            valor = Integer.parseInt(Dato);
            System.out.print(valor + " ");
            arbol.insertarNodo(valor);
        }
         
        System.out.println("\n\nRecorrido Preorden");
        arbol.recorridoPreorden();
         
        System.out.println("\n\nRecorrido Inorden");
        arbol.recorridoInorden();
         
        System.out.println("\n\nRecorrido Postorden");
        arbol.recorridoPosorden();
    }
}
[ Modificado: domingo, 8 de junio de 2014, 17:15 ]
 
Imagen de Jose Antonio Acevedo San Martin
de Jose Antonio Acevedo San Martin - domingo, 8 de junio de 2014, 17:10
Todo el mundo
La recursividad es una técnica potente de programación que puede utilizarse en lugar de la iteración para resolver determinados tipos de problemas.
Por ejemplo, para escribir un método que calcule el factorial de un número entero no negativo, podemos hacerlo a partir de la definición de factorial:
Si n = 0 entonces
0! = 1
si n>0 entonces
n! = n * (n–1) * (n–2) * ... * 3 * 2 * 1 
 
La solución iterativa es fácil de entender. Utiliza una variable para acumular los productos y obtener la solución. En la solución recursiva se realizan llamadas al propio método con valores de n cada vez más pequeños para resolver el problema.
Cada vez que se produce una nueva llamada al método se crean en memoria de nuevo las variables y comienza la ejecución del nuevo método.
Para entender el funcionamiento de la recursividad, podemos pensar que cada llamada supone hacerlo a un método diferente, copia del original, que se ejecuta y devuelve el resultado a quien lo llamó.
En la figura siguiente podemos ver como sería la ejecución del programa Java anterior para calcular el factorial de 3. 
 
 
 
·         Uno o más casos base: casos para los que existe una solución directa.
·         Una o más llamadas recursivas: casos en los que se llama sí mismo

 

[ Modificado: domingo, 8 de junio de 2014, 17:11 ]
 
Imagen de Cesar Babilonia del Villar
de Cesar Babilonia del Villar - domingo, 8 de junio de 2014, 16:57
Imagen de Cesar Babilonia del Villar
de Cesar Babilonia del Villar - domingo, 8 de junio de 2014, 16:56
Imagen de Cesar Babilonia del Villar
de Cesar Babilonia del Villar - domingo, 8 de junio de 2014, 16:50
Todo el mundo

Arboles

 

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.

También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

Esto son definiciones simples. Pero las características que implican no lo son tanto.

Árbol
Árbol

Definiremos varios conceptos. En relación con otros nodos:

  • Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, 'L' y 'M' son hijos de 'G'.
  • Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo 'A' es padre de 'B', 'C' y 'D'.

Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.

En cuanto a la posición dentro del árbol:

  • Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el ejemplo, ese nodo es el 'A'.
  • Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: 'F', 'H', 'I', 'K', 'L', 'M', 'N' y 'O'.
  • Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: 'B', 'C', 'D', 'E', 'G' y 'J'.

Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos.

Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden usarse todos, algunos o ninguno de los punteros de cada nodo.

Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo.

En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un árbol completo.

Existen otros conceptos que definen las características del árbol, en relación a su tamaño:

  • Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
  • Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.
  • Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
  • Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.

Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos árboles se conocen también como árboles binarios.

Frecuentemente, aunque tampoco es estrictamente necesario, para hacer más fácil moverse a través del árbol, añadiremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos avanzar en dirección a la raíz, y no sólo hacia las hojas.

Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se desarrolla el árbol, si perdemos este nodo, perderemos el acceso a todo el árbol.

 

Árboles binarios de búsqueda (ABB).

Se trata de árboles de orden 2 en los que se cumple que para cada nodo, el valor de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave del nodo y que el valor de la clave raíz del subárbol derecho es mayor que el valor de la clave del nodo.

Árbol binario de búsqueda
 

Operaciones en ABB

El repertorio de operaciones que se pueden realizar sobre un ABB es parecido al que realizábamos sobre otras estructuras de datos, más alguna otra propia de árboles:

  • Buscar un elemento.
  • Insertar un elemento.
  • Borrar un elemento.
  • Movimientos a través del árbol:
    • Izquierda.
    • Derecha.
    • Raiz.
  • Información:
    • Comprobar si un árbol está vacío.
    • Calcular el número de nodos.
    • Comprobar si el nodo es hoja.
    • Calcular la altura de un nodo.
    • Calcular la altura de un árbol.

 

Arbol en AVL

 

El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores, Georgii Adelson-Velskii y Yevgeniy Landis.

Los árboles AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad O(log n).

 

Operaciones

Las operaciones básicas de un árbol AVL implican generalmente el realizar los mismos algoritmos que serían realizados en un árbol binario de búsqueda desequilibrado, pero precedido o seguido por una o más de las llamadas "rotaciones AVL".

Representación de árboles AVL
*Mantener la información sobre el equilibrio de forma implícita en la estructura del árbol
*Atribuir a, y almacenar con, cada nodo el factor de equilibrio de forma explícita

 

 

 

 
Imagen de Cesar Babilonia del Villar
de Cesar Babilonia del Villar - domingo, 8 de junio de 2014, 16:48
Todo el mundo

Recursividad

 

 

Hablamos de recursividad, tanto en el ámbito informático como en el ámbito matemático, cuando definimos algo (un tipo de objetos, una propiedad o una operación) en función de sí mismo. La recursividad en programación es una herramienta sencilla, muy útil y potente.

Características.

Un algoritmo recursivo consta de una parte recursiva, otra iterativa o no recursiva y una condición de terminación. La parte recursiva y la condición de terminación siempre existen. En cambio la parte no recursiva puede coincidir con la condición de terminación.

Algo muy importante a tener en cuenta cuando usemos la recursividad es que es necesario asegurarnos que llega un momento en que no hacemos más llamadas recursivas. Si no se cumple esta condición el programa no parará nunca.Podemos distinguir dos tipos de recursividad:

Directa: Cuando un subprograma se llama a si mismo una o mas veces directamente.

Indirecta: Cuando se definen una serie de subprogramas usándose unos a otros.

Ventajas e inconvenientes.

La principal ventaja es la simplicidad de comprensión y su gran potencia, favoreciendo la resolución de problemas de manera natural, sencilla y elegante; y facilidad para comprobar y convencerse de que la solución del problema es correcta.

El principal inconveniente es la ineficiencia tanto en tiempo como en memoria, dado que para permitir su uso es necesario transformar el programa recursivo en otro iterativo, que utiliza bucles y pilas para almacenar las variables.

 
Imagen de Cesar Babilonia del Villar
de Cesar Babilonia del Villar - domingo, 8 de junio de 2014, 16:46
Todo el mundo

Primero debemos decir que la recursividad no es una estructura de datos, sino que es una técnica de programación que nos permite que un bloque de instrucciones se ejecute n veces. Remplaza en ocasiones a estructuras repetitivas.

Este concepto será de gran utilidad para el capítulo de la estructura de datos tipo árbol.

La recursividad es un concepto difícil de entender en principio, pero luego de analizar diferentes problemas aparecen puntos comunes.

En Java los métodos pueden llamarse a sí mismos. Si dentro de un método existe la llamada a sí mismo decimos que el método es recursivo.

Cuando un método se llama a sí mismo, se asigna espacio en la pila para las nuevas variables locales y parámetros.

Al volver de una llamada recursiva, se recuperan de la pila las variables locales y los parámetros antiguos y la ejecución se reanuda en el punto de la llamada al método.

 
Imagen de eder enrique castro sanchez
de eder enrique castro sanchez - domingo, 8 de junio de 2014, 16:30
Todo el mundo

ARBOLES BINARIOS

Definicion: Arboles Restringidos a maximo dos descendientes.

Aplicaciones: Evaluacion de expreciones aritmeticas, busquedas y ordenamiento.

Terminologia:

 

Completo: Todos los nodos exepto las hojas tienen dos hijos

Balanceado: para todos los nodos la diferencia entre las alturas del subArbol Izquierdo y Derecho es menor de dos(2).

Dejenerado: En el que existe un solo nodo hoja( E ) y cada nodo no hoja sólo tiene un hijo.

Implementacion

 

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"));

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

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

}

}

 
Imagen de eder enrique castro sanchez
de eder enrique castro sanchez - domingo, 8 de junio de 2014, 15:38
Todo el mundo

Recursividad.

Definicion: La recursividad es una regla que permite que la funcion o metodo se autollame, es una alternativa a los procesos interativos { for, while, do while }.

Cuando es util: cuando una solucion a un problema interativamente es muy compleja.

Aplicaciones: Recorrido de estructuras no lineales (Arboles y Grafos, formulas matematicas complejas).

Nota: por cada autollamado (equibalente a interacio) se crea una copia con todas las variables e instrucciones que se almacenan en la pila de llamado a subprogramas.

Implementacion de recursividad:

sintaxis 

Public Static tipo/clase NombreMetodoRecursivo(){

If (Exprecion logica) // Contro Autollamado

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

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

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

NombreMetodoRecursivo(parametros actuales) }

Ejemplo:

Public class Principal {

Public Static LongFactorial (int n){

            if (n == 0) {

                   return 1;

           }else {

                  return n*Factorial (n-1);

}

}

Public Static void main (String []... arg) {

          S.O.P(Factorial (5));

 

 
Imagen de eder enrique castro sanchez
de eder enrique castro sanchez - domingo, 8 de junio de 2014, 14:57
Todo el mundo

Arboles

Definicion: Los arboles son estructuras no linealies, que sirven para organizar informacion en forma de niveles.

Aplicacion: Se aplica en, directorios, organigrama, geneologia, ordenamiento de busqueda, evaluacion de expreciones aritmeticas.

Utilidad: se utilizan en estructuracion de datos en forma gerarquica, distinguen entre mayores y menores.

Terminologia:

Nodo raiz: Es unico, sin ascendentes. Nodo Interno: Tiene tanto ascendientes como descendiente. Nodo Hoja: No tiene descendiente. Altura: Es la cantidad de niveles. Rama: camino desde la raiz hasta la hoja. Peso: Cantidad de hojas. Orden: Cantidad de nodos. Subarbol: Es un nodo con todos sus descendientes.             

 

                                        

Implementacion Arreglo Y Nodos: 

 

 

 

 

 
Página: ()  1 ...  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28 ...112   ()