Download Estructuras de Datos (Uva) Curso 2005

Estructuras de Datos (Uva)
Curso 2005-2006
Ejercicios de Árboles
1.- Construir un árbol binario de búsqueda mediante la inserción sucesiva de los
elementos con clave: 34, 67, 56, 24, 27, 19, 82, 33, 12, 77, 6 y 29. Indicar:
a) La raíz del árbol.
b) La altura del árbol.
c) La altura de cada uno de los nodos del árbol.
d) El nivel de cada uno de los nodos del árbol.
e) El grado del árbol.
f) El número de hojas del árbol.
g) El número de nodos interiores.
h) El número de nodos con un único descendiente.
i) El número de nodos con dos descendientes.
j) La secuencia de nodos en el recorrido enorden del árbol.
k) La secuencia de nodos en el recorrido en preorden del árbol.
l) La secuencia de nodos en el recorrido en postorden del árbol.
2.- Escribir una función que cuente y devuelva el número de nodos de un árbol
binario.
3.- Crear una función que devuelva la altura de un árbol binario y otra que
devuelva el nivel de un nodo en un árbol binario.
4.- Crear un procedimiento que almacene los datos de un árbol binario ordenado en
un archivo de texto.
5.- Crear tres funciones que devuelvan, respectivamente, el número de nodos con
ninguno (hojas), uno y dos descendientes directos que hay en un árbol binario.
6.- Escribir un procedimiento que libere de la memoria el espacio ocupado por
todos los datos dinámicos que almacenan los nodos de un árbol binario.
7.- Dado el árbol formado por la inserción sucesiva de los elementos con claves:
13, 7, 15, 3, 9, 17 y el procedimiento:
procedure po (A: tArbol);
begin
if A <> nil then
begin
po (A^.iz);
po (A^.de);
writeln (A^.info)
end
end;
si se realiza la llamada po (raiz), donde raiz es un puntero que apunta a la raíz del
árbol anterior, ¿cuál será el tercer valor escrito por pantalla?
8.- Dado el procedimiento tresp, indicar el número total de llamadas (incluyendo la
inicial) a dicho procedimiento, cuando se ejecuta la llamada tresp (p); y p señala la
estructura de la figura:
type puntero=^elem;
elem = record
1
info: integer;
iz, ce,de: puntero
end;
procedure tresp (r: puntero);
begin
if r <> nil then
begin
tresp (r^.iz);
tresp (r^.ce);
write (r^.info);
tresp (r^.de)
end;
9.- Se construye un árbol binario ordenado alfabéticamente mediante la inserción
sucesiva de los elementos con claves de tipo carácter m, f, x, g, t. Dibujar el árbol
resultante después de ejecutar el procedimiento pro (raiz) siendo raiz un puntero
externo al nodo raíz del árbol anterior.
procedure pro (var A: tArbol);
var B,C: tArbol;
begin
B := A^.iz;
C := A^.iz^de;
B^.de := C^.iz;
C^.iz := B;
A^.iz := C^.de;
C^.de := A;
A := C
end;
10.- Dado el procedimiento fibo, si efectuamos la llamada fibo (raiz, 4) visualizar el
resultado de recorrer enorden el árbol construido.
type ptr = ^nodo;
nodo = record
info: integer;
iz, de: ptr;
end;
var raiz: ptr;
procedure fibo (var r: ptr; altura: integer);
begin
if altura = 0 then r := nil
else if altura = 1 then
begin
new (r);
with r^ do begin
info := altura;
iz := nil;
de := nil
end
end
else begin
new (r);
r^.info := altura;
fibo (r^.iz, altura-2);
fibo (r^.de, altura-1);
end
end;
2