Arboles (estructura de datos)

Arboles

Existen en Informática varias estructuras no lineales, en las que un elemento puede estar relacionado con más de uno sea por delante o detrás de él (por ejemplo, los grafos); no obstante, dentro del carácter introductorio de este curso, nosotros nos restringiremos a la más sencilla de ellas, la de árbol.

A todos nos son familiares expresiones como “árbol genealógico” o “recorrer unárbol”. En este sentido, un árbol es una estructura que implica una jerarquía, en la que cada elemento está unido a otros por debajo de él. Comparada con las estructuras lineales anteriores, el árbol tiene la particularidad de que cada elemento puede tener más de un “siguiente”, aunque un solo antecedente o padre.

Definiremos árbol, de forma recursiva, como un conjunto finito de uno o másnodos, de tal manera, que exista un nodo especial denominado raíz y los nodos restantes están divididos en conjuntos denominados subárboles, que también responden a la estructura de un árbol. Por extensión a la idea de árbol genealógico se habla de nodos padres y nodos hijo y un nodo, en la parte inferior del que no cuelgue ningún subárbol (no tiene ningún hijo) se denomina nodo terminal u hoja(véase Figura 5.13).




raíz
nodo





nodo
nod
nodo


nodo terminal
nodo nodo



subárbol
hoja





Fig 5.13. Conceptos relacionados con los árboles
El nodo raíz es el primer nodo de un árbol. Cada enlace en el nodo raíz se refiere a un hijo.

El hijo izquierdo es el primer nodo en el subárbol izquierdo y el hijo derecho es el primer nodo enel subárbol derecho.

Los hijos de un nodo se conocen como descendientes. Un nodo sin hijos se conoce como nodo de hoja.

El nodo n1 es un ancestro del nodo n2, si n1 es el padre de n2 o el padre de algún ancestro de n2.

Un nodo n2 es un descendiente izquierdo del nodo n1, si n2 es el hijo izquierdo de n1 o un descendiente del hijo izquierdo de n1. Un descendiente derecho se define de lamisma forma.

Dos nodos son hermanos si son los hijos izquierdo y derecho del mismo padre.
Aunque los árboles naturales crecen con sus raíces en el suelo y sus hojas en el aire, los
computólogos casi universalmente representan las estructuras de árbol con la raíz en la parte superior y las hojas en la parte inferior.

La dirección de la raíz a las hojas es “hacia abajo” y la dirección opuestaes “hacia arriba”. Pasar de las hojas a la raíz se denomina “subir” por el árbol, y dirigirse de la raíz a las hojas se denomina “descender” por el árbol.

Si cada nodo que no es hoja en un árbol binario tiene subárboles izquierdo y derecho que no están vacíos, el elemento se clasifica como árbol estrictamente binario. Un árbol estrictamente binario con n hojas siempre contiene 2n-1 nodos.El nivel de un nodo en un árbol binario se define del modo siguiente: la raíz del árbol tiene el nivel 0, y el nivel de cualquier otro nodo en el árbol es uno más que el nivel de su padre.

La profundidad de un árbol binario es el máximo nivel de cualquier hoja en el árbol. Esto es igual a la longitud de la trayectoria más larga de la raíz a cualquier hoja. Un árbol binario completo deprofundidad d es un árbol estrictamente binario que tiene todas sus hojas en el nivel d.

Arbol binario

Hay un tipo especial de árbol muy usado en computación, denominado árbol binario, en el que de cada nodo pueden colgar, a lo más, dos subárboles. Estos se denominan subárbol derecho y subárbol izquierdo, y también son árboles binarios. La Figura representa un árbol binario.



nodonodo nodo


nodo
nodo
nodo

nodo


La forma usual de representar los árboles supone el uso de punteros, aunque también se puede hacer con vectores. En un árbol...