Pascal/Turbo Pascal - Problema arboles binarios

 
Vista:

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:
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;
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:
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
Me gusta: Está pregunta es útil y esta claraNo me gusta: Está pregunta no esta clara o no es útil
0
Responder

Problema arboles binarios

Publicado por ramon (2158 intervenciones) el 06/05/2014 00:41:13
Pasa todo lo que tengas para poder revisarlo bien.
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Problema arboles binarios

Publicado por Ahmed (11 intervenciones) el 06/05/2014 00:45:12
Gracias por tu interes Ramon, pero ya conseguí solucionarlo por mí mismo, el problema estaba en los recorridos. Muchas gracias de todos modos.
Un saludo
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar

Problema arboles binarios

Publicado por ramon (2158 intervenciones) el 06/05/2014 01:21:02
me alegro que todo funcione suerte
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
0
Comentar
sin imagen de perfil

Problema arboles binarios

Publicado por federico (6 intervenciones) el 05/02/2015 20:53:53
hola tengo que entregar un problema mañana ( o recurso) que dice que dice espejar la imagen en forma simetrica horizontalmente y no entiendo a que se refiere es algo como este ejercicio?
Valora esta respuesta
Me gusta: Está respuesta es útil y esta claraNo me gusta: Está respuesta no esta clara o no es útil
-1
Comentar