Proyecto 1 - Estructuras De Datos

El objetivo de este proyecto es enseñarle a personas de entre 12 y 15 años de edad el funcionamiento básico de las siguientes estructuras de datos:

1. Listas enlazadas
2. Listas doblemente enlazadas 
3. Árboles binarios
4. Árboles binarios de búsqueda
5. Grafos dirigidos
6. Grafos no dirigidos

La actividad se enfocará en la creación y búsqueda de nodos de estas estructuras, no incluirá eliminación, ordenamiento y demás. Por medio de esta actividad los estudiantes aprenderán la importancia de las estructuras de datos y se espera que después de la actividad puedan utilizar las funcionalidades mencionadas anteriormente.

1. 6 Botellas de agua o refrescos, preferiblemente plásticas para evitar posibles accidentes con botellas de vidrio.
2. Deben ser llenadas hasta la mitad de agua, arena o cualquier material que les de peso.
3. Al menos dos metros de cuerda
4. Tijeras (o Cutter)
5. Cinta adhesiva
6. Marcador permanente
7. Una hoja
8. Un carrito de juguete

En primera instancia vamos a cortar dos trozos de cinta, y pegarlos a la par, esto simplemente para aumentar el grosor del trozo. Una vez tenemos la cinta cortada le escribimos el numero 1 y se lo pegamos a una botella.

Hacemos el mismo procedimiento, pero ahora las cintas tendrán el numero 2, 3, ..., 6 y se lo pegamos a las distintas botellas que nos sobraron.

Con una hoja, vamos a formar un embudo de papel para poder llenar de manera mas sencillas las botellas de arena y minimizar algún tipo de accidente con la arena.

Una vez formado el embudo / cono procedemos poner este mismo en la boca de botella para así poder pasar la arena de una forma más sencilla.

Ahora bien, aún no hemos explicado que las botellas representarán los nodos en las listas enlazadas.

¿Recuerdan los números que escribimos en la cinta? Esa es la información almacenada dentro de cada nodo (botella). Pero, como sabemos, las listas enlazadas necesitan un puntero que indique hacia el siguiente nodo. Aquí es donde entra en juego la cuerda, que funcionará como el puntero.

Para simular esto, cortamos la cuerda en pedazos más pequeños y los usamos para conectar las botellas. Luego, tomamos más cinta y dibujamos una flecha en ella para representar la dirección en la que apunta el puntero, indicando el siguiente nodo en la lista.

Con la ayuda de un adulto, perfora las botellas utilizando un cúter o unas tijeras. Es importante tener precaución durante este paso, ya que puede ocurrir un accidente si no se maneja con cuidado.

Para facilitar el paso de la cuerda, realiza una incisión en forma de cruz en la botella. Asegúrate también de hacer dos incisiones opuestas, es decir, una en cada lado de la botella, para que la cuerda pueda atravesarla de forma adecuada.

Ahora lo que hay que hacer es, mediante un extremo de la cuerda, la ingresamos a una de las botellas y el otro extremo en otra botella.

Recordemos que estamos trabajando con listas enlazadas, por lo que es importante comprender su funcionamiento.

Imaginemos que Mario quiere llegar al nodo 3, pero siempre inicia en el nodo 1. En este tipo de estructura, el nodo 1 únicamente conoce la dirección del nodo 2. Por lo tanto, Mario debe moverse primero al nodo 2 para verificar si este conoce la ubicación del nodo 3. Al encontrar la dirección correcta, Mario finalmente se mueve directamente al nodo 3.

Sin embargo, hay un detalle importante: Mario no puede retroceder. Esto se debe a que, en una lista enlazada simple, los nodos solo almacenan la referencia al siguiente nodo, pero no tienen información sobre el nodo anterior. Por esta razón, el recorrido es unidireccional.

Para solucionar el problema mencionado anteriormente, podemos usar otro tipo de lista enlazada: la lista doblemente enlazada. Este tipo de lista tiene un puntero tanto para el nodo siguiente como para el nodo anterior, permitiendo recorrerla en ambas direcciones.

