Download Pr ctica N 4: Tipo de dato - Centro de Computación Gráfica

UNIVERSIDAD CENTRAL DE VENEZUELA
FACULTAD DE CIENCIAS
ESCUELA DE COMPUTACIÓN
ALGORITMOS Y ESTRUCTURAS DE DATOS
PRÁCTICA DE ÁRBOLES GENERALES Y BINARIOS
1.
2.
3.
4.
5.
6.
7.
Usando las primitivas de árboles generales desarrolle una función que retorne la suma de todos los enteros comprendidos entre
dos niveles.
Digamos que un árbol es semi-completo cuando sus nodos no hojas, tienen el mismo grado. Empleando las primitivas de árbol
general, elabora un algoritmo que permita saber si un árbol es semi-completo (el grado del árbol no se conoce).
Elabore los recorridos en inorden (también llamado simétrico) y preorden de árboles generales usando solamente el recorrido en
postorden (es decir, debe mostrar la secuencia de los primeros dos recorridos visitando el árbol de la forma Izquierdo-DerechoRaiz).
Se tiene el siguiente árbol genealógico representado gráficamente de la siguiente manera:
Implemente la operación primos (dado el nombre de una persona, imprimir a todos sus primos.
Usando las primitivas de árboles generales, implemente la operación PodarHojas, la cual consiste en eliminar todos aquellos
nodos que son hojas en un árbol.
Elabore un algoritmo empleando las primitivas de árbol general, que retorne el siguiente valor:
Valor(A) = Productoria(izquierdo(A)) - Productoria(derecho(A))
Donde Productoria(izquierdo(A)) es la productoria de todos nodos en el subárbol izquierdo de A, y Productoria(derecho(A))
corresponde con a la productoria de los nodos en el subárbol derecho de A. Sólo debe recorrer una sola vez cada nodo, y el perfil
de la función es el siguiente:
Función Valor (Arbol B)  Entero.
Considere la siguiente representación estática de árboles:
a
b
c
h
b
0
1
d
e
h
0
2
e
0
3
g
0
4
f
1
5
c
3
6
d
0
7
a
3
8
Info
Grado
Índice
f
g
8.
9.
Se puede ver que la forma de almacenamiento del árbol consiste en tener su recorrido en postorden definido en el arreglo (además
de tener el grado de cada nodo). ¿Qué desventajas podría tener este enfoque de almacenamiento estático? Basada en esta
representación defina las primitivas de Primer_Hijo, Hermano_Der y Padre. Sugerencia: Utilice una pila auxiliar.
Un árbol se dice cuasi-completo cuando todos sus nodos son hojas, o tienen el mismo grado. Empleando las primitvas de árbol
general, elabora un algoritmo que permita saber si un árbol es cuasi-completo (el grado del árbol no se conoce).
Indique cuáles de las siguientes afirmaciones son verdaderas o falsas. Justifique:
a. La altura del nodo de un árbol es la longitud del camino que va desde el nodo a la hoja.
b. La altura del nodo de un árbol viene dada por la altura del árbol menos el nivel del nodo.
c. Para cualquier árbol binario la secuencia que se produce al recorrerlo en preorden es diferente a la que se produce en
simétrico.
1
UNIVERSIDAD CENTRAL DE VENEZUELA
FACULTAD DE CIENCIAS
ESCUELA DE COMPUTACIÓN
ALGORITMOS Y ESTRUCTURAS DE DATOS
10. Generalice la forma de los árboles binarios cuyos nodos aparecen exactamente en el mismo orden en los recorridos:
a. Preorden y Simétrico
b. Postorden y Simétrico
c. Preorden y Postorden
11. Considere el problema de recorrer un árbol binario, por ejemplo en preorden. Para ello existen dos posibles soluciones:
a) Procedure PreOrden (Arbin A)
If not EsVacio(A) then
write(Raiz(A))
PreOrden(Izq(A))
PreOrden(Der(A))
EndIf
Faccion
b) Procedure PreOrden (Arbin A)
if not EsVacio(A) then
Tratar(Raiz(A))
If not EsVacio(Izq(A)) then
PreOrden(Izq(A))
EndIf
If not EsVacio(Der(A)) then
PreOrden(Der(A))
EndIf
EndIf
EndProcedure
¿Cuántas llamadas se realizan en cada caso? Exprese su respuesta en base al número de nodos del árbol
12. Dada la siguiente representación de árboles generales, elabore un algoritmo que, dado un árbol general, produzca su equivalente
en un árbol binario.
Class ArbGen
Nodo ^root;
EndClass
Class Nodo
Elem info
Nodo_Hijo ^Hijos
EndClass
Class Nodo_Hijo
ArbGen pNodo
Nodo_Hijo ^prox
EndClass
Type Nodo ^ArbGen;
Type Record Nodo
Elem info
Nodo_Hijo ^Hijos
EndRecord
Type Record Nodo_Hijo
ArbGen pNodo
Nodo_Hijo ^prox
EndRecord
4. Dada una secuencia en notación prefija y almacenada como una SECUENCIA[ELEMENTO], se desea que Ud. implemente una
operación utilizando las primitivas de Árboles binarios y del tipo Secuencia, que almacene dicha expresión en un árbol binario, tal que
si se recorre ese árbol en Simétrico se obtenga la expresión en notación infija. Los elementos de la secuencia pueden ser operadores u
operandos. Sobre dichos elementos se tiene definida la siguiente primitiva:
Funcion EsOperador (ELEMENTO E) → Lógico
si E  { + , - , * , / } entonces
 (Verdadero);
