Download Este material es de uso exclusivo para clase de algoritmos y

Este material es de uso exclusivo
para clase de algoritmos y
estructura de datos, la
información de este documento
fue tomada textualmente de
varios libros por lo que está
prohibida su impresión y
distribución.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Árboles
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Arboles
• Un árbol es una estructura de datos no lineal
formada por un conjunto de nodos.
• Son estructuras jerárquicas, cada elemento
puede tener diferentes siguientes elementos.
• El concepto de árbol implica una estructura en
la que los datos se organizan de modo que los
elementos de información están relacionados
entre sí a través de ramas
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Arboles
• Un árbol esta compuesto por un conjunto
finito de elementos, llamados nodos y un
conjunto finito ramas , que conectan a los
nodos.
• En un árbol existe un nodo especial llamado
raíz. Así mismo, un nodo del que sale una
rama, recibe el nombre de nodo de
bifurcación o nodo rama y un nodo que no
tiene ramas se le llama nodo hoja
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Como se aprecia en la figura cada nodo de un árbol
es la raíz de algún subárbol contenido en el. El
número de ramas de un nodo recibe el nombre de
grado del nodo.
• El nivel de un nodo respecto al nodo raíz se define
diciendo que la raíz tiene el nivel 0 cualquier otro
nodo tiene un nivel igual a la distancia de ese nodo al
nodo raíz. El máximo de los nivele se denomina
altura del árbol.
• Es útil limitar los arboles en el sentido de que cada
nodo sea a lo sumo de grado 2. De esta forma cabe
distinguir entre subárbol izquierdo y subárbol
derecho de un nodo. Los arboles así formados, se les
llama
Este arboles
material es debinarios.
uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Es necesario recordar:
• Un árbol consta de un conjunto finito de
elementos, denominados nodos y un conjunto
finito de líneas dirigidas llamadas ramas, que
conectan a los nodos. El numero de ramas
asociado con un nodo es el grado del nodo.
• Un árbol es una estructura recursiva (los
subarboles se definen como arboles)
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Nivel de un nodo es la distancia desde la raíz o
la longitud del camino que lo conecta a la raíz.
• La altura de un árbol es la longitud del camino
más largo que conecta la raíz a una hoja.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Un árbol binario es un árbol en el que ningún
nodo puede tener más de dos subárboles. En
un árbol binario cada nodo puede tener cero,
uno o dos hijos (subárboles). Se conoce el
nodo de la izquierda como hijo izquierdo y el
nodo de la derecha como hijo derecho.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Un árbol binario es una estructura recursiva,
existe un nodo denominado raíz. Cada nodo es la
raíz de su propio subárbol y tiene 0, 1 o 2 hijos,
que son raíces de árboles llamados subárboles
derecho e izquierdo del nodo respectivamente.
Un árbol binario se divide en tres subconjuntos
disjuntos:
• {R}
Nodo raíz
• {I1, I2, … In}
Subárbol izquierdo de R
• {D1, D2, … Dn}
Subárbol derecho de R
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Imagen de un árbol binario
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• En cualquier nivel n, un árbol binario puede contener de 1 a
2n nodos. El número de nodos por nivel contribuye a la
densidad del árbol.
• En la siguiente figura, el árbol de raíz 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, denominada árbol degenerado, en el que existe un
solo nodo hoja y cada nodo no hoja sólo tiene un hijo. Un
árbol degenerado es equivalente a una lista enlazada.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• La distancia de un nodo a la raíz determina la eficiencia con la
que ser localizado.
• Si dado cualquier nodo de un nodo árbol, a sus hijos se puede
llegar siguiendo sólo un camino de bifurcación o de ramas, el
que conduce al nodo solicitado. los nodos a nivel 2 de un
árbol sólo pueden ser llegar siguiendo un camino de sólo dos
ramas del árbol.
• La información anterior nos conduce a una característica
importante de un árbol binario, su balance o equilibrio. Para
determinar si un árbol está equilibrado, se calcula su factor de
equilibrio. El factor de equilibrio de un árbol binario es la
diferencia en altura entre los subárboles derecho e izquierdo.
Si so define la altura del subárbol izquierdo como HI y la altura
del subárbol derecho como HD, entonces el factor de
equilibrio del árbol B, se determina: B = HD -HI
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Utilizando esta fórmula el equilibrio del nodo raíz los dos
árboles de la figura anterior, (A) -1 y (B) 4.
• Un árbol está perfectamente equilibrado si su equilibrio o
balance es cero y sus subárboles son también perfectamente
equilibrados. Dado que esta definición ocurre raramente se
aplica una definición alternativa. Un árbol binario está
equilibrado si la altura de sus árboles difierenciarse en no
más de uno (su factor de equilibrio es -1, 0, +1) y sus
subárboles son también equilibrados.
• Un árbol binario está equilibrado si para cada nodo del árbol
la diferencia entre la altura de la rama derecha y, rama
izquierda es menor o igual que 1 (en valor absoluto).
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Un árbol binario completo de profundidad n es un árbol en el que
para cada nivel, del 0 al nivel n-1, tienen un conjunto lleno de nodos
y todos los nodos hijo a nivel n ocupan las posiciones más a la
izquierda del árbol.
• Un árbol binario, de profundidad n, completo que contiene 2n
nodos a nivel n es un árbol lleno. Un árbol lleno es un árbol binario
que tiene el máximo número de entradas para su altura. Esto
sucede cuando el último nivel está lleno. En la figura A muestra un
árbol binario completo.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Árbol completo de profundidad 4
El último caso de árbol es un tipo especial denominado árbol
degenerado en el que hay un solo nodo hoja (E) y cada nodo
no hoja sólo tiene un hijo. Un árbol degenerado es
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
equivalente
a una lista enlazada.
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• el árbol de la figura (a) es un árbol
degenerado y (b) corresponde con uno lleno.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Los árboles binarios y llenos de profundidad k+1 proporcionan
algunos datos matemáticos que es necesario comentar. En
cada caso, existe un nodo al nivel 0 (raíz), dos nodos (21) a
nivel 1, cuatro nodos (22) a nivel 2, etc. Se puede demostrar
que a través de los primeros k niveles (del nivel 0 al nivel k-1)
hay 2k -1 nodos, considerando la suma de la progresión
geométrica de razón 2:
• 1 + 2 + 4 + . . . + 2k-1 = 2k -1
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• A nivel k, el número de nodos adicionados para un árbol
completo está en el rango de un mínimo de 1 a un máximo de
2k (lleno). Con un árbol lleno, el número de nodos es:
• 1 + 2 + 4 + . . . + 2k-1 + 2k+1 -1
• El número de nodos n en un árbol binario completo de
profundidad k+1 (del nivel 0 al nivel k) cumple la inigualdad:
• 2k < n < 2k+1 -1 < 2k+1
• Aplicando logaritmos a la desigualdad anterior:
• k < log2 (n) < k + 1
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Se deduce que la altura o profundidad de un árbol binario
completo de n nodos es:
• H = |Log2 n| + 1 (parte de Log2 n + 1
• Por ejemplo, un árbol lleno de profundidad 4 (niveles 0 a 3)
tiene 24 -1 = 15 nodos.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Existen otros conceptos que definen las características del
árbol, en relación a su tamaño:
• Orden: es el número potencial de hijos que puede tener cada
elemento de árbol. De este modo, diremos que un árbol en el
que cada nodo puede apuntar a otros dos es de orden dos, si
puede apuntar a tres será de orden tres, etc.
• Grado: el número de hijos que tiene el elemento con más
hijos dentro del árbol.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Nivel: se define para cada elemento del árbol como la
distancia a la raíz, medida en nodos. El nivel de la raíz es cero
y el de sus hijos uno. Así sucesivamente.
• Altura: la altura de un árbol se define como el nivel del nodo
de mayor nivel. Como cada nodo de un árbol puede
considerarse a su vez como la raíz de un árbol, también
podemos hablar de altura de ramas.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Estructura de un Árbol Binario
• La estructura de un árbol binario se construye
con nodos. Cada nodo debe contener el
campo dato (datos a almacenar) y dos
campos apuntador, uno al subárbol izquierdo
y otro al subárbol derecho, que se conocen
como apuntador izquierdo (izquierdo, izdo.) y
apuntador
derecho
(derecho,
dcho.)
respectivamente. Un valor NULL indica un
árbol vacío.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• El algoritmo correspondiente a la estructura de un
árbol es el siguiente:
Nodo
subarbolIzquierdo
<apuntador a Nodo>
datos
<Tipodato>
subarbolDerecho
<apuntador a Nodo>
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
Fin Nodo
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• La figura muestra un árbol binario y su estructura en
nodos:
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Diferentes tipos de representaciones en C
• Los nodos se pueden representar con un de struct.
Suponiendo que el nodo tiene tres campos Datos, Izquierdo
(apuntador subárbol izquierdo) y Derecho (apuntador a
subárbol derecho):
Representación 1
typedef struct nodo *puntero_arbol;
struct nodo
{
int datos;
puntero_arbol hijoIzdo, hijoDcho;
}
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Representación 2
typedef int TipoElemento; es el tipo de los datos; puede ser
cualquier tipo ya definido.
struct Nodo
{
TipoElemento dato;
struct Nodo *izdo, *dcho;
};
typedef struct Nodo ElementoDeArbolBin;
typedef ElementoDeArbolBin *ArbolBinario;
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Creación de un Árbol Binario
A partir del nodo raíz de un árbol es posible llegar a los demás
nodos del árbol; por ello el apuntador que permite llegar al
árbol es el que referencia al raíz. La rama izquierda y derecha
son a su vez árboles binarios que tienen su raíz, y así
recursivamente hasta llegar a las hojas del árbol.
La formación del árbol pasa por la creación de cada uno de los
nodos y el enlace con el correspondiente nodo padre. Para
crear un nodo de un árbol binario, se reserva memoria para el
nodo, se asigna el dato al campo de datos y se inicializa los
apuntadores izdo y dcho a NULL.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
ArbolBinario crearNodo (TipoElemento x)
{
ArbolBinario a;
a = (ArbolBinario) malloc (sizeof(Nodo));
a -> dato = x;
a -> dcho = a -> izdo = NULL;
return a;
}
La función nuevoArbol ( ) crea un árbol cuya raíz es un nodo
nuevo que tiene como campo dato y es pasado como tercer
argumento. A su vez, la rama izquierda y derecha del árbol se
pasan como segundo y cuarto argumento.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
void nuevoArbol (ArbolBinario* raíz, ArbolBinario ramaIzqda,
TipoElementos x, ArbolBinario ramaDrcha)
{
*raíz = crearNodo(x);
(*raiz) -> izdo = ramaIzda;
(*raiz) -> dcho = ramaDrcha;
}
Como ejemplo: se establece un árbol binario de cadenas de
caracteres, siguiendo un esquema secuencial y utilizando la
estructura auxiliar Pila:
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
ArbolBinario raiz, al, a2;
Pila pila;
nuevoArbol(&al, NULL, "Maria", NULL);
nuevoArbol(&a2, NULL, "Rodrigo", NULL);
nuevoArbol(&raiz, al, "Esperanza", a2);
insertar(&pila, raiz);
nuevoArbol(&al, NULL, "Anyora", NULL);
nuevoArbol (&a2, NULL, "Abel" ,NULL);
nuevoArbol (&raiz, al', "M Jesus", a2) ;
insertar(&pila, raiz)
a2 = quitar(&pila);
al = quitar(&pila);
nuevoArbol
(&raiz,
a2)
;
Este material
es de al,
uso "Esperanza",
exclusivo para clase de
algoritmos
y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Operaciones en Árboles Binarios
Es necesario que árbol binario exista, para poder realizar las operaciones
sobre el.
El hacer uso de una operación u otra dependerá de la aplicación que se le
quiera dar al árbol.
Las operaciones típicas en árboles binarios son:
 Determinar su altura.








Determinar su número de elementos.
Determinar el número de nodos hoja.
Hacer una copia.
Visualizar el árbol binario en pantalla.
Determinar si dos árboles binarios son idénticos.
Borrar (eliminar el árbol).
Si es un árbol de expresión", evaluar la expresión.
Si es un árbol de expresión, obtener la forma de paréntesis de la
expresión.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Las operaciones se pueden realizar recorriendo el árbol binario
de un modo sistemático.
El recorrido de un árbol es la operación de vista al árbol, o lo
que es lo mismo, la visita a cada nodo del árbol una vez y sólo
una.
El recorrido de un árbol es necesario en muchas ocasiones, por
ejemplo si se quiere ver la información contenida en cada
nodo.
Existen diferentes formas de recorrer un árbol.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Profundidad y altura de un árbol binario
La profundidad de un árbol binario es una característica que
se necesita conocer con frecuencia durante el desarrollo de
una aplicación con árboles. La función profundidad ( )
determina la profundidad de un árbol binario. Para ello tiene
un parámetro que es un apuntador a la raíz del árbol.
• El caso más sencillo de cálculo de la profundidad es cuando el
árbol está vacío (raiz == NULL, o bien, ! raiz) en cuyo caso la
profundidad es 0. Si el árbol no está vacío, cada subárbol debe
tener su propia profundidad, por lo que se necesita evaluar
cada una por separado. Las variables profundidadI,
profundidadD almacenan las profundidades de los subárboles
izquierdo y derecho respectivamente.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
La altura es un concepto similar al de profundidad de un árbol. Un árbol
que tiene nodo raíz, se considera que su altura es 1, la altura del árbol:
es 2, y la altura del árbol:
es 4. Por último, si la altura de un árbol con un nodo es 1, la altura de un árbol
material es es
de uso
exclusivo
vacíoEste
(el puntero
NULL)
es 0.para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Función que determina la altura de un árbol binario de
manera recursiva.
Se considera que la altura de un árbol vacío es 0; si no está
vacío, la altura es 1 + máximo entre las alturas de rama
izquierda y derecha.
int altura(ArbolBinario r)
{
if (r == NULL)
return 0;
else
return (1 + max(altura(r->izdo), altura(r->dcho)));
}
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Número de hojas de un árbol binario
Muchas aplicaciones se necesita recorrer los nodos de un árbol pero sin
tomar en cuenta un orden de recorrido preestablecido.
La operación que determina el número de nodos que no tienen
descendientes visita cada nodo del árbol comprobando si tiene
descendientes, es decir, si es un nodo hoja.
La operación con la función contarhojas (); el nodo es hoja sí su rama
izquierda como derecha están a NULL, para visitar cada uno de los
nodos se utiliza el recorrido en preorden.
void contarhojas(ArbolBinario r, int* nh) {
if (r != NULL) {
contarhojas(r -> izdo, nh);
contarhojas(r -> dcho, nh); /* procesar raíz: determinar si es hoja */
if (r->izdo= =NULL && r->dchoa==NULL) (*nh)++; } }
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Eliminar los nodos de un árbol binario
Esta operación libera todos los nodos del árbol; se visita cada uno de los
nodos para borrar el nodo con la función free( ).
El recorrido del árbol se hace de tal forma que asegura la liberación de
la memoria ocupada por un nodo después de haber liberado su rama
izquierda y derecha.
La función eliminarbol(), antes de liberar el nodo se escribe el dato (se
supone de tipo entero).
void eliminarbol(ArbolBinario r) {
if (r != NULL) {
eliminarbol(r -> izdo);
eliminarbol (r -> dcho);
printf ("\tNodo borrado: %d ",r -> dato);
free(r) ; } }
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Árboles de Expresión
• Es una secuencia de tokens (componentes de léxicos que
siguen unas reglas establecidas). Un token puede ser o bien un
operando o bien un operador.
• La figura representa la expresión infija a * (b + c ) + d junto a su
árbol de expresión. El nombre de infija es debido a que los
operadores se sitúan entre los operandos. En una primera
observación vemos que los paréntesis de la expresión no
aparecen en el árbol y esto resulta muy interesante para la
evaluación de la expresión.
Un árbol de expresión es un árbol binario con las siguientes
propiedades:
 Cada hoja es un operando.
 Los nodos raíz y nodos internos son operadores.
 Los subárboles son subexpresiones en las que el nodo raíz es
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
un operador.
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Árboles de Expresión
• Es una secuencia de tokens (componentes de léxicos
que siguen unas reglas establecidas). Un token puede
ser o bien un operando o bien un operador.
• La figura representa la expresión infija a * (b + c ) + d
junto a su árbol de expresión. El nombre de infija es
debido a que los operadores se sitúan entre los
operandos. En una primera observación vemos que
los paréntesis de la expresión no aparecen en el árbol
y esto resulta muy interesante para la evaluación de la
expresión.
Un árbol de expresión es un árbol binario con las
propiedades:
1. Cada hoja es un operando.
2. Los nodos raíz y nodos internos son operadores.
3. Los subárboles son subexpresiones en las que el
nodo raíz es un operador.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Los árboles binarios se usan para representar expresiones en memoria;
esencialmente, en compiladores de lenguajes de programación. Se
muestra el árbol binario de expresión de (a + b) * c.
Note: que los paréntesis no se almacenan en el árbol pero están
implicados en la forma del árbol
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Si todos los operadores tienen dos operandos, se puede representar una expresión
con un árbol binario cuya raíz contiene un operador y cuyos subárboles izquierdo y
derecho son los operandos izquierdo y derecho.
• Cada operando puede ser una letra (x, y, a, b, etc.) o una subexpresión
representada como un subárbol.
• En la figura se puede ver cómo el operador que está en la raíz es *, su subárbol
izquierdo representa la subexpresión (x + y) y su subárbol derecho representa la
subexpresión (a - b).
• El nodo raíz delsubárbol izquierdo contiene el operador (+) de la subexpresión
izquierda y el nodo raíz del subárbol derecho contiene el operador (-) de la
subexpresión derecha. Todos los operandos letras se almacenan en nodos hojas.
Árbol de expresión (x + y) * (a - b).
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Reglas para la Construcción de Árboles de Expresión
Los árboles de expresiones se usan para evaluar expresiones usadas en
programas. El algoritmo más sencillo para construir un árbol de expresión
es aquel que lee una expresión completa que contiene paréntesis en la
misma. Una expresión con paréntesis es aquella en que:
La prioridad se determina sólo por paréntesis.
La expresión completa se sitúa entre paréntesis.
A fin de ver la prioridad en las expresiones, considérese la expresión, a *
c + e I g - (b + d)
Los operadores con prioridad más alta son * y /; es decir,
(a * c) + (e I g) - (b + d)
Los operadores que siguen en orden de prioridad son + y -, que se
evalúan de izquierda a derecha. Por consiguiente, se puede escribir, ((a *
c) + (e I g)) - (b + d)
Por último la expresión completa entre paréntesis será,
(((a*c) + Este
(e/g))
- (b+d))
material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
El algoritmo para la construcción de un árbol de expresión se expresa
en los siguientes pasos:
• La primera vez que se encuentra un paréntesis a izquierda, crea un
nodo y lo hace en el nodo raíz. Se llama a éste, el nodo actual y se
sitúa su apuntador en una pila.
• Cada vez que se encuentre un nuevo paréntesis a izquierda, crear
un nuevo nodo. Si el nodo actual no tiene un hijo izquierdo, hacer
al nuevo nodo el hijo izquierdo; en caso contrario, se crea el hijo
derecho. Hacer el nuevo nodo el nodo actual y situar su apuntador
en la pila.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Cuando se encuentra un operando, crear un nuevo
nodo y asignar el operando a su campo de datos. Si
el nodo actual no tiene un hijo izquierdo, crea al
nuevo nodo el hijo izquierdo; en caso contrario, crea
el hijo derecho.
• Cuando se encuentra un operador, sacar un
apuntador de la pila y situar el operador en el campo
datos del nodo del apuntador.
• Ignora los paréntesis derecho y blancos.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Recorrido de un árbol
Para consultar los datos almacenados en un árbol se necesita
recorrer el árbol o visitar los nodos del mismo. Al contrario que las
listas enlazadas, los árboles binarios no tienen un primer valor, un
segundo valor, tercer valor, etc. Se puede afirmar que el raíz viene
el primero, pero ¿quién viene a continuación?
Existen diferentes métodos de recorrido de árbol ya que la mayoría
de las aplicaciones binarias son bastante sensibles al orden en el
que se visitan los nodos, de forma que será necesario definir el tipo
de recorrido.
Un recorrido de un árbol binario requiere que cada nodo del árbol
sea procesado (visitado) una vez y sólo una, en una secuencia
predeterminada. Existen dos enfoques generales para la secuencia
de recorrido, profundidad y anchura.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
En el recorrido en profundidad, el proceso exige un camino desde el
raíz a través de un hijo, al descendiente más lejano del primer hijo
antes de proseguir a un segundo hijo. En otras palabras, en el
recorrido en profundidad, todos los descendientes de un hijo se
procesan antes del siguiente hijo.
En el recorrido a lo ancho, el proceso se realiza horizontalmente desde
el raíz a todos sus hijos, y enseguida a los hijos de sus hijos y así
sucesivamente hasta que todos los nodos han sido visitados.
En este recorrido cada nivel se procesa totalmente antes de que pase
al siguiente nivel. Dado un árbol binario que consta de un raíz, un
subárbol izquierdo y un subárbol derecho se pueden definir tres
tipos de secuencia de recorrido en profundidad.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Recorrido en Preorden
• El recorrido preorden2 (NID) conlleva los siguientes pasos, en los que el raíz va
antes que los subárboles:
– Recorrer el raíz (N)
– Recorrer el subárbol izquierdo (I) en preorden.
– Recorrer el subárbol derecho (D) en preorden.
•
Regla( En el recorrido preorder el raíz se procesa antes que-los subárboles
izquierdo y derecho.)
• Dado las características recursivas de los árboles y la definición recursiva del
recorrido, el algoritmo tiene naturaleza recursiva. Primero, se procesa la raíz, a
continuación el subárbol izquierdo y a continuación el subárbol derecho. Para
procesar el subárbol izquierdo, se hace una llamada recursiva al recorrido
preorden y luego se hace lo mismo con el subárbol derecho.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
• Preorden
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Recorrido en Inorder (orden)
El recorrido en orden (inorder) visita primero el subárbol izquierdo,
después el raíz y a continuación el subárbol derecho. El significado de
in es que la raíz se procesa entre los subárboles.
Sí el árbol no está vacío, el método implica los siguientes pasos:
1. Recorrer el subárbol izquierdo ,(I)en inorden.
2. Visitar el nodo raíz (N).
3. Recorrer el subárbol derecho (D) en inorden.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
En el árbol de la figura siguiente, los nodos se han numerado en
el orden en que son visitados durante el recorrido inorden.
El primer subárbol recorrido es el subárbol izquierdo del nodo
raíz (árbol cuyo nodo contiene la letra E).
Este subárbol consta de los nodos B,D y E, es a su vez otro árbol
con el nodo B como raíz, por lo que siguiendo el orden IND, se
visita primero D, a continuación B (nodo raíz) y por último E
(derecha).
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Después para el subárbol izquierdo se visita el nodo raíz A y por último se
visita el subárbol derecho que consta de los nodos C,F y G.
Siguiendo el orden IND para el subárbol derecho, se visita primero F, después
C (nodo raíz) y por último G.
Entonces el orden del recorrido inorden del árbol de la
figura, es D-B-E-A-F-C-G.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Recorrido en Postorden
El recorrido postorden (IDN) visita el nodo raíz (post) después de que los
subárboles izquierdo y derecho se han visitados. Se inicia situándose en la hoja
más a la izquierda y se procesa. Después se visita su subárbol derecho. Por
último se visista el nodo raíz. Las etapas del algoritmo son:
1.
2.
3.
Recorrer el subárbol izquierdo (I) en postorden.
Recorrer el subárbol derecho (D) en postorden.
Visitar el nodo raíz (N)
Recorriendo en postorden el árbol de la figura siguiente se visita primero el
subárbol izquierdo de A.
Este subárbol lo forman de los nodos B,D y E; siguiendo el orden IDN, se visitará
primero D(izquierdo), luego E (derecho) y por último B(nodo).
Enseguida se visita el subárbol derecho de A que esta formado por los nodos C, F y
G. Siguiendo el orden IDN para este árbol, se visita primero F (izquierdo),
después G(derecho)
y de
porusoúltimo
C (nodo).
final se visita
el nodo
raíz laA.
Este material es
exclusivo
para clase Al
de algoritmos
y estructura
de datos,
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
La secuencia de nodos que determina el recorrido en
postorden del árbol de la figura , es: D-E-B-F-G-C-A.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Árbol Binario de Búsqueda
• Los árboles binarios ordenados se disponen siguiendo un cierto orden, respecto
de un campo clave, de tal forma que para cualquier subárbol, los nodos de la
rama izquierda son menores que el raíz, y los nodos de la rama derecha son
mayores que el raíz.
• Los elementos de un árbol ordenado pueden ser eficientemente localizados, se
utiliza un algoritmo de búsqueda binaria similar al empleado en arrays.
• Un árbol binario de búsqueda es aquel en el que dado un nodo, todos los datos
del subárbol izquierdo son menores que el dato de ese nodo, mientras que
todos los datos del subárbol derecho son mayores que el dato del nodo.
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
Creación de un Árbol Binario de Búsqueda
El árbol binario de búsqueda se construye teniendo en cuenta las siguientes
supuestos:
 El primer elemento se utiliza para crear el nodo raíz del árbol.
 Los valores que guarda cada nodo del árbol deben ser tales que pueda existir
un orden. Es decir, debe existir un campo (entero, real, carácter, cadena)
respecto del cual se establece el orden del árbol.
 En cualquier nodo todos los valores del subárbol izquierdo del nodo son
menores al valor del nodo. De modo similar, todos los valores del subárbol
derecha deben ser mayores que los valores del nodo.
Con estas condiciones es sencillo probar que el recorrido inorden del árbol
produce una secuencia de valores en orden ascendente.
Por ejemplo, el árbol de búsqueda de caracteres, los tres tipos de recorrido para
el árbol:
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.
inorden
preorden
postorden
C E F G N P R T
N E C G F P T R
C F G E R T P N
Este material es de uso exclusivo para clase de algoritmos y estructura de datos, la
información de este documento fue tomada textualmente de varios libros por lo que
está prohibida su impresión y distribución.