Arboles Binarios y sus aplicaciones

El árbol binario es el caso más simple de árbol de orden N, cuando N vale 2. Su
especificación se puede hacer considerando un valor constante, el árbol nulo, y un constructor
de árboles a partir de un elemento y dos árboles.
Para saber el contenido de todos los nodos en un árbol es necesario recorrer el árbol. Esto es debido a que solo tenemos conocimiento del contenido de la dirección de un nodo a la vez. Al recorrer el árbol es necesario tener la dirección de cada nodo, no necesariamente todos al mismo tiempo, de hecho normalmente se tiene la dirección de uno o dos nodos a la vez; de manera que cuando se tiene la dirección de un nodo, se dice que se visita ese nodo.

Un árbol binario es una estructura de datos útil cuando se trata de hacer modelos de procesos en donde se requiere tomar decisiones en uno de dos sentidos en cada parte del proceso. Por ejemplo, supongamos que tenemos un arreglo en donde queremos encontrar todos los duplicados. Esta situación es bastante útil en el manejo de las bases de datos, para evitar un problema que se llama redundancia.

Una manera de encontrar los elementos duplicados en un arreglo es recorrer todo el arreglo y comparar con cada uno de los elementos del arreglo. Esto implica que si el arreglo tiene $ n$ elementos, se deben hacer $ n$ comparaciones, claro, no es mucho problema si $ n$ es un número pequeño, pero el problema se va complicando más a medida que $ n$ aumenta.

Si usamos un árbol binario, el número de comparaciones se reduce bastante, veamos cómo.

El primer número del arreglo se coloca en la raíz del árbol (como en este ejemplo siempre vamos a trabajar con árboles binarios, simplemente diremos árbol, para referirnos a un árbol binario) con sus subárboles izquierdo y derecho vacíos. Luego, cada elemento del arreglo se compara son la información del nodo raíz y se crean los nuevos hijos con el siguiente criterio:

* Si el elemento del arreglo es igual que la información del nodo raíz, entonces notificar duplicidad.
* Si el elemento del arreglo es menor que la información del nodo raíz, entonces se crea un hijo izquierdo.
* Si el elemento del arreglo es mayor que la información del nodo raíz, entonces se crea un hijo derecho.

Una vez que ya está creado el árbol, se pueden buscar los elementos repetidos. Si x el elemento buscado, se debe recorrer el árbol del siguiente modo:

Sea k la información del nodo actual p. Si X>K entonces cambiar el nodo actual a right(p), en caso contrario, en caso de que X=k informar una ocurrencia duplicada y en caso de que X >= K cambiar el nodo actual a left(p).

El siguiente algoritmo

leer numero buscado >> n
tree=makeTree(n)
while(hay numeros en el arreglo){
leeSiguienteNumero >> k
p=q=tree;
while(k!=info(p)&&q!=NULL){
p=q
if(k
q=left(p)
else
q=right(p)
}
if(k==info(p))
despliega<<" el numero es duplicado"; else if (k
setLeft(p,k)
else
setRight(p,k)
}

Aunque hay un orden preestablecido (la enumeración de los nodos) no siempre es bueno recorrer el árbol en ese orden, porque el manejo de los apuntadores se vuelve más complejo. En su lugar se han adoptado tres criterios principales para recorrer un árbol binario, sin que de omita cualquier otro criterio diferente.

Los tres criterios principales para recorrer un árbol binario y visitar todos sus nodos son, recorrer el árbol en:

preorden:
Se ejecutan las operaciones:

1. Visitar la raíz
2. recorrer el subárbol izquierdo en preorden
3. recorrer el subárbol derecho en preorden

entreorden:
Se ejecutan las operaciones:

1. recorrer el subárbol izquierdo en entreorden
2. Visitar la raíz
3. recorrer el subárbol derecho en entreorden

postorden:
Se ejecutan las operaciones:

1. recorrer el subárbol izquierdo en postorden
2. recorrer el subárbol derecho en postorden
3. Visitar la raíz

Al considerar el árbol binario que se muestra en la figura:

usando cada uno de los tres criterios para recorrer el árbol se tienen las siguientes secuencias de nodos:

En preorden: 14,4,3,9,7,5,15,18,16,17,20

En entreorden:3,4,5,7,9,14,15,16,17,18,20

En postorden: 3,5,7,9,4,17,16,20,18,15,14

Esto nos lleva a pensar en otra aplicación, el ordenamiento de los elementos de un arreglo.

Para ordenar los elementos de un arreglo en sentido ascendente, se debe construir un árbol similar al árbol binario de búsqueda, pero sin omitir las coincidencias.

El árbol de ordenamiento es el que se muestra Para ordenar los elementos de este arreglo basta recorrer el árbol en forma de entreorden.

se podría decir que un árbol binario se define como un conjunto finito de elementos llamados nodos. En estos casos se puede usar terminología de relaciones familiares para descubrir las relaciones entre los nodos de un árbol; y que un árbol puede ser implementado fácilmente en una computadora.

En Conclusion es bueno hacer énfasis en esto ya que se puede saber mucho sobre lo que tiene que ver con los árboles; entre las cosas que podemos mencionar se encuentra la raíz, los nodos de un árbol y la diferencia entre nodos sucesores y nodos terminales, como se muestran en el contenido del trabajo. Por ultimo dejo este video muy Ilustrativo acerca del recorrido de un arbol binario.

Bibliografia
http://computacion.cs.cinvestav.mx/~acaceres/courses/estDatosCPP/node53.html

http://foro.elhacker.net/programacion_cc/arboles_binarios-t293011.0.html;msg1451005