Árboles

Introducción a los árboles
Un árbol es una de las EDD más utilizadas para resolver multitud de problemas (y muy utilizada también en juegos).
En una EDD no lineal.
Un árbol se define recursivamente así: o es vacío o consiste en un nodo que contiene datos y punteros hacia otros árboles.

Idea gráfica del concepto de árbol (imagen)
Conceptos asociados:
raíz
Hoja
Ascendiente
Descendiente
Hermano
Padre
Hijo

Un caso concreto: árbol binario
Cada nodo tiene como máximo dos hijos.
Esto hace que la implementación sea más sencilla (cada nodo incluye dos punteros para apuntar a cada uno de los hijos, el izquierdo y el derecho):
struct nodo{
     struct info elemento;
     struct nodo *izq;
     sruct nodo *dcha;
};
struct nodo *arbol;

Implementación de un árbol general
Un árbol en general no tiene limitados el número de hijos que puede tener cada nodo, y por tanto no puedo establecer a priori un número de punteros en la estructura para apuntar a los hijos.
Una posible forma de hacerlo, sería teniendo una lista de punteros a los hijos almacenada en cada nodo, junto con la información que guarda el nodo. Es decir, para implementar un árbol general, haríamos uso de otra EDD.

Operaciones habituales con árboles
Insección
Eliminación
Búsqueda
Recorrido:
- Inorden: primero se recorre el subárbol izquierdo, luego se lee el valor de nodo y finalmente se recorre el subárbol derecho.
- Preorden: primero se lee el valor del nodo y después se recorren los subárboles.
- Postorden: se recorren primero el subárbol izquierdo y el derecho y después se lee el valor del nodo.

Aplicación de los árboles
Se utilizan en problemas que involucran jerarquía (por ejemplo, miembros de una familia), ramificación (como los árboles de juegos, que involucran tomar la mejor decisión de las posibles, tras analizar todas las consecuencias), clasificación y búsqueda eficiente.