Arboles Binarios

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 20

ARBOLES BINARIOS

C
B

D E F

G
H I
• Se define un árbol binario como un conjunto
finito de elementos (nodos) que bien esta vacío o
esta formado por una raíz con dos arboles
binarios disjuntos, es decir, dos descendientes
directos llamados subárbol izquierdo y subárbol
derecho.
• Los árboles binarios (también llamados de grado
2 ) tienen una especial importancia.
• Las aplicaciones de los arboles binarios son muy
variadas ya que se les puede utilizar para
representar una estructura en la cual es posible
tomar decisiones con dos opciones en distintos
puntos.
Árbol binario de búsqueda.
• Los árboles binarios se utilizan
frecuentemente para representar conjuntos
de datos cuyos elementos se identifican por
una clave única. Si el árbol está organizado de
tal manera que la clave de cada nodo es
mayor que todas las claves su subárbol
izquierdo, y menor que todas las claves del
subárbol derecho se dice que este árbol es un
árbol binario de búsqueda.
OPERACIONES BÁSICAS
• Una tarea muy común a realizar con un árbol es ejecutar
una determinada operación con cada uno de los elementos
del árbol. Esta operación se considera entonces como un
parámetro de una tarea más general que es la visita de
todos los nodos o, como se denomina usualmente, del
recorrido del árbol.
• Si se considera la tarea como un proceso secuencial,
entonces los nodos individuales se visitan en un orden
específico, y pueden considerarse como organizados según
una estructura lineal. De hecho, se simplifica
considerablemente la descripción de muchos algoritmos si
puede hablarse del proceso del siguiente elemento en el
árbol, según un cierto orden subyacente.
• Hay dos formas básicas de recorrer un árbol: El recorrido en
amplitud y el recorrido en profundidad.
RECORRIDO DE UN ARBOL BINARIO
• Recorrido en amplitud

– Es aquel recorrido que recorre el árbol por niveles,


en el último ejemplo sería:

12 - 8,17 - 5,9,15
RECORRIDO EN PROFUNDIDAD
• Recorre el árbol por subárboles.
• Hay tres Preorden, orden central y postorden.
• Hay tres formas: 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 subárbol izquierdo en inorden.
– Examinar la raíz.
– Recorrer el subárbol derecho en inorden.
• PREORDEN
– Examinar la raíz.
– Recorrer el subárbol izquierdo en preorden.
– recorrer el subárbol derecho en preorden.
• POSTORDEN
– Recorrer el subárbol izquierdo en postorden.
– Recorrer el subárbol 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
Clasificación de Arboles Binarios
• ÁRBOL BINARIO DISTINTO
– Se dice que dos árboles binarios son distintos cuando sus
estructuras son diferentes.
• ÁRBOL BINARIO SIMILAR
– Dos arboles binarios son similares cuando sus estructuras son
idénticas, pero la información que contienen sus nodos es
diferente.
• ÁRBOL BINARIO EQUIVALENTE
– Son aquellos arboles que son similares y que además los nodos
contienen la misma información.
• ÁRBOL BINARIO COMPLETO
– Son aquellos arboles en los que todos sus nodos excepto los del
ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol
derecho.
TERMINOLOGÍA
• Hijo: X es hijo de Y, sí y solo sí el nodo X es apuntado
por Y. También se dice que X es descendiente directo
de Y.
• Padre: X es padre de Y sí y solo sí el nodo X apunta a Y.
También se dice que X es antecesor de Y.
• Hermano: Dos nodos serán hermanos si son
descendientes directos de un mismo nodo.
• Hoja: Se le llama hoja o terminal a aquellos nodos que
no tienen ramificaciones (hijos).
• Nodo anterior: Es un nodo que no es raíz ni terminal.
• Grado: Es el número de descendientes directos de un determinado
nodo.
• Grado de un árbol: Es el máximo grado de todos los nodos del
árbol.
• Nivel: Es el número de arcos que deben ser recorridos para llegar a
un determinado nodo. Por definición la raíz tiene nivel 1.
• Altura: Es el máximo número de niveles de todos los nodos del
árbol.
• Peso: Es el número de nodos del árbol sin contar la raíz.
• Longitud de camino: Es el número de arcos que deben ser
recorridos para llegar desde la raíz al nodo X. Por definición la raíz
tiene longitud de camino 1, y sus descendientes directos longitud
de camino 2 y así sucesivamente.
ÁRBOLES BINARIOS
• En cualquier nivel n, un árbol binario puede
contener de 1 a 2 nodos. El número de nodos
por nivel contribuye a la densidad del árbol.
• En la Figura (a) el árbol A contiene 8 nodos en
una profundidad de 4, mientras que el árbol
(b) contiene 5 nodos y una profundidad 5.
Este último caso es una forma especial,
denominado árbol degenerado, en el que
existe un solo nodo hoja ( E ) y cada nodo no
hoja sólo tiene un hijo. Un árbol degenerado
es equivalente a una lista enlazada.
ESTRUCTURA DE UN ÁRBOL BINARIO
• La estructura de un árbol se construye con
nodos. Cada nodo debe contener el campo
dato (datos a almacenar) y dos campos
punteros, uno al subárbol izquierdo y otro al
subárbol derecho, que se conocen como
puntero izquierdo (izquierdo, izdo) y puntero
derecho (derecho, dcho) respectivamente.
• Un valor NULL indica un árbol vacío.
Algoritmo de la estructura de un árbol
Nodo
subarbolIzquierdo < puntero a Nodo>
datos < Tipodato >
subarbolDerecho < puntero a Nodo>
Fin Nodo

También podría gustarte