Download Solución Práctico 4

Ejercicios Resueltos del Práctico 4
Ejercicio 2
Considere la representación para Lista de Naturales y Árbol Binario de Naturales de la Figura 1.
1
2
3
4
5
struct NodoLista {
int elem ;
NodoLista * sig ;
};
6
7
typedef NodoLista * LNat ;
8
9
10
11
12
13
struct Nodo {
int elem ;
Nodo * left , * right ;
};
typedef Nodo * BinaryTree ;
Figura 1: Definición del tipo lista de naturales y árbol binario de naturales.
(a) Utilícelas para implementar las siguientes operaciones:
i. LNat inOrder (BinaryTree t); /* Devuelve la lista de los elementos del árbol t, según la
recorrida en orden de t */
ii. LNat preOrder (BinaryTree t); /* Devuelve la lista de los elementos del árbol t, según la
recorrida en preorden de t */
iii. LNat postOrder (BinaryTree t); /* Devuelve la lista de los elementos del árbol t, según la
recorrida en posorden de t */
iv. bool isPath (LNat l, BinaryTree t); /* Devuelve TRUE si y sólo si l es un camino, desde
la raíz a un hoja, de t */
v. LNat LongestPath (BinaryTree t); /* Devuelve una lista con los elementos del camino más
largo de t (desde la raíz a una hoja). En caso de haber más de un camino de igual longitud a
la del camino más largo, retorna cualquiera de ellos */
(b) ¿Cuántos nodos tiene como mínimo y cómo máximo el camino más largo desde la raíz a una hoja,
para un árbol de n nodos? Justifique.
(c) ¿Cuántos nodos tiene un árbol binario completo (perfectamente balanceado) de altura h? Escriba
una función booleana que dados un árbol binario a y un natural h, retorne TRUE si, y sólo si, a
es un árbol completo de altura h. Implemente dicha función sin usar operaciones auxiliares para
calcular la cantidad de nodos o la altura de un árbol.
Análisis del problema para las funciones inOrder, preOrder y postOrder
Estas tres funciones consisten en recorrer los nodos del árbol en determinado orden e ir insertando los
elementos de los mismos en una lista a retornar. Los elementos en la lista resultante quedan ordenados según
el criterio de orden utilizado para recorrer el árbol.
Asumiendo que el subárbol izquierdo (I) se debe visitar siempre antes que el subárbol derecho (D) lo
que resta es definir en qué momento se visita la raíz del árbol (R). Esto da origen a tres recorridas posibles:
en orden (IRD), en pre orden (RID) y en post orden (IDR). Los nombres de las mismas refieren en que
momento se visita la raíz del árbol.
Estos tres problemas se pueden resumir en el siguiente problema general. Dado un orden O y un árbol
A, obtener una lista L que contenga a los elementos de A según el orden O. Para obtener L se propone una
solución recursiva, donde en cada paso se cuenta con dos listas: una que representa la recorrida según O del
subárbol izquierdo de A (LI) y otra que representa la recorrida según O del subárbol derecho de A (LD).
En cada paso se genera además una nueva lista, de un sólo elemento, que contiene al elemento en la raíz del
árbol (LR). Luego, en cada paso, resta generar la salida, la cual consiste en combinar LI, LD y LR según O.
Por ejemplo, para el caso en orden la salida es LI,LR,LD.
Instituto de Computación - Facultad de Ingeniería - UdelaR
Página 1 de 5
Solución
Del análisis anterior sabemos que podemos construir una solución recursiva combinando en cada paso
las listas generadas en un paso anterior con una lista de un sólo elemento que se genera en cada paso. Para
ahorrarse la creación de la lista de un sólo elemento podemos pensar en insertar dicho elemento al comienzo o
al final de alguna de las listas previamente generadas y luego pegando las dos listas resultantes. Continuando
con el ejemplo del caso en orden podríamos hacer LD’=R.LD (lo que es equivalente a LD’=Cons(R,LD) ) y
luego concatenar LI y LD’. Siguiendo esta estrategia para el caso de post orden es necesario contar con una
función que permita insertar elementos al final de una lista y en todos los casos es necesaria una
función que concatene dos listas.
Para implementar la solución a las tres recorridas se definen la funciones auxiliares Append, para concatenar dos listas, y Snoc, para insertar un elemento al final de una lista.
1
2
3
4
5
6
7
LNat Append ( LNat l , LNat p )
{
if ( Empty ( l ))
return p ;
else
return ( Cons ( Head ( l ) , Append ( Tail ( l ) , p )));
}
8
9
10
11
12
13
14
15
LNat Snoc ( int x , LNat l )
{
if ( Empty ( l ))
return ( Cons (x , NULL ));
else
return Cons ( Head ( l ) , Snoc (x , Tail ( l )));
};
Luego se utilizan éstas funciones auxiliares, y la función Cons para generar la solución.
1
2
3
4
5
6
7
LNat inOrder ( BinaryTree t )
{
if ( t != NULL )
return Append ( inOrder (t - > left ) , Cons (t - > elem , inOrder (t - > right )));
else
return NULL ;
};
8
9
10
11
12
13
14
15
16
LNat preOrder ( BinaryTree t )
{
if ( t != NULL )
return Append ( Cons (t - > elem , preOrder (t - > left )) , preOrder (t - > right ));
else
return NULL ;
};
17
18
19
20
21
22
23
24
LNat postOrder ( BinaryTree t )
{
if ( t != NULL )
return Append ( postOrder (t - > left ) , Snoc (t - > elem , postOrder (t - > right )));
else
return NULL ;
};
Instituto de Computación - Facultad de Ingeniería - UdelaR
Página 2 de 5
Ejercicio 5
Los Árboles Generales (también llamados Árboles Finitarios) son árboles con una cantidad finita de
subárboles, pero no necesariamente la misma para todos los nodos1 .Es posible representar un Árbol
General utilizando un Árbol Binario y para esto se suele utilizar la representación de primer hijo –
siguiente hermano. Como es necesario que algunas funciones reciban/devuelvan un conjunto de árboles,
esta representación requiere la implementación adicional de una Lista de Árboles Generales. Considere
las representaciones de la Figura 2, donde FTree es un tipo de datos que implementa árboles finitarios
de naturales como primer hijo – siguiente hermano y ListFTree es una lista de árboles finitarios de
naturales implementados como FTree.
1
2
3
4
5
struct FTreeNode {
int dato ;
FTreeNode * primerHijo , * sigHermano ;
};
typedef FTreeNode * FTree ;
6
7
8
9
10
11
struct NodoFTreeL ista {
FTree elem ;
Nodo FTreeL ista * sig ;
};
typedef No doFTre eLista * ListaFTree ;
Figura 2: Representación primer hijo - siguiente hermano para Árbol Finitario de Naturales y lista de Árboles
finitarios
(a) Utilice las representaciones de la Figura 2 para implementar las siguientes funciones constructoras:
i. nullFTree: que devuelve el árbol vacío.
ii. consFTree: que recibe un natural x y una lista de árboles finitarios l, y retorna un nuevo árbol
t, donde x es el elemento en la raiz de t y los árboles en l son los hijos de t.
iii. addOffspringFTree: que recibe dos árboles finitarios t y s, y agrega a s como hijo de t.
iv. deleteOffspringFTree: que recibe un árbol finitario t y un natural x, y elimina de t el único
subárbol de t que tiene a x como raíz.
Utilice las representaciones para implementar los siguientes predicados:
i. isEmptyFTree: que recibe un árbol finitario t y devuelve TRUE si y solo si t es vacío.
ii. isLeafFTree: que recibe un árbol finitario t y devuelve TRUE si y solo si t es una hoja.
iii. belongsFTree: que recibe un árbol finitario t y un natural x, y devuelve TRUE si y sólo si x
pertenece a t.
Implemente las siguientes funciones selectoras:
i. rootFTree: que recibe un árbol finitario no vacío t y devuelve el elemento en la raiz de t.
ii. offspringFTree: que recibe un árbol finitario no vacío t y devuelve una lista con los hijos de
t.
iii. siblingsFTree: devuelve la lista de hermanos de un árbol o subárbol t, no vacío
(b) ¿Qué criterio utilizó en la función AddOffspringFTree para agregar el nuevo hijo?
Análisis del problema
El principal objetivo de este ejercicio es familiarizarse con la representación de primer hijo – siguiente
hermano, la cual permite representar árboles finitarios mediante árboles binarios. En esta representación
todos los nodos del árbol poseen dos punteros: uno que apunta al siguiente hermano en cierto nivel del árbol
y otro que apunta al primer hijo del árbol. Es importante destacar que se asume que el nodo raíz del árbol
no tiene hermanos, por lo tanto el puntero al siguiente hermano de la raíz deberá referenciar a NULL.
1 Ver
Teórico 5 en la Sección teórico de la página web del curso
Instituto de Computación - Facultad de Ingeniería - UdelaR
Página 3 de 5
A modo de ejemplo, si consideramos el árbol finitario de la Figura 3a, la Figura 3b presenta su representación mediante un árbol binario usando primer hijo – siguiente hermano, asumiendo que para cada nodo el
puntero más a la izquierda corresponde al primer hijo y el más a la derecha al siguiente hermano. Se omite
que, para las hojas del árbol, estos dos punteros referencian a NULL.
10
10
12
15
12
3
2
4
1
9
21
11
NULL
20
17
24
13
3
18
15
(a) Árbol finitario
2
NULL
21
4
1
NULL
9
11
NULL
20
17
NULL
NULL
24
NULL
13
NULL
18
(b) Representación del árbol finitario como árbol binario
Figura 3: árbol finitario y su representación mediante un árbol binario usando primer hijo – siguiente
hermano
En algunas funciones es necesario considerar una colección de árboles. Por ejemplo en el caso de ConsFTree,
que recibe un elemento que se ubicará en la raíz del árbol finitario a retornar y una colección de árboles finitarios que deberán ser hijos directos el nodo recién creado. Para representar colecciones de árboles finitarios
se provee el tipo ListFTree. A primera vista este tipo parece ser innecesario, dado que los árboles podrían
engancharse usando al puntero al siguiente hermano, pero es importante tener en cuenta que cada uno de
los árboles finitarios contenidos en esta colección es un árbol finitario bien formado, por lo tanto la raíz
de cada uno de ellos no debe tener hermanos.
A continuación se presenta una implementación posible de las funciones ConsFTree y OffspringFTree,
donde se asumen las siguientes funciones auxiliares sobre listas de árboles finitarios:
bool IsEmptyLFT(ListaFTree l); /*Devuelve TRUE si la lista l es vacia, FALSE en otro caso */
FTree HeadLFT (ListaFTree l); /* Devuelve el árbol finitario que está en el primer elemento de la
lista l */
ListaFTree TailLFT (ListaFTree l); /* Devuelve la lista l sin su primer elemento */
Instituto de Computación - Facultad de Ingeniería - UdelaR
Página 4 de 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
FTree ConsFTree ( int x , ListaFTree l )
{
FTreeNode * tree , * iter ;
tree = new ( FTreeNode );
tree - > dato = x ;
tree - > sigHermano = NULL ;
if ( IsEmptyLFT ( l ))
tree - > primerHijo = NULL ;
else {
tree - > primerHijo = HeadLFT ( l );
l = TailLFT ( l );
iter = tree - > primerHijo ;
while (! IsEmptyLFT ( l )) {
iter - > sigHermano = HeadLFT ( l );
l = TailLFT ( l );
iter = iter - > sigHermano ;
};
};
return tree ;
};
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
ListaFTree O ffspri ngFTre e ( FTree t )
{
/* Precondicion : t no es vacio */
ListaFTree l ;
FTree aux ;
l = NullLFT ();
aux = t - > primerHijo ;
/* hacia el primer hijo ... */
while ( aux != NULL ) {
l = ConsLFT ( aux , l );
/* inserta un nodo de tipo FTree al comienzo de la lista */
aux = aux - > sigHermano ;
};
return l ;
};
Instituto de Computación - Facultad de Ingeniería - UdelaR
Página 5 de 5