Listas y arboles

Una de las aplicaciones más interesantes y potentes de la memoria dinámica y de los punteros son, sin duda, las estructuras dinámicas de datos. Las estructuras básicas disponibles en C y C++ (structsy arrays) tienen una importante limitación: no pueden cambiar de tamaño durante la ejecución. Los arrays están compuestos por un determinado número de elementos, número que se decide en la fase dediseño, antes de que el programa ejecutable sea creado.
En muchas ocasiones se necesitan estructuras que puedan cambiar de tamaño durante la ejecución del programa. Por supuesto, podemoscreararrays dinámicos, pero una vez creados, tu tamaño también será fijo, y para hacer que crezcan o disminuyan de tamaño, deberemos reconstruirlos desde el principio.
Las estructuras dinámicas nos permiten crearestructuras de datos que se adapten a las necesidades reales a las que suelen enfrentarse nuestros programas. Pero no sólo eso, como veremos, también nos permitirán crear estructuras de datos muyflexibles, ya sea en cuanto al orden, la estructura interna o las relaciones entre los elementos que las componen.
Las estructuras de datos están compuestas de otras pequeñas estructuras a las quellamaremos nodos o elementos, que agrupan los datos con los que trabajará nuestro programa y además uno o más punteros autoreferenciales, es decir, punteros a objetos del mismo tipo nodo.
Una estructurabásica de un nodo para crear listas de datos seria:
-------------------------------------------------
struct nodo {
-------------------------------------------------int dato;
-------------------------------------------------
struct nodo *otronodo;
-------------------------------------------------
};
El campo "otronodo"puede apuntar a un objeto del tipo nodo. De este modo, cada nodo puede usarse como un ladrillo para construir listas de datos, y cada uno mantendrá ciertas relaciones con otros nodos.
Para acceder a...