TEORIA DE ARBOLES

Árboles Binarios

Teoría general de Arboles binarios
Los árboles a diferencia de las listas son una estructura de datos de no lineal, atendiendo más a una estructura de tipo jerárquico. Los árboles son, sin duda, una de las estructuras de datos no lineales, empleadas en informática, tanto para resolver problemas de hardware como de software. Los árboles de directorios son organizaciones bastante empleadas por cualquier usuario o programador de una computadora. De igual manera cumplen un buen papel en la toma de decisiones, valido como árbol de decisiones.
Los árboles genealógicos y los organigramas son ejemplos comunes. Entre otras aplicaciones, los árboles se emplean para analizar circuitos eléctricos y para representar la estructura de fórmulas matemáticas, así como para organizar la información de bases de datos, para representar la estructura sintáctica de un programa fuente en compiladores y para la toma de decisiones.
Definición de árboles
Los árboles binarios son estructuras de datos muy similares a las listas doblemente enlazadas, en el sentido que tienen dos punteros que apuntan a otros elementos, pero no tienen una estructura lógica de tipo lineal o secuencial como aquellas, sino ramificada.  Tienen aspecto de árbol, de ahí su nombre.
Un árbol binario es una estructura de datos no lineal en la que cada nodo puede apuntar a uno o máximo a dos nodos. También se suele dar una definición recursiva que indica que es una estructura compuesta por un dato y dos árboles. Esto son definiciones simples. Este tipo de árbol se caracteriza porque tienen un vértice principal y de él se desprende dos ramas. La rama izquierda y la rama derecha a las que también se les conoce como subárboles.
Una representación gráfica de la estructura general de un árbol binario se puede visualizar en la imagen1 que presente a continuación.
Imagen 1. Estructura general de un árbol binario

La rama izquierda y la derecha, también son dos árboles binarios. El Vértice principal se denomina raíz y cada una de las ramas se puede denominar como subárbol izquierdo y subárbol derecho.

Representación gráfica del árbol binario y su recorrido en preorden


Veamos como se realiza el recorrido paso a paso según la gráfica del árbol de la imagen 3:
El recorrido inicia con el subárbol izquierdo, el primer nodo a visitar es  la raíz  que es el nodo 10, luego se visita el subárbol izquierdo  con el nodo 5,  posteriormente el 3, luego el nodo 1, sigue con el nodo 4, pasamos al nodo 7  y luego el 9.
Continuamos con el recorrido del subárbol derecho en preorden, con la  visita del  nodo 15, luego el 14, se continúa con el 17, se visita el 16  y  se finaliza con la visita del nodo 20.
 El resultado completo del recorrido en preorden para el árbol de la imagen es:  10 – 5 – 3 – 1 – 4 – 7 – 9 – 15 – 14 – 17 -16 – 20,  Tal como se muestra en la imagen 3.

Recorrido en  Inorden
Recorrer un árbol en Inorden  consiste en primer lugar en recorrer el subárbol izquierdo en Inorden, luego se examina el dato del nodo raíz, y finalmente  se recorre el subárbol derecho en  Inorden. Esto significa que para cada subárbol se debe conservar el recorrido en Inorden, es decir, primero se visita la parte izquierda, luego la raíz y posteriormente la parte derecha.
Imagen 4.  Representación grafica del árbol binario y su recorrido en Inorden

Veamos como se realiza el recorrido paso a paso según la grafica del árbol de la imagen 4:
El recorrido inicia con el subárbol izquierdo, el primer nodo a visitar es el  3 luego se visita el 5 y posteriormente el 7, con esto se garantiza que el recorrido del subárbol izquierdo se hizo en Inorden.
 Finalizado el recorrido del subárbol izquierdo se visita el nodo de la raíz, que para este caso es el numero 10.
 Solo queda recorrer el subárbol derecho en Inorden, es decir se visita el 11 luego el 12 y se finaliza con la visita del nodo 15
 El resultado completo del recorrido en Inorden para el árbol de la imagen es:3  –   5 –   7 –   10  –  11 –  12 – 15,  Tal como se muestra en la imagen.
Recorrido en Postorden:
Recorrer un árbol en Postorden  consiste en primer lugar en recorrer el subárbol izquierdo en Postorden, luego serecorre el subárbol derecho en  Postorden y finalmente se visita el nodo raíz. Esto significa que para cada subárbol se debe conservar el recorrido en Postorden, es decir, primero se visita la parte izquierda, luego la parte derecha y por último la raíz.
Imagen 5.  Representación grafica del árbol binario y su recorrido en postorden


Veamos como se realiza el recorrido paso a paso según la gráfica del árbol de la imagen 5.
El recorrido inicia con el subárbol izquierdo, el primer nodo a visitar es el  3 luego se visita el 7 y posteriormente el 5 que es la raíz, con esto se garantiza que el recorrido del subárbol izquierdo se hizo en Postorden.
Finalizado el recorrido del subárbol izquierdo se inicia la visita al subárbol derecho en Postorden, es decir, se visita el 11 luego el 15 y se finaliza con la visita del nodo 12 que sería la raíz de este subárbol.
Solo queda recorrer la raíz del árbol que para este caso es el número 10.
El resultado completo del recorrido en Postorden para el árbol de la imagen es:
3  –   7 –   5 –  11 –  15 – 12 – 10 Tal como se muestra en la imagen.
Árbol binario de búsqueda (ABB)
Los árboles binarios de búsqueda, son un tipo especial de árbol binario cuya característica radica en la forma ordenada de insertar sus elementos, facilitando así la búsqueda de un nodo en particular. Para puntualizar aun más, se tratarán los árboles binarios de búsqueda, en los que se tiene preestablecido un cierto orden, que seguramente ayudará a encontrar un cierto dato dentro de un árbol con mucha rapidez.
La pregunta sería;¿cómo es este orden prefijado o preestablecido?  La respuesta es sencilla y entenderlo es aun más,Solo se debe cumplir la condición que para cada nodo se tiene que:
 la rama de la izquierda contendrá elementos menores.
 la rama de la derecha contendrá elementos mayores.
Un ejemplo sería la forma más sencilla de explicarlo y comprenderlo.  Parimos de la siguiente gráfica del árbol binario de Búsqueda.
Imagen 6. Gráfica de un árbol binario de búsqueda


Partiendo de la gráfica del árbol de la imagen 6 realizaremos los tres recorridos, conservando el orden correspondiente para cada uno.
Recorrido en preorden:  20 – 13 – 9 – 6 – 10 – 18 – 14 – 17 – 32 – 26 – 24 – 29 – 36 – 34 – 40
Recorrido en inorden: 6 – 9 – 10 – 13 – 14 – 18 – 17 – 20 – 24 – 26 – 29 – 32 – 34 – 36 – 40
Recorrido en postorden: 6 – 10 – 9 – 14 – 17 – 18 – 13 – 24 – 29 – 26 – 34 – 40 – 36 – 32 – 20