Problema arboles binarios
Publicado por Ahmed (11 intervenciones) el 02/05/2014 22:43:32
Buenas tardes,
escribo porque estoy teniendo un problema a la hora de implementar una operación en un árbol binario. La cuestión es la que sigue:
Debo realizar un procedimiento que devuelva el espejo (o la imagen especular) de un árbol recibido. He realizado la siguiente implementación, es lo primero que no sé si está bien:
La operación raíz recibe un árbol a y devuelve su raíz r.
HijoIzq e HijoDer devuelven respectivamente el hijo izquierdo (izq) y el hijo derecho (der) del árbol a
La cabecera de la operación construir es PROCEDURE Construir (VAR a2:TArbolBin, i,d:TArbolBin,r:TElemento);
El programa de prueba que evalúa la operación espejo es el que sigue:
Como pueden ver, utiliza los recorridos del árbol, los cuales tengo implementados como sigue:
PROCEDURE InOrden(a: TArbolBin; VAR l: TLista);
{Pre = recibe un árbol binario}
{Post = devuelve una lista con los elementos del árbol recorrido en orden}
PROCEDURE PreOrden(a: TArbolBin; VAR l: TLista);
{Pre = recibe un árbol binario}
{Post = devuelve una lista con los elementos del árbol recorrido en preorden}
PROCEDURE PostOrden(a: TArbolBin; VAR l: TLista);
{Pre = recibe un árbol binario}
{Post = devuelve una lista con los elementos del árbol recorrido en postorden}
Se que alguna de las dos cosas (espejo o algún recorrido) está mal programada, pero no doy con ello... Espero que ustedes puedan solucionarme algo.
Gracias de antemano. Un saludo.
PD: El TAD Lista lo tengo implementado correctamente, está comprobado, al igual que el TAD ArbolBin
escribo porque estoy teniendo un problema a la hora de implementar una operación en un árbol binario. La cuestión es la que sigue:
Debo realizar un procedimiento que devuelva el espejo (o la imagen especular) de un árbol recibido. He realizado la siguiente implementación, es lo primero que no sé si está bien:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
PROCEDURE Espejo(a: TArbolBin; VAR a2: TArbolBin);
VAR
izq,der,izq2,der2:TArbolBin;
r:TElem;BEGIN
IF EsArbolBinVacio(a) THEN
CrearArbolBinVacio(a2)
ELSE
BEGIN
Raiz(a,r);
HijoIzq(a,izq);
HijoDer(a,der);
Espejo(izq,izq2);
Espejo(der,der2);
Construir(a2,der2,izq2,r);
END;
END;
HijoIzq e HijoDer devuelven respectivamente el hijo izquierdo (izq) y el hijo derecho (der) del árbol a
La cabecera de la operación construir es PROCEDURE Construir (VAR a2:TArbolBin, i,d:TArbolBin,r:TElemento);
El programa de prueba que evalúa la operación espejo es el que sigue:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
PROCEDURE Probar_Espejo(VAR entrada, salida: Text);
VAR
a1,a2: TArbolBin;
lpre, lin, lpost: TLista;
BEGIN
LeerArbolEntrada(entrada,a1);
Operaciones.Espejo(a1,a2);
Recorridos.PreOrden(a2, lpre);
Recorridos.InOrden(a2, lin);
Recorridos.PostOrden(a2, lpost);
EscribirLista(salida, lpre);
write(salida,' ');
EscribirLista(salida, lin);
write(salida,' ');
EscribirLista(salida, lpost);
ArbolBin.DestruirArbol(a1);
ArbolBin.DestruirArbol(a2);
Lista.Destruir(lpre);
END;
Como pueden ver, utiliza los recorridos del árbol, los cuales tengo implementados como sigue:
PROCEDURE InOrden(a: TArbolBin; VAR l: TLista);
{Pre = recibe un árbol binario}
{Post = devuelve una lista con los elementos del árbol recorrido en orden}
PROCEDURE PreOrden(a: TArbolBin; VAR l: TLista);
{Pre = recibe un árbol binario}
{Post = devuelve una lista con los elementos del árbol recorrido en preorden}
PROCEDURE PostOrden(a: TArbolBin; VAR l: TLista);
{Pre = recibe un árbol binario}
{Post = devuelve una lista con los elementos del árbol recorrido en postorden}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
PROCEDURE InOrden(a: TArbolBin; VAR l: TLista);
VAR
r:TInfo;izq,der:TArbolBin;
BEGIN
CrearListaVacia(l);
IF NOT EsArbolBinVacio(a) THEN
BEGIN
Raiz(a,r);
HijoIzq(a,izq);
HijoDer(a,der);
InOrden(izq,l);
InsertarFinal(l,r);
InOrden(der,l);
END;
END;
PROCEDURE PreOrden(a: TArbolBin; VAR l: TLista);
VAR
r:TInfo;izq,der:TArbolBin;
BEGIN
CrearListaVacia(l);
IF NOT EsArbolBinVacio(a) THEN
BEGIN
Raiz(a,r);
HijoIzq(a,izq);
HijoDer(a,der);
InsertarFinal(l,r);
PreOrden(izq,l);
PreOrden(der,l);
END;
END;
PROCEDURE PostOrden(a: TArbolBin; VAR l: TLista);
VAR
r:TInfo;izq,der:TArbolBin;
BEGIN
CrearListaVacia(l);
IF NOT EsArbolBinVacio(a) THEN
BEGIN
Raiz(a,r);
HijoIzq(a,izq);
HijoDer(a,der);
PostOrden(izq,l);
PostOrden(der,l);
InsertarFinal(l,r);
END;
END;
Se que alguna de las dos cosas (espejo o algún recorrido) está mal programada, pero no doy con ello... Espero que ustedes puedan solucionarme algo.
Gracias de antemano. Un saludo.
PD: El TAD Lista lo tengo implementado correctamente, está comprobado, al igual que el TAD ArbolBin
Valora esta pregunta
0