Para representar este puntero adicional, simplemente cortamos un poco más de cinta y dibujamos otra flecha en ella. Sin embargo, esta vez la pegaremos apuntando en la dirección contraria a la flecha original, indicando el enlace hacia el nodo anterior.

En este caso si Mario tiene que ir a la ciudad numero 3 y luego regresar a la ciudad numero dos lo podrá hacer sin mayor problema.

Un árbol binario es una forma de organizar información usando una estructura que se parece a un árbol, pero al revés: en lugar de crecer hacia arriba, crece hacia abajo.

El árbol comienza con una sola pieza llamada raíz (un nodo). Desde la raíz, salen ramas (punteros) que conectan con otras piezas llamadas nodos (los mismos que mencionamos antes). En un árbol binario, cada nodo puede tener como máximo dos hijos: uno a la izquierda y otro a la derecha.

Para reutilizar los materiales que habíamos usado ya, nada mas quitemos las flechas que antes se había puesto en los punteros que representaban el viaje de vuelta en la lista enlazada.

Ahora debemos usar todos los nodos disponibles y conectarlos utilizando los punteros, recordando que cada nodo puede tener, como máximo, dos hijos.

Imaginemos que Mario quiere llegar al nodo número 5, pero comienza en el nodo 1. Este nodo tiene dos hijos: el nodo 2 y el nodo 3.

Supongamos que Mario elige ir por el nodo 3. Sin embargo, este nodo solo tiene una referencia al nodo 6, y el nodo 6 no tiene más referencias. Al no encontrar su destino, Mario regresa al nodo raíz para intentar otra ruta hacia el nodo 5.

Ahora, Mario decide tomar el camino hacia el nodo 2, que tiene dos referencias: el nodo 4 y el nodo 5. En este punto, Mario sigue la referencia hacia el nodo 5, logrando finalmente llegar a su destino.

Ahora hablemos de otro tipo de árbol binario: el árbol binario de búsqueda. Estos árboles tienen una característica especial: están organizados de tal manera que, al recorrerlos de izquierda a derecha, los nodos siguen un orden de menor a mayor.

Veamos ahora el nuevo árbol que tenemos. Como puedes observar, el nodo raíz ya no es el nodo 1, ya que eso haría que solo tuviera un hijo a la derecha. La idea aquí es ejemplificar de manera más clara cómo funcionan este tipo de árboles.

Imaginemos que Mario quiere llegar al nodo 5. Como él comienza en el nodo 4, debemos preguntarnos lo siguiente: ¿es el nodo 5 mayor o menor que el nodo 4?

Si fuera menor, Mario se movería al nodo derecho. Sin embargo, como el nodo 5 es mayor, Mario se dirige al nodo izquierdo. Esto sigue la regla de los árboles binarios de búsqueda, donde los nodos a la izquierda siempre son mayores que el nodo actual.

Los grafos dirigidos no necesariamente deben estar organizados en un orden específico. Además, estos pueden tener direcciones unidireccionales o bidireccionales. Pero, ¿qué significa esto exactamente?

En la imagen actual, podemos ver que los nodos tienen punteros hacia otros nodos. Presten atención a los nodos 3 y 4: el nodo 3 apunta al nodo 4, y el nodo 4 apunta al nodo 3. Esto indica que existe una dirección bidireccional entre esos nodos. Sin embargo, supongamos que queremos ir del nodo 3 al nodo 2. Esto no sería posible en este grafo, ya que no existe un puntero que apunte directamente hacia el nodo 2 desde el nodo 3.

En el caso de este tipo de grafos no dirigidos, nuestro protagonista, Mario, puede ir del nodo 1 al nodo 2 y del nodo 2 al nodo 1 sin ningún problema, ya que existe una conexión bidireccional entre ambos nodos.

Veamos otro ejemplo con la imagen que tenemos. Mario quiere llegar al nodo 5, pero comienza en el nodo 1. Desde allí, puede moverse al nodo 2, y luego al nodo 3. En el nodo 3, hay dos caminos: uno que lo lleva al nodo 4 y otro que lo lleva al nodo 5. Supongamos que, por error, Mario toma el camino hacia el nodo 4. Sin embargo, esto no es un problema, ya que puede devolverse y tomar el otro camino que lo llevará al nodo 5.