sino
 (Falso);
fsi
Ffuncion
Nota: Tome en cuenta que todos los operadores son binarios.
Ejemplo: Sea la secuencia S = { * + A B C }. Al aplicarle la operación Generar (var A: Arbin; S: Secuencia) y al recorrer el árbol
A en Simétrico, genera la secuencia:
A+B*C
13. Se tiene un lenguaje que no permite la recursión, y para simularla emplea una pila en la cual almacena en el caso de los árboles, el
camino recorrido desde la raíz hasta el nodo visitado. Se quiere que Ud. realice el algoritmo que permita recorrer un árbol binario
(Sin utilizar recursión) en Simétrico.
14. Usando las operaciones de ARBIN, desarrolle las siguientes operaciones:
a) Function EsHoja(Arbin A, Arbin X) : Boolean
2
UNIVERSIDAD CENTRAL DE VENEZUELA
FACULTAD DE CIENCIAS
ESCUELA DE COMPUTACIÓN
ALGORITMOS Y ESTRUCTURAS DE DATOS
Tal que EsHoja(A,X) = verdad Si y sólo sí Grado(raiz(X)) = 0 en el árbol A.
b) Function EsPadre(Arbin A, Arbin x, Arbin y) : Boolean
Tal que EsPadre(A,x,y) retorna true si y sólo si Raiz(x) es ascendiente directo de Raiz(y), y retorna false en caso contrario.
¿Qué modificaciones le haría a la estructura original para que EsPadre sea O(1)?
15. Utilizando las primitivas de la clase Arbin elabore un algoritmo que verifique si un árbol binario es completo.
16. Un Árbol Binario S está incluido en un Árbol Binario T, si S es igual a T o si S es igual a un subárbol de T. Escriba una función
que indique si un árbol S está incluido en un árbol T, en cuyo caso debe retornar la dirección del subárbol de T que es igual a S.
17. Escriba una función que verifique la simetría de un árbol binario cualquiera. Ejemplos:
Simétrico
No Simétrico
18. Se tiene la secuencia en preorden, postorden y simétrico de un árbol de n nodos almacenados en tres listas distintas. Realice un
algoritmo que determine si el nodo i es ascendiente del nodo j (para cualquier par de nodos i, j). ¿Sería posible elaborar dicho
algoritmo con sólo dos recorridos? Si su respuesta es afirmativa ¿Cuáles serían esos pares de recorridos, y elabore los
correspondientes algoritmos? Si su respuesta es negativa, justifique detalladamente el porqué. Elabore el (los) algoritmo (s) tanto
para árboles binarios como para árboles generales
GDAYED/2011
3