Download Clases de Arboles

ARBOLES
ESTRUCTURAS DE DATOS
2006
DEFINICION
Un árbol (tree) es un conjunto finito de
nodos.
Es una estructura jerárquica
aplicable sobre una colección de elementos
u objetos llamados nodos; uno de los cuales
es conocido como raíz.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
Los árboles representan las estructuras no
lineales y dinámicas. No lineales, puesto
que a cada elemento del árbol pueden
Dinámicas,
seguirle varios elementos.
puesto que la estructura árbol puede
cambiar durante la ejecución del programa.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
EJEMPLOS DE ARBOLES
Figura 1 :Árboles
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
CARACTERISTICAS Y PROPIEDADES DE
LOS ÁRBOLES EN GENERAL
Todo árbol que no es vacío, tiene un único nodo raíz.
Un nodo X es descendiente directo de un nodo Y, si el nodo X
apunta al nodo Y. X es hijo de Y.
Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta
al nodo Y. X es el padre de Y.
Se dice que todos los nodos que son descendientes directos
(hijos) de un mismo nodo (padre), son hermanos.
Todo nodo que no tiene ramificaciones (hijos) se conoce con el
nombre de terminal u hoja.
Todo nodo que no es raíz, ni terminal u hoja se conoce con
el nombre de interior.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
CARACTERISTICAS Y PROPIEDADES DE
LOS ÁRBOLES EN GENERAL
Grado es el número de descendientes directos de un
determinado nodo. Grado del á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 del árbol es el máximo número de niveles de todos los
nodos del árbol.
Rama es un camino desde el nodo raíz a una hoja.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
Figura 2 :Árbol General
A raíz del árbol
B es el hijo de A. C es hijo de A.
B es padre de D. D es padre de I.
B y C son hermanos. D, E, F son hermanos.
I, E, J, K, G, L son hojas.
B, D, F, C y H son nodos interiores.
Nivel del nodo A es 1. Nivel del nodo E es 3.
La altura del árbol es 4.
El grado de nodo A es 2
El grado de nodo B es 3
El grado de nodo C es 2
El grado de nodo D es 1
El grado de nodo E es 0
Grado del árbol es 3
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ÁRBOLES BINARIOS
Definición 1:
Un árbol binario es un árbol en el que cada nodo no puede tener mas
de dos hijos o descendientes. Es un árbol de grado 2.
Definición 2:
Un árbol binario es un conjunto finito de nodos, el cual puede ser vacío
o un conjunto que consta de un nodo raíz enlazado a dos árboles
binarios disjuntos denominados subárbol izquierdo y subárbol derecho.
Figura 3 :Árboles Binarios
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ÁRBOLES BINARIOS
TERMINOLOGIA
En un árbol binario los hijos se conocen como hijo izquierdo e hijo
derecho
Un nodo que no tiene hijos se denomina hoja. En la figura 4 B, C
son hojas.
El nodo raíz se dice que está en el nivel O en el árbol. Los nodos B y
C están en el nivel 1. (figura 4)
Altura del árbol se define como el nivel más alto del árbol. En la
figura 4 la altura del árbol es 2.
Figura 4 :Árbol Binario
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ÁRBOLES BINARIOS
TERMINOLOGIA
Un árbol binario está balanceado (equilibrado) si cada nodo tiene
exactamente dos hijos o no tiene hijos y si cada hoja está al mismo
nivel.
Figura 5 :Árbol Binario Equilibrado
Figura 6 :Árbol Binario no Equilibrado
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ÁRBOLES BINARIOS
TERMINOLOGIA
Los subárboles izquierdo y derecho de un árbol binario deben ser
subconjuntos disjuntos, esto es, ningún nodo puede estar en ambos
subárboles. Ejemplo:
(b)
(a)
Figura 7 :Árboles Binarios: a) no Disjunto. b) Disjunto
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ÁRBOLES BINARIOS DISTINTOS,
SIMILARES Y EQUIVALENTES
ÁRBOLES BINARIOS DISTINTOS
Dos árboles binarios son distintos cuando sus estructuras son
diferentes
Figura 8 :Árboles Binarios distintos
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ÁRBOLES BINARIOS DISTINTOS,
SIMILARES Y EQUIVALENTES
ÁRBOLES BINARIOS SIMILARES
Dos árboles binarios son similares cuando sus estructuras son
idénticas, pero la información que contiene sus nodos difiere entre sí.
Figura 9 :Árboles Binarios similares
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ÁRBOLES BINARIOS DISTINTOS,
SIMILARES Y EQUIVALENTES
ÁRBOLES BINARIOS EQUIVALENTES
Dos árboles binarios son equivalentes si son similares y además los
nodos contienen la misma información.
Figura 10 :Árboles Binarios equivalentes
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ÁRBOLES BINARIOS COMPLETOS
Se define como un árbol en el que todos sus nodos, excepto los del
último nivel, tienen dos hijos; el subárbol izquierdo y el subárbol
derecho.
Figura 11 :Árbole Binario completo
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
REPRESENTACION DE LOS ÁRBOLES
GENERALES COMO BINARIOS
Los pasos que se deben aplicar para lograr la conversión del árbol
general a binario son los siguientes:
Deben enlazarse los hijos de cada nodo en forma horizontal (los
hermanos).
Debe enlazarse en forma vertical el nodo padre con el hijo que se
encuentra más a la izquierda.
Debe rotarse el diagrama resultante, aproximadamente 45 grados
hacia la izquierda y así se obtendrá el árbol binario
correspondiente.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
REPRESENTACION DE LOS ÁRBOLES
GENERALES COMO BINARIOS
Figura 12 : Conversión de un árbol general en un árbol
binario. (a) Árbol general. (b) Árbol binario luego de
aplicar pasos 1 y 2. (c) Árbol binario luego de aplicar el
paso 3.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
REPRESENTACION DE LOS ÁRBOLES
GENERALES COMO BINARIOS
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
REPRESENTACION DE LOS ÁRBOLES
GENERALES COMO BINARIOS
Todo árbol binario obtenido a partir de un árbol general, debe cumplir lo
siguiente:
En la rama derecha de cada nodo, excepto el nodo raíz, si ésta es
distinta de vacío se encuentra un nodo que era hermano de éste en el
árbol general.
En la rama izquierda de cada nodo (si ésta es distinta de vacío), se
encuentra un nodo que era hijo de éste en el árbol generado.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
REPRESENTACION DE ÁRBOLES
BINARIOS EN MEMORIA
Existen dos formas tradicionales de representar un árbol binario en
memoria.
Por medio de listas enlazadas, variables dinámicas.
Por medio de arreglos.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
REPRESENTACION DE ÁRBOLES
BINARIOS EN MEMORIA. POR MEDIO DE
LISTAS ENLAZADAS.
Los nodos del árbol binario serán representadas como registros, que
contendrán como mínimo tres campos. En un campo se almacenará la
información del nodo. Los dos restantes se utilizarán para apuntar los
subárboles izquierdo y derecho respectivamente del nodo en cuestión.
Dado el siguiente nodo T:
Donde:
IZQ: campo donde se almacena la dirección del subárbol izquierdo del
nodo T.
INFO: campo donde se almacena la información de interés del nodo.
DER: campo donde se almacena la dirección del subárbol derecho del nodo
T.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
REPRESENTACION DE ÁRBOLES
BINARIOS EN MEMORIA. POR MEDIO DE
LISTAS ENLAZADAS.
La definición de un árbol binario en lenguaje algorítmico es como sigue.
Enlace = ˆ nodo
Nodo = registro
IZQ: tipo enlace
INFO: tipo dato
DER: tipo enlace
{Fin de la definición}
Nota: se utiliza ˆ para representar el concepto de dato tipo puntero.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
REPRESENTACION DE ÁRBOLES
BINARIOS EN MEMORIA. POR MEDIO DE
LISTAS ENLAZADAS.
Figura 13 : Representación de un árbol
binario en memoria. (a) Árbol binario. (b)
Árbol binario representación memoria.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
REPRESENTACION DE ÁRBOLES
BINARIOS EN MEMORIA. POR MEDIO DE
ARREGLOS.
(b)
2n-1= 24-1=16-1=15
(a)
Figura 14 : Representación de un árbol
binario en memoria. (a) Árbol binario. (b)
Árbol binario representación memoria con
arreglos.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
REPRESENTACION DE ÁRBOLES
BINARIOS EN MEMORIA. POR MEDIO DE
ARREGLOS.
Para calcular el número de elementos de un árbol es: 2n-1. n = nivel de
profundidad.
Dado un nodo I, padre de I
pos = [I/2]
Dado un nodo I, hijo izq.
pos = 2*I
Dado un nodo I; hijo der.
pos= 2* I + 1
Desventaja: el espacio que hay que dejar disponible, sino se le asigna
hijo izq. o der. el espacio se esta multiplicando. Cuando se trabaja con
árboles degenerados se pierde mucho espacio.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ÁRBOLES DE EXPRESIÓN
Los árboles binarios se utilizan para representar expresiones en
memoria, esencialmente en compiladores de lenguajes de programación
CONSTRUCCION DE ÁRBOLES DE EXPRESION
Los paréntesis no se almacenan en el árbol pero
están implicados en la forma del árbol. Si se supone que todos los
operadores tienen dos operandos, se puede representar una expresión
por un árbol binario cuya raíz contiene un operador y cuyos subárboles
izquierdo y derecho son los operandos izq. y der. respectivamente.
Cada operando puede ser una letra o una subexpresión representada
como un subárbol. Todos los operandos letras se almacenan en nodos
hojas.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ÁRBOLES DE EXPRESIÓN
Ejemplo 1: Dada la expresión (X+Y) * (A-B) construir el árbol de
expresión.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ÁRBOLES DE EXPRESIÓN
Ejemplo 3: Deducir la expresión que representa el siguiente árbol
binario.
1. X+Y
2. A*(X+Y)
3.(A*(X+Y)) *C
Sol: (A*(X+Y)) *C
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
RECORRIDOS EN ÁRBOLES BINARIOS
Recorrer un árbol binario significa visitar los nodos del árbol en
forma sistemática, de tal manera que todos los nodos del mismo sean
visitados una sola vez.
Existen tres formas diferentes de efectuar el recorrido (todos de
forma recursiva) los cuales son:
Recorrido en Preorden
Recorrido en Inorden
Recorrido en Posorden
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
RECORRIDOS EN ÁRBOLES BINARIOS
RECORRIDO EN PREORDEN
Visitar raíz (escribir la información del nodo).
Recorrer el subárbol izquierdo en preorden.
Recorrer el subárbol derecho en preorden.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
RECORRIDOS EN ÁRBOLES BINARIOS
Algoritmo:
Preorden (nodo)
Si nodo ≠ Nil entonces { Visitar el nodo (escribir nodo→Info)
Regresar a Preorden con (nodo→Izq)
Regresar a Preorden con (nodo→der) }
Fin.
El valor en cada nodo es procesado conforme se pasa por cada nodo.
Después de que se procese el valor de un nodo dado, son procesados
los valores del subárbol izquierdo y a continuación los valores en el
subárbol derecho.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
RECORRIDOS EN ÁRBOLES BINARIOS
RECORRIDO EN INORDEN
Recorrer el subárbol izquierdo en Inorden
Visitar raíz (procesar el valor en el nodo).
Recorrer el subárbol derecho en Inorden
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
RECORRIDOS EN ÁRBOLES BINARIOS
Algoritmo:
Inorden (nodo)
Si nodo ≠ Nil entonces { Regresar a Inorden (nodo→Izq)
Visitar el nodo (escribir nodo→Info)
Regresar a Inorden con (nodo→der) }
Fin.
El valor en un nodo no es procesado en tanto no sean procesados los
valores de su subárbol izquierdo.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
RECORRIDOS EN ÁRBOLES BINARIOS
RECORRIDO EN POSORDEN
Recorrer el subárbol izquierdo en Posorden
Recorrer el subárbol derecho en Posorden
Visitar raíz (procesar el valor en el nodo).
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
RECORRIDOS EN ÁRBOLES BINARIOS
Algoritmo:
Posorden (nodo)
Si nodo ≠ Nil entonces { Regresar a Posorden (nodo→Izq)
Regresar a Posorden con (nodo→der)
Visitar el nodo (escribir nodo→Info) }
Fin.
El valor en cada nodo no se imprime hasta que son impresos los
valores de sus hijos.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL
BINARIO UTILIZANDO STRUCT
DEFINICIÓN
#define NULL 0
struct nodo
{
struct nodo *izq;
tipo info;
struct nodo *der;
};
Con esta definición de ArbolB las operaciones asociadas especificadas
en el TAD quedarían del siguiente modo:
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL
BINARIO UTILIZANDO STRUCT
Inicializa el Árbol Binario a través del apuntador raíz.
void InicializarArbolB (struct nodo **raiz)
{
(*raiz)=NULL;
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL BINARIO
UTILIZANDO STRUCT
Crea un Árbol Binario con un solo nodo, el nodo Raíz.
struct nodo *CrearArbolB(int valor)
{
struct nodo *nuevo;
if (!ArbolBLleno())
{ nuevo = new nodo;
nuevo ->info = valor;
nuevo ->izq = NULL;
nuevo ->der = NULL;
return nuevo;
}
else
cout << "Árbol Overflow ";
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL BINARIO
UTILIZANDO STRUCT
A partir de dos árboles binarios y de un valor de tipo base, el resultado es
un nuevo árbol binario cuyo nodo raíz contiene el valor de tipo base y en el
que los árboles originales pasan a ser subárboles izquierdo y derecho.
struct nodo * CombArbolB(struct nodo *B1,struct nodo *B2, int valor)
{
struct nodo *nuevo;
if (!ArbolBLleno())
{ nuevo = CrearArbolB(valor);
nuevo->izq=B1;
nuevo->der=B2;
return nuevo;
}
else
cout << "Árbol Overflow ";
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL BINARIO
UTILIZANDO STRUCT
Inserta un nodo en el Árbol Binario como hijo Izquierdo.
bool InsHijoIzq(struct nodo *p, int valor)
{
struct nodo *nuevo;
if (p!=NULL)
if (!ArbolBLleno())
{ nuevo = CrearArbolB(valor);
p->izq = nuevo;
return true;
}
else
{ cout << "Nodo P No Existe ";
return false;
}
else
{ cout << "Árbol Overflow ";
return false;
}
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL BINARIO
UTILIZANDO STRUCT
Inserta un nodo en el Árbol Binario como hijo Derecho.
bool InsHijoDer(struct nodo *p, int valor)
{
struct nodo *nuevo;
if (p!=NULL)
if ((!ArbolBLleno()))
{ nuevo = CrearArbolB(valor);
p->der = nuevo;
return true;
}
else
{ cout << "Nodo P No Existe ";
return false;
}
else
{ cout << "Árbol Overflow ";
return false;
}
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL BINARIO
UTILIZANDO STRUCT
Dado un Árbol, elimina el nodo cuya dirección se envía como
parámetro en Ptr.
void ElimNodo(struct nodo *ptr)
{
struct nodo *ant;
struct nodo *temp;
temp = ptr;
if (ptr->der==NULL)
ptr=ptr->izq;
else if (ptr->izq==NULL)
ptr=ptr->der;
else
{
temp=ptr->izq;
ant=ptr;
while(temp->der!=NULL)
{ ant = temp;
temp = temp->der;
}
ptr->info = temp->info;
if (ant==ptr)
ant->izq = temp->izq;
else ant->der = temp->izq;
}
delete temp;
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL BINARIO
UTILIZANDO STRUCT
Dado un Árbol Binario devuelve la información almacenada en su nodo
raíz.
int DatoRaiz(struct nodo *p)
{
return p->info;
}
Devuelve el valor verdadero si el Árbol Binario está vacío y falso en
caso contrario.
bool ArbolBVacio(void)
{
return (raiz==NULL);
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL BINARIO
UTILIZANDO STRUCT
Devuelve el valor verdadero si el Árbol Binario está lleno y falso en
caso contrario.
bool ArbolBLleno(void)
{
struct nodo *p;
p = new nodo;
if (p!=NULL)
{
delete p;
return false;
}
else return true;
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL BINARIO
UTILIZANDO STRUCT
Permite que una vez que no se requiera más de la utilización del
Árbol Binario, liberar este espacio.
void LiberarNodos( const struct nodo Tree)
{
if (Tree != NULL)
{ LiberarNodos(Tree->izq);
LiberarNodos(Tree->der);
delete Tree;
}
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL BINARIO
UTILIZANDO STRUCT
Recorridos en el árbol binario
void RecorrerPreOrdenArbol (struct nodo **raiz)
{
if ((*raiz)!=NULL)
{
cout << " " << (*raiz)->info;
RecorrerPreOrdenArbol(&((*raiz)->izq));
RecorrerPreOrdenArbol(&((*raiz)->der));
}
}
void RecorrerInOrdenArbol (struct nodo **raiz)
{
if ((*raiz)!=NULL)
{
RecorrerInOrdenArbol (&((*raiz)->izq));
cout << " " << (*raiz)->info;
RecorrerInOrdenArbol (&((*raiz)->der));
}
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL BINARIO
UTILIZANDO STRUCT
Recorridos en el árbol binario
void RecorrerPostOrdenArbol (struct nodo **raiz)
{
if ((*raiz)!=NULL)
{
RecorrerPostOrdenArbol (&((*raiz)->izq));
RecorrerPostOrdenArbol (&((*raiz)->der));
cout << " " << (*raiz)->info;
}
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL BINARIO
UTILIZANDO STRUCT
Busca un elemento en el árbol binario
int EstaenArbol(struct nodo **raiz, int elem)
{
if ((*raiz)==NULL)
return 0;
else if (elem==((*raiz)->info))
return 1;
else return (EstaenArbol((&((*raiz)->izq)),elem) || EstaenArbol((&((*raiz)->der)),elem));
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ARBOL BINARIO DE BUSQUEDA
Un árbol binario de búsqueda (que no tiene los valores duplicados de
nodos) tienen la característica que los valores en cualquier subárbol
izquierdo son menores que el valor en sus nodos padres y los valores
en cualquier subárbol derecho son mayores que el valor en sus nodos
padres.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ARBOL BINARIO DE BUSQUEDA
Recorrido del árbol:
Preorden: 47 25 11 7 17 43 31 44 77 65 68 93
Inorden: 7 11 17 25 31 43 44 47 65 68 77 93
Posorden: 7 17 11 31 44 43 25 68 65 93 77 47
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
CREACION DE UN ARBOL BINARIO DE
BUSQUEDA
Supongamos que se desea almacenar los números: 8 3 1 20 10 5 4 en un
árbol binario de búsqueda. Siguiendo la regla, dado un nodo en el árbol
todos los datos a su izquierda deben ser menores que todos los datos del
nodo actual, mientras que todos los datos a ala derecha deban ser
mayores, que dichos datos. Inicialmente el árbol esta vacío y se le debe
insertar el 8.
A continuación viene el 3. Ya que 3 es menor que 8, el 3 debe ir en el
subárbol izquierdo.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
CREACION DE UN ARBOL BINARIO DE
BUSQUEDA
A continuación viene el 3. Ya que 3 es menor que 8, el 3 debe ir en el
subárbol izquierdo.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
CREACION DE UN ARBOL BINARIO DE
BUSQUEDA
A continuación se ha de insertar 1 que es menor que 8 y que 3; por lo
tanto irá a la izquierda y debajo de 3.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
CREACION DE UN ARBOL BINARIO DE
BUSQUEDA
Cada nuevo elemento se inserta como una hoja del árbol. Los restantes
elementos se pueden situar fácilmente.
Una propiedad de los árboles binarios de búsqueda es que no son únicos
para los datos dados.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
CREACION DE UN ARBOL BINARIO DE
BUSQUEDA
Ejemplo: Construir un árbol binario para almacenar los datos 12, 8, 7,
16 y 11.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
CONSTRUCCION DE UN ÁRBOL BINARIO
DE BÚSQUEDA A PARTIR DE RECORRIDO
INORDEN, PREORDEN, POSORDEN.
Si se dan los recorridos inorden y preorden se procede la siguiente
manera:
En el preorden el primer elemento es el nodo raíz y los siguientes son
nodo raíz de los demás.
Se busca en el inorden ese nodo raíz y se divide en subárbol izquierdo y
derecho.
En el preorden se busca el siguiente nodo raíz y en el inorden los
subárboles y así sucesivamente hasta agotar los valores.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
Ejemplo: Dado los valores:
Inorden 6 13 17 27 33 42 48
Preorden 27 13 6 17 42 33 48
Construir el árbol binario de búsqueda correspondiente.
•
Se busca en el preorden el primer elemento que es nodo raíz.
•
Se busca en el inorden ese valor y se divide en subárbol izquierdo y
derecho.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
•
Se busca en el preorden el siguiente nodo raíz y se subdivide en
subárbol izquierdo y derecho y así sucesivamente.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
Ejemplo: Un árbol binario tiene 10 nodos. El recorrido es inorden y
preorden. Son dados como sigue. Dibuje el árbol.
•Inorden: ABCEDFJGIH
•Preorden: JCBADEFIGH
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
Ejemplo: Dados los valores:
Inorden: 6 13 17 27 33 42 48
Posorden: 6 17 13 33 48 42 27
Construir el árbol binario de búsqueda correspondiente.
•
Se busca en el posorden el último valor que es el nodo raíz.
•
Se busca en inorden el valor y se divide en subárbol izquierdo y
derecho.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
•
Se busca en posorden siguiente nodo raíz que es 42.
•
Se busca en posorden siguiente nodo raíz que es 13.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
OPERACIONES DE BÚSQUEDA,
INSERCCION Y ELIMINACION
El árbol binario de búsqueda es una estructura sobre la cual se pueden
realizar eficientemente las operaciones de búsqueda, inserción y
eliminación.
Búsqueda (nodo, valor)
Algoritmo
Si nodo <> Nil
Entonces Si valor < nodo → info.
Entonces Búsqueda (nodo → izq., valor)
Sino Si valor > nodo → info.
Entonces Búsqueda (nodo → der., valor)
Sino escribir (“nodo existe”)
Fin
Fin
Sino escribir (“Nodo no se encuentra en el árbol”)
Fin.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
INSERCION EN UN ARBOL BINARIO DE
BUSQUEDA
•
Debe compararse la clave a insertar con la raíz del árbol. Si es
mayor, debe comenzarse hacia el subárbol derecho. Si es menor
debe comenzarse hacia el subárbol izquierdo.
•
Repetir sucesivamente el paso 1 hasta que se cumpla alguna de las
siguientes condiciones:
– el subárbol derecho es igual a vacío. El subárbol izquierdo es
igual a vacío, en cuyo caso se procederá a insertar el elemento
en el lugar que le corresponde.
– La clave que quiere insertarse es igual a la raíz del árbol; en
cuyo caso no se realiza la inserción.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
INSERCION EN UN ARBOL BINARIO DE
BUSQUEDA
Algoritmo
Si nodo <> Nil Entonces
Si valor < nodo → info.
Entonces Inserción (nodo → izq., valor)
Sino Si valor > nodo → info.
Entonces Inserción (nodo → der., valor)
Sino escribir (“nodo existe”)
Fin
Fin
Sino { crear (nuevo nodo)
Hacer nuevo nodo → izq. = Nil;
Hacer nuevo nodo → der. = Nil;
Nuevo nodo → info. = valor;
Nodo = nuevo nodo}
Fin.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
INSERCION EN UN ARBOL BINARIO DE
BUSQUEDA
Ejemplo: Supóngase que se quiere insertar los siguientes valores en un
árbol binario de búsqueda que se encuentra vacío.
95 80 72 60 82 81 84 100 110 105
Y así sucesivamente hasta que se agoten los valores.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
ELIMINACION EN UN ARBOL BINARIO
DE BUSQUEDA
Se debe distinguir los siguientes casos:
•
•
•
Si el nodo a borrar es terminal u hoja simplemente se suprime.
Si el nodo a borrar tiene un solo descendiente, entonces tiene que
sustituirse por ese descendiente.
Si el nodo a borrar tiene los dos descendientes entonces se tiene
que sustituir por el nodo que se encuentra más a la izquierda en el
subárbol derecho o por el nodo que se encuentra más a la derecha
en el subárbol izquierdo.
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
Algoritmo Eliminacion(nodo,infor)
1. Si nodo <> Nil Entonces
1.1 Si infor < nodo → info.
Entonces Eliminación (nodo → izq, infor)
Sino
1.1.1 Si infor > nodo → info
Entonces Eliminación (nodo → der, infor)
Sino hacer otro ← nodo
1.1.1.A Si otro → der = NULL
Entonces hacer nodo ← otro → izq
1.1.1. BSino Si otro → izq = NULL
Entonces hacer nodo ← otro → der
Sino hacer Aux ← otro → izq Y Aux1 ← Aux
1.1.1. CRepetir mientras Aux → der <> NULL
Hacer Aux1 ← Aux y Aux ← Aux → der
Fin.
Hacer otro → info ← Aux → info
otro ← aux Y Aux1 → der ← Aux → izq.
Fin (condicional del paso 1.1.1. B)
Fin (condicional del paso 1.1.1. A)
Fin (condicional del paso 1.1.1)
Fin (condicional del paso 1.1)
Quita (otro) {libera la memoria del nodo}
Sino escribir (“el nodo no se encuentra en el árbol”)
Ing. M.Sc. Fulbia Torres
Fin
Asignatura: Estructuras de Datos
Barquisimeto 2006
Ejemplo: Supóngase que se desea eliminar las siguientes claves del
árbol binario de búsqueda:
Claves: 22 – 99 – 87 – 120
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
Eliminación clave: 22
Eliminación clave: 99
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
Eliminación clave: 87
Eliminación clave: 120
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL
BINARIO DE BÚSQUEDA UTILIZANDO STRUCT
DEFINICIÓN
#define NULL 0
struct nodo
{
struct nodo *izq;
tipo info;
struct nodo *der;
};
Con esta definición de ArbolBB las operaciones asociadas especificadas
en el TAD quedarían del siguiente modo:
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL
BINARIO DE BÚSQUEDA UTILIZANDO STRUCT
Inicializa el Árbol Binario de búsqueda a través del apuntador raíz.
void CrearArbolBB (struct nodo **raiz)
{
(*raiz)=NULL;
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL
BINARIO DE BÚSQUEDA UTILIZANDO STRUCT
void InsercionValorArbol (struct nodo **raiz, int valor)
{
if ((*raiz)!=NULL)
if (valor<((*raiz)->info)) InsercionValorArbol(&((*raiz)->izq),valor);
else if (valor>((*raiz)->info)) InsercionValorArbol(&((*raiz)->der),valor);
else cout << "El nodo existe en el arbol\n";
else
{
struct nodo *n;
n=new nodo;
n->izq=NULL;
n->der=NULL;
n->info=valor;
(*raiz)=n;
}
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL
BINARIO DE BÚSQUEDA UTILIZANDO STRUCT
void EliminacionValorArbol (struct nodo **raiz, int valor)
{
struct nodo *Otro, *Aux, *Aux1;
Otro=new nodo; Aux=new nodo; Aux1=new nodo;
if ((*raiz)!=NULL)
{
if (valor<((*raiz)->info)) EliminacionValorArbol(&((*raiz)->izq),valor);
else if (valor>((*raiz)->info)) EliminacionValorArbol(&((*raiz)->der),valor);
else { Otro=*raiz;
if ((Otro->der)==NULL) (*raiz)=Otro->izq;
else { if ((Otro->izq)==NULL) (*raiz)=(Otro->der);
else { Aux=(Otro->izq);
Aux1=Aux;
while ((Aux->der)!=NULL)
{ Aux1=Aux;
Aux=(Aux->der);
}
(Otro->info)=(Aux->info);
Otro=Aux;
(Aux1->der)=(Aux->izq);
}
delete(Otro);
}
else cout << "El nodo no se encuentra en el arbol\n";
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL
BINARIO DE BÚSQUEDA UTILIZANDO STRUCT
Recorridos en el árbol binario
void RecorrerPreOrdenArbol (struct nodo **raiz)
{
if ((*raiz)!=NULL)
{
cout << " " << (*raiz)->info;
RecorrerPreOrdenArbol(&((*raiz)->izq));
RecorrerPreOrdenArbol(&((*raiz)->der));
}
}
void RecorrerInOrdenArbol (struct nodo **raiz)
{
if ((*raiz)!=NULL)
{
RecorrerInOrdenArbol (&((*raiz)->izq));
cout << “ " << (*raiz)->info;
RecorrerInOrdenArbol (&((*raiz)->der));
}
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL
BINARIO DE BÚSQUEDA UTILIZANDO STRUCT
Recorridos en el árbol binario
void RecorrerPostOrdenArbol (struct nodo **raiz)
{
if ((*raiz)!=NULL)
{
RecorrerPostOrdenArbol (&((*raiz)->izq));
RecorrerPostOrdenArbol (&((*raiz)->der));
cout << " " << (*raiz)->info;
}
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
IMPLEMENTACIÓN DINÁMICA DEL ÁRBOL
BINARIO DE BÚSQUEDA UTILIZANDO STRUCT
Busca un elemento en el árbol binario de búsqueda
void BusquedaValorArbol (struct nodo **raiz, int valor)
{
if ((*raiz)!=NULL)
if (valor<((*raiz)->info)) BusquedaValorArbol(&((*raiz)->izq),valor);
else
if (valor>((*raiz)->info)) BusquedaValorArbol(&((*raiz)->der),valor);
else cout << "El nodo existe\n";
else
cout << "El nodo no se encuentra en el arbol\n";
}
Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006
GRACIAS POR SU
ATENCIÓN
HASTA LA PRÓXIMA
CLASE