Download ÁRBOLES BINARIOS

ÁRBOLES BINARIOS
♦
DEFINICIÓN
Un árbol binario es:
• Un objeto vacío.
• Ó, un nodo con dos árboles binarios llamados subárbol izquierdo y subárbol derecho
♦
JERARQUÍA
Todo árbol manifiesta relaciones de dependencia o parentesco entre sus nodos.
Si T = n1 ( n2 ( n3 , n4 (n5 , n6 ) ) , n7 ( , n8 ) ) entonces
Raíz(T) = n1
Padre(n5) = n4
Hijos(n4) = {n5, n6}
Primos(n8) = {n3, n4}
♦
DEFINICIONES
• Ruta: Es la secuencia de nodos n1, ..., nk de un árbol binario, de modo que ni es padre de ni+1,
∀ i=1..k-1. Por ejemplo, Ruta(n1, n5) = (n1, n2, n4, n5).
• Arco: Es la trayectoria entre dos nodos consecutivos.
• Longitud de ruta (módulo de ruta): Es la cantidad de arcos entre dos nodos.
|
Ruta(n1, n5)| = #(Ruta(n1, n5)) − 1 = Arcos(n1, n5) = 3.
• Hoja: Es un nodo que no tiene hijos.
• Nodo interior: Es un nodo que no es hoja.
• Altura: La altura de un nodo ni es h(ni) = max(|Ruta(ni, nk)|) donde nk es una hoja. Si n1 es la
raíz de un árbol T entonces h(n1) es la altura de T.
• Profundidad: Si n1 es la raíz de un árbol T entonces la profundidad de un nodo n i es p(ni) = |
Ruta(n1, ni)|.
• Nivel: El nivel de un nodo ni es su Profundidad.
• Grado: Es el número de descendientes directos de un nodo. El máximo de los grados para
todos los nodos de un árbol se conoce como grado del árbol. Luego, un árbol binario es un
árbol de grado 2.
• Árbol completo: El aquel que tiene todos sus niveles completos.
• Máximo de nodos de un árbol: El máximo número de nodos de un árbol se alcanza cuando
está completo. El número de nodos de un árbol completo de grado g y altura h es
N(g, h) =
g h +1 −1
g −1
Árbol binario ⇒ g = 2. Luego N(2, h) =
2 h +1 −
1
♦
RECORRIDO
En un árbol, un recorrido es una secuencia n1, ..., nk tal que ni ≠ nj ∀ i≠j y, además, para un nodo
cualquiera el siguiente nodo en la secuencia sólo puede ser su padre, un hijo ó su hermano. Por
ejemplo, si T = n1 (n2 (n3 , n4 ) , n5 ) entonces para el nodo n2 el siguiente nodo en la secuencia
sólo puede ser n1, n3 ó n4, o bien, n5.
Al recorrer un árbol binario, en cada nodo puede ocurrir uno de los tres siguientes eventos:
• Ejecutar alguna acción sobre la raíz (R)
• Recorrer el subárbol izquierdo (I)
• Recorrer el subárbol derecho (D)
Luego, existen seis posibles formas distintas de ordenar tales eventos:
RID, RDI, IRD, DRI, IDR, DIR
Sin embargo, por convención, siempre se recorre el subárbol izquierdo antes que el derecho,
razón por la cual existen tan sólo tres recorridos normalizados:
• Predorden (RID)
• Enorden (IRD)
• Postorden (IDR)
Formalmente, para un árbol binario T:
i) Si T = n entonces Preorden(T) = n
Enorden(T) = n
Postorden(T = n
ii) Si T = n ( Ti , Td )entonces Preorden(T) = n, Preorden(Ti), Preorden(Td)
Enorden(T) = Enorden(Ti), n, Enorden(Td)
Postorden(T) = Postorden(Ti), Postorden(Td), n
Representación de un árbol binario en lenguaje C:
typedef struct nodo
{ int dato;
struct nodo *izq;
struct nodo *der;
}nodo;
typedef nodo *ab;
Implementar, en lenguaje C, operadores para imprimir el contenido de un árbol binario t según
los tres recorridos normalizados.
void imprimerid(ab t)
{ if (t != NULL)
{ printf ("%d", t->dato);
imprimerid(t->izq);
imprimerid(t->der);
}
}
void imprimeird(ab t)
{ if (t != NULL)
{ imprimeird(t->izq);
printf ("%d", t->dato);
imprimeird(t->der);
}
}
void imprimeidr(ab t)
{ if (t != NULL)
{ imprimeidr(t->izq);
imprimeidr(t->der);
printf ("%d", t->dato);
}
}
ÁRBOLES DE EXPRESIONES
Un árbol binario de expresión (ABE) es un árbol binario utilizado para representar una expresión
aritmética de la siguiente manera:
• Cada hoja contiene un operando.
• Cada nodo interior contiene un operador aritmético.
Un ABE tiene información implícita sobre prioridad de operadores y asociatividad.
Sea T un ABE compuesto de un nodo N y subárboles izquierdo T i y derecho Td. La evaluación de
T se efectúa de acuerdo al siguiente algoritmo:
• Si Ti y Td son árboles vacíos, entonces el valor de T es el valor contenido en N.
• Si Ti y Td son árboles no vacíos, entonces el valor de T es el valor de T i operado con el valor
de Td según el operador contenido en N.
Representación de un ABE en lenguaje C:
typedef struct nodo
{ int hoja;
union
{ float valor;
char signo;
}var;
struct nodo *izq;
struct nodo *der;
}nodo;
typedef nodo *arbex;
Con respecto a un árbol binario de expresión t, implementar en lenguaje C operadores para
evaluar la expresión que t representa e imprimir el contenido de t.
float evalua(arbex t)
{
if (t != NULL)
if (t->hoja)
return t->var.valor;
else
switch (t->var.signo)
{ case ’+’: return evalua(t->izq) + evalua(t->der);
case ’−’: return evalua(t->izq) − evalua(t->der);
case ’∗’: return evalua(t->izq) ∗ evalua(t->der);
case ’/’: return evalua(t->izq) / evalua(t->der);
default: printf(“Error”);
}
}
void imprime(arbex t)
{ if (t != NULL)
if (t->hoja)
printf(t->var.valor);
else
{ printf ("(");
imprime(t->izq);
printf ("%c", t->var.signo);
imprime(t->der);
printf (")");
}
}