Arboles

Un árbol es un tipo especial de relación que es muy útil para el estudio de una gran variedad de aplicaciones en las ciencias de la computación e ingeniería. Un árbol se representa como un grafo dirigido o no dirigido. Los árboles son muy usados en el estudio y construcción de base de datos, modelamiento jerárquico de clases y en la teoría de lenguajes y construcción de compiladores, son muy usados para describir los árboles sintácticos correspondientes a gramáticas de lenguajes.

Definición

Un árbol A se define como un conjunto de elementos llamados nodos o vértices, de forma que:

- A es vacío, en cuyo caso se llama árbol vacío o árbol nulo, o

- A contiene un nodo distinguido v0 llamado raíz de A y los nodos restantes de A forman un conjunto de árboles

A1, A2, A3, ..., An

Cada árbol Ai tiene como raíz al nodo vi

Un árbol se representa mediante un grafo en donde la raíz v0 es el nodo en A en la parte superior. Una línea hacia abajo de izquierda a derecha, un arco señala a los hijos de v0

-A1, A2, A3, ..., An son llamados subárboles de v0

-Si Ai no es vacío, entonces su raíz vi, es llamado hijo de v0, y v0 es llamado padre de vi

Terminologia

• Raíz - El nodo superior del árbol.
• Padre - Nodo con hijos.
• Hijo - Nodo descendiente de otro nodo.
• Hermanos - Nodos que comparten el mismo padre.
• Hojas - Nodos sin hijos.
• Nivel - El nivel de un nodo está definido por 1+ el número de conexiones entre el nodo y la raíz.
• La longitud de camino - Es el número de nodos de la secuencia menos uno. La longitud de camino está determinado por el número de aristas del camino, no por el número de nodos del camino. Así el camino (a,b,c) es de longitud 2, el camino (a, b) es de longitud 1, el camino (a) es de longitud 0.
• - Si existe un camino del nodo a hacia el nodo b, se dice que a es antecesor de b y b es sucesor o descendiente de a.
• - El momento o tamaño de un árbol, es el número de nodos que contiene el árbol.
• - El peso es el número de hojas del árbol.
• - Llamamos grado de un nodo al número de hijos del nodo.

...