Estructura de Datos: Arboles

Un árbol es una estructura de datos no lineal y jerárquicamente organizada, cuyos elementos son nodos conectados por bordes que no forman ciclos. Todo árbol tiene un nodo raíz de donde descienden mas nodos, existe solo un camino para acceder a cada nodo desde la raíz.

Algunos ejemplos de arboles son: la tabla de contenido de un libro o el sistema de archivos de cualquier sistema operativo ya sea Unix, DOS o Windows.

 

Datos importantes y terminología

• Un árbol con n nodos tiene n-1 bordes o conectores
• La raíz es un nodo sin padres o ancestros
• las hojas son los nodos mas externos sin hijos o descendientes
• hermanos son nodos con el mismo padre

Longitud de un camino: el el número de bordes que se pueden seguir desde un nodo hasta alcanzar otro nodo

Profundidad: Número de bordes desde la raíz a el nodo, la profundidad del nodo raíz siempre es 0

Altura: Longitud del camino mas largo desde la raíz al a la hoja mas profunda que se pueda alcanzar.

Tamaño del nodo: Es la suma de todos los nodos descendientes mas uno, que equivale al nodo que estamos midiendo, el tamaño de la raíz determina el tamaño del árbol.

Estructuras para implementar árboles

Con una lista enlazada

Con una matriz si sabemos el número máximo de hijos que poseen los nodos

Siguiente:Formas de recorrer un árbol

Si tienes información adicional sobre este tema, tus comentarios o enlaces de referencia serán bienvenidos.