Programacion

Árboles
Los árboles son estructuras de datos útiles en muchas aplicaciones. Hay varias formas de árboles y cada una de ellas es práctica en situaciones especiales, en este capítulo vamos a definir algunas de esas formas y sus aplicaciones.

Concepto general de árbol
Desde el punto de vista de estructuras de datos, un árbol es un concepto simple en su definición, sin embargo es muyingenioso. Un árbol es un grafo con características muy especiales:
Definición 9   Un árbol es un grafo que tiene un único nodo llamado raíz que:
* Tiene 0 relaciones, en cuyo caso se llama nodo hoja
* tiene un número finito de relaciones, en cuyo caso, cada una de esas relaciones es un subárbol
Para empezar a estudiar los árboles, nos concentraremos en primer lugar en el caso en que el nodoraíz tenga 0, 1 ó 2 subárboles.
Árboles binarios
Definición 10   Un árbol binario es una estructura de datos de tipo árbol en donde cada uno de los nodos del árbol puede tener 0, 1, ó 2 subárboles llamados de acuerdo a su caso como:
* Si el nodo raíz tiene 0 relaciones se llama hoja.
* Si el nodo raíz tiene 1 relación a la izquierda, el segundo elemento de la relación es el subárbolizquierdo.
* Si el nodo raíz tiene 1 relación a la derecha, el segundo elemento de la relación es el subárbol derecho.
La figura 25 muestra algunas configuraciones de grafos que sí son árboles binarios, y la figura 26 muestra algnas configuraciones de grafos que no son árboles binarios.
|
Figura 25: Grafos que son estructuras tipo árbol binario |

|
Figura 26: Grafos que no sonárboles binarios |
Vamos a dar una lista de teérminos que se usan frecuentemente cuando se trabaja con árboles:
* Si A es la raíz de un árbol y B es la raíz de su subárbol izquierdo (o derecho), se dice que A es el padre de B y se dice que B es el hijo izquierdo (o derecho) de A.
* Un nodo que no tiene hijos se denomina hoja
* El nodo a es antecesor del nodo b (y recíprocamente elnodo b es descendiente del nodo a), si a es el padre de b o el padre de algún ancestro de b.
* Un nodo b es un descendiente izquierdo del nodo a, si b es el hijo izquierdo de a o un descendiente del hijo izquierdo de a. Un descendiente derecho se define de la misma forma.
* Dos nodos son hermanos si son hijos izquierdo y derecho del mismo padre.
Otros términos relacionados conárboles, tienen que ver con su funcinoamiento y topología:
* Si cada nodo que NO es una hoja tiene un subárbol izquierdo y un subárbol derecho, entonces se trata de un árbol binario completo.
* El nivel de un nodo es el número de aristas que se deben recorrer para llegar desde ese nodo al nodo raíz. De manera que el nivel del nodo raíz es 0, y el nivel de cualquier otro nodo es el nivel delpadre más uno.
* La profundidad de un nodo es el máximo nivel de cualquier hoja en el árbol.
Si un árbol binario tiene nodos en el nivel , el máximo número de nodos en el nivel es . Dado que un árbol binario sólo tiene un nodo en el nivel 0, puede contener un máximo de nodos en el nivel . Un árbol binario completo de profundidad es el árbol que contiene exactamente nodos en cada nivel entre 0 y. La cantidad total de nodos en un árbol binario completo de profundidad , es igual a la suma de nodos en cada nivel entre 0 y , por tanto:

Usando inducción matemática se puede demostrar que . Dado que todas las hojas en este árbol están en el nivel , el árbol contiene hojas y, por tanto, nodos que no son hojas.
Si conocemos el número total de nodos en un árbol binario completo, podemoscalcular su profundidad , a partir de la expresión . Así sabemos que la profundidad es igual a 1 menos que el número de veces que 2 debe ser multiplicado por sí mismo para llegar a . Es decir, que en un árbol binario completo,

Definición 11   Un árbol binario es un árbol binario casi completo si:
1. Cualquier nodo a un nivel menor que tiene 2 hijos
2. Para cualquier nodo en el árbol...