Problemas estructuras de datos

Estructura de datos y de la informaci´n
o
Bolet´ de problemas - Tema 10
ın
1. En el caso de que sea posible, dar un ejemplo de los siguientes puntos.
Si no, explicar por qu´ no lo es. Considerar un valor gen´rico de n > 1.
e
e
a) Un ´rbol binario con n nodos cuya secuencia en Preorden y en
a
Inorden coincida.
b) Un arbol binario con n nodos cuya secuencia en Postorden y en
´
Inordencoincida.
c) Un ´rbol binario con n nodos cuya secuencia en Preorden y en
a
Postorden coincida.
2. Cada una de las siguientes sentencias es verdadera o falsa. Si es verdadera
explica por qu´ lo es, y si es falsa construye un ejemplo que lo demuestre.
e
a) X es descendiente de Y si, y solo si, Y precede a X en Preorden y
X precede a Y en Postorden.
b) X es descendiente de Y si, y solo si,Y precede a X en Preorden y
X precede a Y en Inorden.
c) Si X e Y son dos nodos hoja, su orden relativo es el mismo en:
1) Preorden e Inorden
2) Inorden y Postorden
3) Preorden y Postorden
3. Considerar las siete operaciones siguientes:
Procesar la ra´
ız.
Procesar el hijo izquierdo.
Procesar el hijo derecho.
Recorrer el sub´rbol izquierdo del hijo izquierdo.
a
Recorrer el sub´rbolderecho del hijo izquierdo.
a
Recorrer el sub´rbol izquierdo del hijo derecho.
a
Recorrer el sub´rbol derecho del hijo derecho.
a
a) Mostrar tres formas de ordenar estas siete operaciones de manera
que se correspondan con las tres formas naturales de recorrer un
arbol binario: preorden, inorden y postorden.
´
b) Otra manera de recorrer un arbol binario puede ser en orden de
´
niveles, dela siguiente manera:
1

si el ´rbol no es vac´o entonces
a
ı
nivel = 1
mientras nivel sea menor o igual a la profundidad del ´rbol
a
procesar todos los nodos del nivel actual
nivel = nivel + 1
Si es posible, representar este algoritmo con las siete operaciones
anteriores, y si no lo es explicar por qu´.
e
4. Implementar una funci´n que dado un arbol binario calcule su altura,
o
´teniendo en cuenta la siguiente definici´n recursiva: la altura de un arbol
o
binario vac´ es 0, en cualquier otro caso la altura es 1 m´s el mayor
ıo
a
entre la altura de su sub´rbol izquierdo y su sub´rbol derecho.
a
a
5. Suponer que se dispone de una funci´n que devuelve la altura de un ´rbol
o
a
binario:
int altura(const arbin &ab);
Utilizando esta funci´n y la estructura dedatos vista en clase para reo
presentar un ´rbol binario, implementar los algoritmos siguientes:
a
a) bool equilibrado(const arbin &ab); Dice si el ´rbol binario es
a
equilibrado.
b) bool completo(const arbin &ab); Dice si el arbol binario es com´
pleto.
c) bool extendido(const arbin &ab); Dice si el arbol binario es
´
extendido.
6. Otra forma de procesar un arbol binario es recorrerlo porniveles. El
´
algoritmo no es recursivo y en pseudoc´digo ser´
o
ıa:
Si el ´rbol no est´ vac´o entonces
a
a
ı
escribir la ra´z
ı
a~adir la ra´z a una cola
n
ı
mientras la cola no este vac´a
ı
sacar el frente de la cola
escribir sus hijos y a~adirlos a la cola (si no est´n vac´os)
n
a
ı
Implementar una funci´n que recorra y muestre el contenido de un arbol
o
´
binario porniveles.
7. Implementar una funci´n recursiva que dado un arbol binario contenieno
´
do una expresi´n matem´tica, devuelva el resultado de evaluar dicha
o
a
expresi´n. Para simplificar, supondremos que los operandos unicamente
o
´
son d´
ıgitos entre 0 y 9 y los operadores son: +, −, ∗ y /.
2

8. Considerar el siguiente algoritmo para recorrer un ´rbol binario en preora
den:
voidpreorden(const arbin &ab) {
if (!ab.EsVacio()) {
cout a[i]))
mayor= izq
else mayor= i;
if ((der < tam) && (a[der] > a[mayor]))
mayor = der;
if (mayor != i) {
9

intercambia(a, i, mayor);
reconstruir(a, mayor, tam); // Llamada recursiva
}
}

10

// Construye un mont´culo con los elementos del vector a
ı
void crear-monticulo(mont a) {
int j, tam;
tam= longitud_vector(a);...