Árbol binario

Un árbol binario se puede definir como una estructura de datos utilizada en la ciencia de la computación. Esta estructura inicia con una raíz que luego se extiende en dos ramificaciones hasta que finalmente terminan en una hoja.

En otras palabras, se podría decir que un árbol binario inicia con un nodo que funciona como una raíz. Luego, de esa raíz se originan dos nuevos nodos o ramificaciones que se conocen como hijos.

Cada raíz solo puede tener dos hijos o ramificaciones. Por esa razón, se denomina árbol binario. Una ramificación se presenta hacia el lado derecho y la otra hacia el lado izquierdo.

Efectivamente, un árbol binario es una estructura de datos que relaciona información de manera jerárquica no lineal. Por ello, justamente recibe el nombre de árbol por la manera como se presenta la información. La información se estructura de forma ramificada como si fuera un árbol. Adicionalmente, es binario porque únicamente se desprenden dos ramas.

¿Cómo se estructura un árbol binario?

Para comenzar, un árbol binario representa un conjunto finito de elementos y todo el conjunto se divide en tres partes separadas o subconjuntos. Cada elemento que conforma el árbol binario se denomina nodo del árbol y cuando un nodo no tiene un hijo o un subárbol, se le conoce con el nombre de hoja.

Se estructura de la siguiente forma:

• Raíz: La raíz es el primer subconjunto y solo contiene un elemento.
• Subárbol izquierdo: Representa un segundo subconjunto y es igualmente un árbol binario. Se le reconoce como subárbol izquierdo del árbol original.
• Subárbol derecho: El tercer subconjunto es también un árbol binario y es conocido como el subárbol derecho del árbol original.

Clasificación de los nodos

Los nodos que forman un árbol binario se pueden clasificar de la siguiente forma:

• Nodo padre: Se conoce como nodo padre al nodo que origina otros nodos denominados hijos. Pero, es un nodo que no tiene padre o no se origina de otro.
• Nodo rama: Es un nodo que tiene la característica que tiene hijos y también tiene un padre. Es decir, se origina de otro nodo y de él derivan otros nodos.
• Nodo hoja: Este es un nodo que tiene padre, pero no tiene hijos. En este caso el nodo se deriva de otro nodo. Sin embargo, este nodo ya no origina otro.

Formas de recorrer un árbol binario

Ahora bien, el recorrido es el proceso de orden o secuencia que se debe utilizar para visitar los nodos que lo componen. Esto permite seguir un orden específico y determinar cómo se encuentra estructurada y organizada la información.

Un árbol binario puede ser recorrido siguiendo su amplitud o siguiendo su profundidad.

1. Recorrido en amplitud

Desde luego, el recorrido en amplitud se realiza cuando el recorrido en el árbol se realiza empezando en el nivel superior. Para posteriormente ir bajando hacia los niveles inferiores. Por ejemplo, si tuviéramos la siguiente gráfica de un árbol, el recorrido sería el siguiente:

12, 8, 17, 5, 9 y 15.

2. Recorrido en profundidad

Por otro lado, el recorrido en profundidad se efectúa cuando el recorrido se hace a lo largo de los subárboles. Para ello se puede seguir una secuencia distinta. Se puede seguir un proceso de preorden, orden central o postorden.

• Preorden: En este caso el recorrido inicia con la raíz, luego se recorre el subárbol izquierdo y el recorrido finaliza con el subárbol derecho. Cada subconjunto se analiza en preorden.
• Orden central: Por su parte, el recorrido en orden central empieza recorriendo el subárbol izquierdo, luego se pasa a la raíz y el recorrido termina con el subárbol derecho.
• Postorden: En cuanto al recorrido en postorden, se debe iniciar el recorrido en el subárbol izquierdo, se traslada luego al subárbol derecho y el recorrido finaliza en la raíz. Cada recorrido se hace en postorden.

En conclusión, se puede afirmar que un árbol binario es una estructura que es muy utilizada en la informática y también puede ser usada en las matemáticas. La parte fundamental para su estructura es el nodo. Dentro de los nodos se establecen relaciones. Un árbol binario solo puede tener dos ramificaciones y siempre termina en una hoja.