Arboles Binarios

Definición  Un arbol 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 elsubárbol izquierdo.
• 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 26muestra algnas configuraciones de grafos que no son árboles binarios.

    Figura 25: Grafos que son estructuras tipo árbol binario 
                                              Image sabin

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 el nodo b es descendiente del nodo a), sia 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 del padre 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, podemos calcular 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 con un descendiente derecho en el nivel  debe tener un hijo izquierdo y cada descendiente izquierdo de  :
   • es una hoja en el nivel  ó
   • tiene dos hijos

Figura 27: Comparación de un árbol binario y un árbol binario casi completo. El árbol mostrado en (A) descumple la regla 2 de los árboles binarios casi completos.

Los nodos en un árbol binario (completo, casi completo o incompleto) se pueden enumerar del siguiente modo. Al nodo raíz le corresponde el número 1, al hijo izquierdo le corresponde el doble del número asignado al padre y al hijo derecho le corresponde el doble más 1 del número asignado al padre.