informatica



REPUBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA EDUCACION SUPERIOR
INSTITUTO UNIVERSITARIO DE MERCADOTECNIA ISUM











AUTOR:
PICHARDO MAIKER CI 14384392
DOCENTE: ROLON
CARACAS 13/04/2013
Introducción

A los arboles ordenados de grado dos se les conoce como arboles binarios ya que cada nodo del árbol no tendrá más de dos descendientesdirectos. Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructuras en la cual es posible tomar decisiones con dos opciones en distintos puntos.



La representación gráfica de un árbol binario es la siguiente:












Clasificación de Árboles Binarios
Existen cuatro tipos de árbol binario:
A. B. Distinto.
A. B.Similares.
A. B. Equivalentes.
A. B. Completos.
A continuación se hará una breve descripción de los diferentes tipos de árbol binario así como un ejemplo de cada uno de ellos.
A. B. DISTINTO
Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes. Ejemplo:

A. B. SIMILARES
Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la informaciónque contienen sus nodos es diferente. Ejemplo:

A. B. EQUIVALENTES
Son aquellos arboles que son similares y que además los nodos contienen la misma información. Ejemplo:

A. B. COMPLETOS
Son aquellos arboles en los que todos sus nodos excepto los del último nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho
Recorrido de un Árbol Binario
Hay tres maneras de recorrer un árbol:en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:
INORDEN
Recorrer el subarbol izquierdo en inorden.
Examinar la raíz.
Recorrer el subarbol derecho en inorden.
PREORDEN
Examinar la raíz.
Recorrer el subarbol izquierdo en preorden.
recorrer el subarbol derecho en preorden.
POSTORDEN
Recorrer elsubarbol izquierdo en postorden.
Recorrer el subarbol derecho en postorden.
Examinar la raíz.
A continuación se muestra un ejemplo de los diferentes recorridos en un árbol binario.

Inorden: GDBHEIACJKF
Preorden: ABDGEHICFJK
Postorden: GDHIEBKJFCA
5.5 Arboles Enhebrados
Existe un tipo especial de árbol binario llamado enhebrado, el cual contiene hebras que pueden estar a la derecha o a laizquierda. El siguiente ejemplo es un árbol binario enhebrado a la derecha.

ARBOL ENHEBRADO A LA DERECHA. Este tipo de árbol tiene un apuntador a la derecha que apunta a un nodo antecesor.
ARBOL ENHEBRADO A LA IZQUIERDA. Estos árboles tienen un apuntador a la izquierda que apunta al nodo antecesor en orden
Salvo que trabajemos con árboles especiales, como los que veremos más adelante, lasinserciones serán siempre en punteros de nodos hoja o en punteros libres de nodos rama. Con estas estructuras no es tan fácil generalizar, ya que existen muchas variedades de árboles.
De nuevo tenemos casi el mismo repertorio de operaciones de las que disponíamos con las listas:
Añadir o insertar elementos.
Buscar o localizar elementos.
Borrar elementos.
Moverse a través del árbol.
Recorrer el árbolcompleto.
Los algoritmos de inserción y borrado dependen en gran medida del tipo de árbol que estemos implementando, de modo que por ahora los pasaremos por alto y nos centraremos más en el modo de recorrer árboles.
6.4 Recorridos por árboles:
El modo evidente de moverse a través de las ramas de un árbol es siguiendo los punteros, del mismo modo en que nos movíamos a través de las listas.Esos recorridos dependen en gran medida del tipo y propósito del árbol, pero hay ciertos recorridos que usaremos frecuentemente. Se trata de aquellos recorridos que incluyen todo el árbol.
Hay tres formas de recorrer un árbol completo, y las tres se suelen implementar mediante recursividad. En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una.
Supongamos que...