Arboles

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o   varios nodos.También se suele dar una definición recursiva: un árbol es una estructura en compuesta  por un dato y varios árboles.Esto son definiciones simples

Pero las características que implican no lo son tanto.

Definiremos varios conceptos. En relación con otros nodos:

• Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol.     En el ejemplo, ‘L’ y ‘M’ son hijos de ‘G’.
• Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo    ‘A’ es padre de ‘B’, ‘C’ y ‘D’.

Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo   puede ser apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que   estos árboles estén fuertemente jerarquizados, y es lo que en realidad les da la apariencia   de árboles.

En cuanto a la posición dentro del árbol:

• Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al   árbol. En el ejemplo, ese nodo es el ‘A’.
• Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: ‘F’, ‘H’, ‘I’, ‘K’,    ‘L’, ‘M’, ‘N’ y ‘O’.
• Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no    pertenecen a ninguna de las dos categorías anteriores. En el ejemplo: ‘B’, ‘C’, ‘D’, ‘E’,     ‘G’ y ‘J’.

Otra característica que normalmente tendrán nuestros árboles es que todos los nodos  contengan el mismo número de punteros, es decir, usaremos la misma estructura para  todos los nodos del árbol. Esto hace que la estructura sea más sencilla, y por lo tanto  también los programas para trabajar con ellos.

Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que  pueden usarse todos, algunos o ninguno de los punteros de cada nodo.

Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol  completo.

En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un   nodo cualquiera de la estructura, podemos considerarlo como una estructura   independiente. Es decir, un nodo cualquiera puede ser considerado como la raíz de un   árbol completo.

Existen otros conceptos que definen las características del árbol, en relación a su tamaño:

• Orden: es el número potencial de hijos que puede tener cada     elemento de árbol. De este modo, diremos que un árbol en el que cada nodo     puede apuntar a otros dos es de orden dos, si puede apuntar a tres     será de orden tres, etc.
• Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En    el árbol del ejemplo, el grado es tres, ya que tanto ‘A’ como ‘D’ tienen tres hijos, y no    existen elementos con más de tres hijos.
• Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en     nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el    nodo ‘D’ tiene nivel 1, el nodo ‘G’ tiene nivel 2, y el nodo ‘N’, nivel 3.
• Altura: la altura de un árbol se define como el nivel del nodo de     mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la     raíz de un árbol, también podemos hablar de altura de ramas. El árbol     del ejemplo tiene altura 3, la rama ‘B’ tiene altura 2, la rama ‘G’ tiene     altura 1, la ‘H’ cero, etc.

Árboles Binarios

Un árbol binario   T se define como un conjunto finito de elementos, llamados  nodos, de forma que:

2. T es vacío ( en cuyo caso se llama    árbol nulo o árbol vació) o
3. T contiene un nodo distinguido R, llamado    raíz de T, y los restantes nodos de T forman un par    ordenado de árboles binarios disjuntos T1 y    T2.

Si T contiene una raíz R, los dos    árboles T1 y T2 se llaman, respectivamente,    subárboles izquierdo y derecho de la raíz R. Si    T1 no es vació , entonces su raíz se llama    sucesor izquierdo de R; y análogamente, si T2 no es    vació, su raíz se llama sucesor derecho de    R.

Observe que :

1. B es un sucesor izquierdo y C un sucesor derecho del    nodo A.
2. El subárbol izquierdo de la raíz A    consiste en los nodos B, D, E y F, y el subárbol derecho    de A consiste en los nodos C , G, H, J, K y L.

Cualquier nodo N de un árbol binario T tiene 0, 1  ó 2 sucesores. Los nodos A,B,C y H tienen dos sucesores,  los nodos R y J sólo tienen un sucesor , y los nodos D,F,  G,L y K no tienen sucesores. Los nodos sin sucesores se llaman  nodos terminales.

La definición anterior del árbol binario T  es recursiva, ya que T se define en términos de los  subárboles binarios T1 y T2. Esto significa, en  particular, que cada nodo N de T contiene un subárbol  izquierdo y uno derecho. Más aun, si N es un nodo  terminal, ambos árboles están  vacíos.

Dos árboles binarios T y T’ se dicen que  son similares si tienen la misma estructura o,  en otras palabras, si tienen la misma forma. Los árboles  se dice que son copias si son similares y tienen los mismos  contenidos en sus correspondientes nodos.

Árboles binarios  Completos

Considere un árbol binario T. El  árbol binario T se dice que es completo si todos sus  niveles, excepto posiblemente el ultimo, tienen el máximo  numero de nodos posibles y si todos lo9s nodos del ultimo nivel  están situados. Lo más posible a la izquierda.  Así, solo existe un único árbol completo Tn  con exactamente n nodos.