Grafos y Metodos de ordenacion

Descargar presentación Power Point

Descarga Aqui

Vídeos de los métodos de ordenación 

Descarga Aquí

• Radix
• Quicksort
• Shellsort
• Burbuja

Arboles Binarios

Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3″, eso significa que tenemos un grafo donde cada nodo puede tener máximo 2 hijos ( o hojas ) y estas hojas no pueden tener como hijos a cualquier otra hoja anterior como podemos ver en la siguiente imagen:

Podemos ver en la imagen como “Raíz” es padre de “Hoja 1″ y “Hoja 2″ y estas a su vez también son la raíz de las “Sub hojas” y se vuelve un proceso recursivo hasta ncantidad de hojas.

¿Para que sirve un árbol binario?

Como todos sabemos un árbol binario es una estructura de datos, y como todas, este sirve para organizar datos para facilitar su manipulación, ya sea el ingreso, borrado o búsqueda de datos, y precisamente una de las principales ventajas de los árboles binarios es la búsqueda, ya que como en muchos algoritmos de búsqueda necesitamos tener la información ordenada y en nuestros árboles binarios precisamente los datos van ingresando de forma ordenada.

Recorridos con los conocidos métodos recursivos:

Inorden

 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

Codigo:

public synchronized void recorridoInorden()

    {

        ayudanteInorden(raiz);

    }

     

    //metodo recursivo para recorrido inorden

    private void ayudanteInorden( NodoArbol nodo)

    {

        if(nodo == null)

            return;

         

        ayudanteInorden(nodo.nodoizquierdo);

        System.out.print(nodo.datos + " ");

        ayudanteInorden(nodo.nododerecho);

    }

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

     

Postorden

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

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

    }

}

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

Preorden

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

Codigo:

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

    }

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

Programa de arboles Binarios

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

Listas , Pilas y Colas

Listas , Pilas y Colas

Conceptos:

¿Qué es un Nodo?

Un nodo es una variable que contiene una dirección de memoria, también se le puede llamar puntero o apuntador.

¿Qué es una Lista?

Una lista es una de las estructuras de datos fundamentales, y puede ser usada para implementar otras estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior. El principal beneficio de las listas enlazadas respecto a los vectores convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.

Programa de Listas Simples

Programa de Listas Dobles

¿Qué es una Cola?

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. 

Programa de Colas

¿Qué es una Pila?

Una pila es una lista ordenada o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos. Esta estructura se aplica en multitud de ocasiones en el área de informática debido a su simplicidad y ordenación implícita de la propia estructura.

Programa de Pilas