Árboles binarios (definición).

   Un árbol binario es un conjunto finito de elementos el cual está vacío, o dividido en tres subconjuntos disjuntos:

1. El primer subconjunto contiene un elemento único llamado raíz del árbol.
2. El segundo subconjunto es en sí mismo un árbol binario y se le conoce como subárbol izquierdo del árbol original.
3. El tercer subconjunto es también un árbol binario y se le conoce como subárbol derecho del árbol original.

   Tome en consideración que en un árbol binario, tanto el subárbol izquierdo como el subárbol derecho podrían estar vacíos.

Representación y conceptos.

   Respecto a su representación, es común denominar a cada elemento de un árbol binario como nodo del árbol. La siguiente figura muestra una posible representación para un árbol binario:

Abstracción de un árbol binario como una estructura de nodos.

 

    Ahora bien, la representación de árbol binario de la figura anterior resultará sumamente útil para desarrollar e ilustrar los siguientes conceptos:

• Si B es la raíz de un árbol binario y D es la raíz del subárbol izquierdo/derecho (todos los conceptos que sigan esta notación tienen una naturaleza simétrica debido a la característica inherente a los árboles y por lo tanto, aplica tanto para el subárbol izquierdo como para el subárbol derecho), se dice que B es el padre de D y que D es el hijo izquierdo/derecho de B.
• A un nodo que no tiene hijos como los nodos A o C, se le conoce como nodo hoja.
• Se dice que un nodo n1 es un ancestro de un nodo n2 (y que n2 es un  descendiente de n1) si n1 es el padre de n2 o el padre de algún ancestro de n2.
• Recorrer un árbol de la raíz hacia las hojas se denomina descender el árbol, y al sentido opuesto, ascender el árbol.
• El nivel de un nodo en un árbol binario se define del modo siguiente:

1. La raíz del árbol tiene el nivel 0.
2. El nivel de cualquier otro nodo en el árbol es uno más que el nivel de su nodo padre.

• La profundidad o altura de un árbol binario, es el máximo nivel de cualquier hoja en el árbol.

   Por otro lado, se dice que un árbol estrictamente binario es aquel en el que cada nodo que no es hoja, tiene sus subárboles izquierdo y derecho no vacíos. En términos coloquiales, un árbol estrictamente binario es un árbol binario en el que cada nodo, tiene dos hijos o simplemente no tiene; es decir, no se vale tener un solo hijo: dos o nada.

   De lo anterior, observe que un árbol estrictamente binario con n hojas, siempre contiene 2n - 1 nodos (¿Por qué?).

   Otro tipo de árboles binarios son los árboles binarios completos. Un árbol binario completo de profundidad p, es un árbol estrictamente binario que tiene todas sus hojas en el nivel p.