Índice

Árboles

1. Generalidades sobre los árboles

Árbol

a. Principio

Un árbol es una estructura de datos que permite almacenar información manteniendo una jerarquía y una organización de los datos:

images/06ri43.png

Un árbol está formado por nodos interconectados entre ellos de forma jerárquica por enlaces. El primer nodo es la raíz; los últimos, después de los cuales no hay más nodos, son las hojas. El recorrido de la raíz a una hoja es una rama. Cada nodo puede considerarse como la raíz del subárbol que forma toda su descendencia y él mismo. El árbol es, de hecho, una estructura recursiva. En el anterior ejemplo, cada subárbol corresponde a un paréntesis. Un dato con paréntesis puede traducirse en árbol.

La expresión: (persona (nombre, apellidos, dirección (calle, número, población, provincia))) es la del árbol:

images/06ri44.png

A cada piso del árbol se le llama nivel y los niveles se numeran del 1 (la raíz) a n (la hoja de más abajo). La altura de un árbol es el nivel máximo alcanzado por una hoja. La altura del árbol anterior es 3.

A menudo, se habla de nodos padres e hijos. Los nodos hijos son los que descienden de un nodo padre y solo la raíz no tiene padre. En el ejemplo anterior, persona es la raíz y es padre de nombre, apellidos y dirección, que son sus hijos. Dirección, a su vez, es también padre de calle, número, población ...