Newsgroup: it.comp.lang.pascal
Titolo: procedura di Visita di un albero...,spiegazioni.

ciao a tutti,il mio albero adesso e' perfetto,mi resta qualcosa che
non riesco a spiegarmi,...la procedura qua sotto stampa gli elementi
di un albero in ordine binario simmetrico e prende in entrata il
puntatore al mio albero binario (root:tree).
adesso seguitemi in questi passi,
nella riga 3 faccio un confronto che risulta ovviamente vero se
l'albero non e' vuoto,quindi nella riga 4 e 5 procedo scorrendo i miei
figli di sinistra finche' non trovo un nodo senza figli....cioe'
arrivo ad un nodo senza nessun figlio ,root^.sx e' = nil 
quando vado e rieseguire la procedura, la riga 3 risulta FALSA perche'
root^.sx e' = nil !!!!!! vero???? ma a questo punto non dovrebbe
finire tutto??? cioe' se la riga 3 non e' mai vera come puo' la
procedura continuare????cioe' non potrei mai accedere al begin...end
che c'e' dentro l'if...then, eppure questo avviene.....come mai???
1 PROCEDURE VISITA(root:tree);{visita in oridne bin.simmetrico}
2 begin
3 if root<>nil then
4   begin
5   visita(root^.sx);
6   writeln(root^.chiave);
7   visita(root^.dx);
8   end;
9 end;
e poi ho notato con l'opzione TRACE del pascal che se la riga 3 e'
falsa la procedura salta alla riga 9 e poi prmendo ancora TRACE salta
alla 6!!!!! ed e' questo che non capisco.
ciao e grazie
[federico|end] 
ogal...@iol.it
 ,remove "ogalu." before reply
Key fingerprint = BB 82 C6 18 2B A2 77 44  48 E0 CC E5 BF EC 67 9E
"la Scienza e' un'equazione differenziale ; 
la Religione e' una condizione al contorno"
Alan M. Turing

ogal...@iol.it
 (end) wrote:






La visita inorder (o in ordine simmetrico) dell'albero che tu hai
usato e` ricorsiva e il suo comportamento e` molto diverso da quello
delle procedure non ricorsive.
Ogni qualvolta una procedura viene chiamata nello Stack vengono
salvate delle informazioni che permettono alla procedura chiamata di
gestire i parametri e di poter ritornare al programma chamante.
Ad esempio lo Stack per la seguente procedura potrebbe essere :
procedure Prova (i : integer;j : real);
begin
     ...
end;
begin
   Prova (10,20.54);
   readln;
