Aplicaciones de árboles binarios

Universidad Autónoma del Estado de Hidalgo

Instituto de Ciencias Básicas e Ingenierías.

Estructura de Datos II

“Aplicación de árboles binarios”

5° semestre Grupo 4

Sandra Ramírez Álvarez

Semestre: Enero – Junio.







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 dossentidos 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  elementos, se deben hacer comparaciones, claro, no es mucho problema si  es un número pequeño, pero el problema se va complicando más a medida que  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 quela 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  entonces cambiar el nodo actuala right(p), en caso contrario, en caso de que  informar una ocurrencia duplicada y en caso de que  cambiar el nodo 
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 almismo 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 sevisita ese nodo.
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 criteriosprincipales 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
Esto nos lleva a pensar en otra aplicación, el ordenamiento de los elementos de un arreglo.
Para ordenar los elementos de unarreglo en sentido ascendente, se debe construir un árbol similar al árbol binario de búsqueda, pero sin omitir las coincidencias.
Tipos de árboles binarios:
Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
Un árbol binario perfecto es un árbol binario lleno en el que todas...