end.
Lo Stack conterra` le seguenti informazioni :
    -------------------
    |      10        |
    --------------------
    |    20.54     |
    -------------------
    | Ret Addr.  |
    -------------------
 
dove Ret Addr. (Return Address)  e` l'indirizzo di ritorno, ovvero
quando viene letto il Ret Addr. viene eseguita l'istruzione sucessiva
alla chiamata alla procedura (nell'esempio readln).
Tale indirizzo di ritorno viene letto nel momento in cui si giunge
alla riga che contiene l'end nella procedura.
I due parametri sono i = 10 e j = 20.54 e sono salvati nello Stack.
Quando il programma ha letto il Ret Addr. lo Stack viene svotato.
Per una procedura ricorsiva le cose funzionano alla stessa maniera
solo che  sono un po` piu` complicate.
Per la procedura ricorsiva di vistita inorder di un albero avremo :
1a chiamata :	Visita(root) ;   effettuata dal programma principale.
		   --------------------
		   |   Root        |
		   --------------------
		   | Ret Addr. 1|
		   --------------------
2a chiamata :    Visita(root^.sx);  effettuata dalla procedura.
 
		Per questa nuova chiamata le precedenti informazioni 
		nello stack non vengono	cancellate perche` se questo
		avvenisse allora non saremo piu` in grado di ritornare al
		programma principale, in quanto verrebbe perso il Ret
		Addr. 1.
		   --------------------
		   |   Root        |
		   --------------------
		   | Ret Addr. 1|
		   --------------------
		   | Root^.sx    |
		   --------------------
		   | Ret Addr. 2|
		   --------------------
i-esima chiamata :  Visita (root^.sx);  effettuata dalla procedura.
		   --------------------
		   |   Root        |
		   --------------------
		   | Ret Addr. 1|
		   --------------------
		   | Root^.sx    |
		   --------------------
		   | Ret Addr. 2|
		   --------------------
		   | ................  |
		   --------------------		fig.  1
		   | Root^.sx    |
		   --------------------
		   | Ret Addr. i |
		   --------------------			
Quando abbiamo percorso tutti i figli  piu` a sinistra root^.sx sara`
NIL e quindi a questo punto effettueremo una chiamata in cui nello
Stack e` contenuto NIL e il Ret Addr. i+1.
La procedura a questo punto assegna a root il valore NIL e quando
viene eseguito l'if , che e` in questo caso falso, il programma salta
all'end e quindi viene letto il valore del Ret Addr. i+1 che si
riferisce all'istruzione che segue la chiamata alla procedura ovvero
al writeln (root^.chiave).
Avendo letto sia il parametro che Ret Addr. i+1 tali valori vengono
rimossi e lo Stack si presenta come in figura 1, dove root contiene il
valore root^.sx i-esimo.
Dopo aver eseguito il writeln, il programma esegue la chiamata
Visita(root^.dx).
Poiche` root contiene in tal caso il valore root^sx i-esimo,
effettuando la chiamata ci muoviamo al figlio destro del nodo i-esimo
appena considerato.
Es. :
Nell' esempio ti scrivo il nodo a cui punta root e l'istruzione che
verra` eseguita dopo aver letto il Ret Addr..
			 (1)
		            /      \
		          (2)       (3)
		         /  \       /
		       (4)  (6)  (5)
1a chiamata :    | (1) |  readln; |
2a chiamata :    | (2) | writeln(root^.chiave) | (1) | readln; |
3a chiamata :    | (4) | writeln(root^.chiave) | (2) | writeln ...
4a chiamata :    | Nil | writeln(root^.chiave) | (4) |
		 writeln(root^.chiave) | (2) | ...
L'if e` falso e quindi si ritorna all'istruzione writeln(root^.chiave)
e con root punta a (4).
Viene eseguito il writeln e si stampa (4).
Ora si esegue Visita(root^.dx) con root^.dx che vale NIL.
Quindi nello Stack avremo :
5a chiamata :  | Nil | end; | (4) | writeln(root^.chiave) | (2) | ...
L'if anche in questo caso risulta falso e si ritorna all'istruzione
end; con root che punta a (4).
Lo Stack e` :
 | (4) | writeln (root^.chiave) | (2) | writeln (root^.chiave) | (1) |
  readln; |
Quando viene eseguito l'end; dallo Stack viene prelevato il Ret Addr e
vengono eliminati i due valori correnti di root e Ret Addr..
L'esecuzione continua dal Ret Addr. appena prelevato.
Nel nostro caso avremo che lo Stack conterra` :
 | (2) | writeln (root^.chiave) | (1) | readln; |
e l'esecuzione procede con root che punta a (2) e dall'istruzione
writeln (root^.chiave).
Il programma quindi stampa (2) ed effettua la chiamata 
Visita (root^.dx) dove root^.dx punta a (6).
Lo Stack continene quindi :
 | (6) | end; | (2) | writeln(root^.chiave) | (1) | readln; |
Ora tutto procede in modo analogo a prima.
Quando avremo visitato il nodo (6) avremo la seguente situazione:
 | (1) | readln; | 
con root che punta ad (1) e il programma sara` fermo all'istruzione
writeln (root^.chiave).
Quindi viene stampato (1) e si effettua la chiamata Visita(root^.dx)
con root^.dx che vale (3).
Lo Stack conterra` :
 
 | (3) | end; | (1) | readln; |
Dopo la visita di (3) lo Stack conterra` :
 | (1) | readln; |
con root che punta a (1) e il programma sara` fermo all'istruzione
end;.
Dallo Stack viene prelevato il Ret Addr. che corrisponde al readln;
e viene svuotato.
Spero di esserti stato di aiuto. Per ogni eventuale dubbio scrivimi.
Ciao,
	Alberto Speranzon
         < 
albe...@intercity.it
 >
   ----------------------------------------------------------- - - - -
  |		       
  |  La vita e` un numero complesso,
  |  ha una parte reale ed una immaginaria.
  |	 	
  :  		   
 

[...cut...]
Se sai come funzionano le procedure ricorsive questo non dovrebbe sembrarti 
strano, visto che ti crea problemi invece usi delle cose che nemmeno sai come 
funzionano... male molto male, la ricorsione bisognerebbe saperla bene, visto 
che è uno strumento potentissimo, utilissimo ed allo stesso molto disastroso 
da usare quando si necessita di velocità. Passato questo:
Il TRACE funziona benissimo, perchè quando esegui una chiamata ricorsiva i 
parametri della chiamata si salvano sullo stack, quando la chiamata si 
esaurisce (la condizione è FALSE e quindi si esegue l'END finale) si esegue un 
pop degli ultimi dati dello stack (quindi dell'ultima chiamata) e si prosegue 
con quello che rimane sullo stack (le altre chiamate) che proseguono dove 
erano state interrotte, fino a quando non si esegue il pop della prima 
chiamata da te effettuata e quindi termina tutto il processo con il tuo albero 
stampato. Questo molto a grandi linee e spiegato tutt'altro che bene, leggiti 
un libro (il Wirth, se si scrive cosi) che è un classico. Però leggilo, non 
può farti che bene, se ti interessi di programmazione certe cose BISOGNA 
saperle.
                                                        Luca.