Newsgroup: it.comp.lang.pascal
Titolo: Visitare un albero

Come posso fare una procedura di visita ad un albero binario senza
utilizzare la ricorsione??
grazie.
______________________________
e-mail:  
Aur...@hotmail.com
 
tol...@reteitalia.net
ICQ:     16005054

...



______________________________
e-mail:  
Aur...@hotmail.com
ICQ:     16005054

Non e' tanto ovvio se pensi che i puntatori siano uno strumento ricorsivo!
 ... cmq per farla breve .. se ti interessano me li chiedi per email e ti
mando dei programmi che
 ho fatto in C che puoi convertirti in due secondi che ti risolvono il
problema.


Se la ricorsione non la puoi usare la devi quanto meno simulare. Non
mi sembra che ci sia via d'uscita.
Ciao,   Fabio.
fabi...@rocketmail.com

Ma per piacere.. non diciamo bischerate.

....e che sarebbero i flags??
Usi dei bit (in pascal dei byte...:) ) per capire se hai già "visitato" quel
nodo :-)
Ciao
Emanuele Cesena
d.a.m...@iol.it
           Attenti all'antispam NOSPAM
http://www.geocities.com/SiliconValley/Grid/8879
trovate ora l'editor per i livelli di Bubble2000!! :-))
ICQ n° #10570672


Purtroppo di C non conosco niente.Lo studiero' l'anno prossimo a
Laboratorio II.
Cmq. grazie


Ma per piacere.. non diciamo bischerate.
Un albero binario e' una struttura ricorsiva.
Infatti un sottoalbero di un albero binario e', a sua volta, un albero
binario (foglie comprese).
Da questa considerazione, risulta evidente che la scelta piu' corretta
per visitare un albero sia la ricorsione.
Le altre soluzioni sono un ripiego, generalmente adottato da chi ha
poca confidenza con la ricorsione. Le procedure infatti risultano piu'
lunghe, meno leggibili ed hanno bisogno di alcuni "sotterfugi" come,
appunto marche, flags ecc. per marcare i nodi gia' visitati.
Ancora una considerazione.
Vi e' in effetti uno stretto rapporto fra una procedura ricorsiva e la
sua versione iterativa (cioe' quella non ricorsiva realizzata ad
esempio con un while).
Quindi se qualcuno dice che con una procedura iterativa simula una
procedura ricorsiva, io userei un po' di cautela nel rispondergli,
evitando frasi come "Ma per piacere.. non diciamo bischerate."
Frase che, se vogliamo, e' anche un po' offensiva.
Credo che sarebbe meglio approfondire il significato della frase
"simulare una procedura ricorsiva" e poi la risposta potrebbe anche
essere piu' esplicativa.
In ogni caso, dire "Ma per piacere.. non diciamo bischerate." e'
senz'altro presuntuosa ed altrettanto sicuramente poco costruttivo.
Non sarebbe stato forse meglio spiegare dove sta la bischerata,
piuttosto che lasciar cadere la frase dall'alto, come suggerita da una
divina entita'?
Alessandro C.

Guarda un  po' questa:
type	ptr=^nodo;
	nodo=record
		info:string;
		sx,dx:ptr
	end;
pocedura  preordine(root:ptr);
var	a:array[1..100] of ptr;
	p:ptr;
	i:integer;
	fine:boolean;
begin
if root<>nil then begin
       fine:=false;
       p:=root;
       i:=0;
       repeat
                while p<>nil do begin
                           write(p^.info);
                           inc(i);
                           a[i]:=p;
                           p:=p^.sx
                end;
                p:=a[i];
                while ((p^.dx=nil) or (p^.dx=a[i+1])
                and (not fine) do begin
                          dec(i);
                           if i=0 then
                                 fine:=true
                           else
                                 p:=a[i]
                end
                if (not fine) then
                       if p^.dx<>nil then
                               p:=p^.dx
       until fine
end
end;
A me sembra funzionare ma non ci giurerei.
Ciao,   Fabio
fabi...@rocketmail.com

Alessandro C.
Grazie per l'appoggio.
Visto che lui non spiega spiego io.
Se io devo visitare un albero senza usare la ricorsione (un libricino
che sono andato a riguardare la chiama ricursione) devo mano mano che
lo visito quanto meno memorizzare da qualche parte il percorso fatto
fino al punto in cui mi trovo (almeno quello diretto). Di qui non si
scappa altrimenti in dietro non ci torno. Un'altra cosa da cui non si
scappa e' che la struttura utilizzata per memorizzare il percorso io
la posso implementare come voglio ma alla fine e' una pila (=stack).
Quindi: un ciclo almeno ci vuole, uno stack lo devo utilizzare, dopo
aver visitato il nodo per tornare indietro devo prelevare la posizione
del nodo dallo stack. In pratica mi sto impiccando per imitare quello
che fa la versione ricorsiva.
Ora dimmi grande Master se cosi’ NON LA STO SIMULANDO.
Saluti,  Fabio
fabi...@rocketmail.com

 La ricorsione e' la capacita' che ha un linguaggio di programmazione (ma
non solo) di poter richiamare all'interno di funzioni non ancora
completamente definite la funzioni stesse.
  La cosa nasce col lisp .. che ai primordi usava solo la ricorsione come
forma di ciclo.
  Un puntatore e uno strumento che ti mette in di gestire le variabili in
maniera indipendente dal loro contenuto .. sapendo la loro locazione vera
nella table name .. o in memoria come preferisci.
  Se si va per approssimazione allora si potrebbe dire anche che l'unica
istruzione di programma e' IF
 (come in effetti e'! .. sebbene non sia cosi'.) ... e c'e' pure un
linguaggio di programmazione che usa solo quella di istruzione per elaborare
lo scheletro del programma e i prototipi delle procedure.. il PROLOG.

 Te lo spiego anch'io .. non ci sono problemi!
   Un albero binario NON e' una struttura ricorsiva.. mi sa che hai le idee
un po confuse.
  Un albero binario e' solamente una struttura che puoi percorre tramite una
semplice funzione ricorsiva.
  Ma il fatto che applichi una funzione con delle specifiche particolari ad
un elemento non significa che l'elemento stesso ne acquisisca le specifiche
in oggetto.
 Neanche nel caso in cui la funzione che applichi sia l'UNICA applicabile..
e non e' questo il caso.
    Il fatto che  f(a)=Sin(a+0*i)  con a= k*Pi e k intero.. mi dia come
risultato (SEMPRE) 0 .. ovvero un numero intero .. sarebbe a te bastante per
dire che f(a) e' una funzione agli interi?
    ... ???

Ragazzi .. le parole sono importanti!.
 Tu hai sicuramente simulato uno degli aspetti della ricorsione., come anche
hai simulato una nota procedura di ricerca operativa, come anche ai simulato
l'algoritmo pivot del retto per il minimo cammino,
  ma ovviamente NON hai simulato la ricorsione, come NON hai simulato la
ricerca operativa in pianta stabile, come non hai simulato il retto per il
minimo cammino.
 Se poi vuoi aver simulato la ricorsione ..   va be' ..contento tu.  ;-)

Poi per evitare che mi sentiate dire solo 'parole' vi aggiungo alla presente
un programmino in c
(Lo convertire in pascal ma sinceramente non mi fa volgia! .. ci vuole poco
cmq.)
 E' un topo digitale che trova da solo la strada per uscire da un labirinto.
  Scansiona un albero binario (tutto) piu' volte eliminando percorsi chiusi,
gia' fatti, ecc...
  Puntatori = NESSUNO
  Ricorsione = NEANCHE L'OMBRA!
 -------- Il programma e' questo.   Turbo C 3 della borland. (l'equivalente
in versione al TP7)
#include <stdio.h>
#include <graphics.h>
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <dos.h>
void main()
{
/*   carica il labirinto   */
int p[20][20]=
{
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,
0,0,1,0,0,0,0,1,0,0,1,0,1,1,1,1,1,1,0,0,
0,0,1,0,0,0,0,1,0,0,1,0,1,0,0,0,0,1,0,0,
0,0,1,0,0,0,1,1,1,1,1,1,1,0,0,0,0,1,0,0,
0,0,1,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,0,0,
0,0,1,1,1,1,1,0,0,0,0,0,1,1,1,1,0,1,0,0,
0,0,0,1,0,0,1,0,1,0,0,0,1,0,0,1,0,1,0,0,
0,0,0,1,0,0,1,0,1,0,0,0,1,0,0,1,0,1,0,0,
0,0,0,1,1,0,1,0,1,0,0,0,1,0,0,1,0,1,0,0,
0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,0,0,1,0,0,
0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,1,0,0,
0,0,1,1,1,1,1,1,1,0,0,0,1,0,1,0,0,1,0,0,
0,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,0,1,0,0,
0,0,1,0,1,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,
0,0,1,0,1,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,
0,0,0,0,1,1,1,1,0,0,1,0,1,1,1,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,1,0,0,
0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
};
int c1,c2,c3,c4;
int n,k,x=1,y=1;
char a,buf[30];
int screen=0,modo,error;
int u,d,r,l;
initgraph(&screen,&modo,"");
cleardevice();
abbellimenti();
/* inizializza il labirinto con 256=muro al posto di 0 */
for(y=0;y<=19;y++)
 {
  for(x=0;x<=19;x++)
   {
    if(p[x][y]==0)p[x][y]=256;
   }
 }
vedi(&p);
ferormoni();
getch();
/*   trova l'inizio   */
x=1;
for(k=0;k<=19;k++) if(p[x][k]!=256)y=k;
setcolor(GREEN);
settextstyle(0,0,0);
p[x][y]=p[x][y]+1;
procvedi(&p,&x,&y);
for(k=1;k<=1E8;k++)
  {
   setcolor(1);
   setfillstyle(1,1);
   fillellipse(185,65,50,16);
   settextstyle(3,0,4);
   setcolor(WHITE);
   sprintf(buf,"Mossa n.%d",k);
   outtextxy(30,40,buf);
   settextstyle(0,0,0);
Ragiona_e_vai(&p,&x,&y);
n=procvedi(&p,&x,&y);
if(n==1){
  settextstyle(3,0,4);
  setcolor(WHITE);
  sprintf(buf,"Uscita trovata in %d mosse.",k);
  outtextxy(30,300,buf);
  a=getch();
  exit(0);
 }
  a=getch();
  if(a=='q')exit(0);
 }
}
Ragiona_e_vai(area,x,y)
int area[20][20];
int *x,*y;
{
int U,D,R,L;
/* LEGGE I PERCORSI CHE STANNO INTORNO AL TOPO */
U   = area[(*x)]  [(*y)+1];
D   = area[(*x)]  [(*y)-1];
R   = area[(*x)+1][(*y)]  ;
L   = area[(*x)-1][(*y)]  ;
/* ELIMINATORE DI PERCORSI CHIUSI */
if(*x>1)
  {
   if(U==256 && R==256 && L==256)
      {area[*x][*y]=256;procvedi2(area,x,y);};
   if(D==256 && R==256 && L==256)
      {area[*x][*y]=256;procvedi2(area,x,y);};
   if(U==256 && D==256 && R==256)
      {area[*x][*y]=256;procvedi2(area,x,y);};
   if(U==256 && D==256 && L==256)
      {area[*x][*y]=256;procvedi2(area,x,y);};
  }
/* MUOVE IL TOPO DOVE POSSIBILE E DOVE SI E' MENO NAVIGATO */
/*                                                       Preferenze:     */
if((U<=R) && (U<=L) && (U<=D)){*y=*y+1;goto giu;} /*   1   sopra         */
if((R<=U) && (R<=D) && (R<=L)){*x=*x+1;goto giu;} /*   2   destra        */
if((D<=R) && (D<=L) && (D<=U)){*y=*y-1;goto giu;} /*   3   sotto         */
if((L<=R) && (L<=D) && (L<=U)){*x=*x-1;goto giu;} /*   4   sinistra      */
giu:
area[*x][*y]=area[*x][*y]+1;
}
vedi(area)
int area[20][20];
{
int y,x;
char buf[3];
for(y=0;y<=19;y++)
{
 for(x=0;x<=19;x++)
 {
  if(area[x][y]==256)setcolor(DARKGRAY);
  else setcolor(BLUE);
  outtextxy(100+x*10,100+y*10,"_");
 }
}
settextstyle(2,0,2);
setcolor(YELLOW);
for(y=0;y<=19;y++)
 {
 sprintf(buf,"%d",y);
 outtextxy(90,100+y*10,buf);
 }
for(x=0;x<=19;x++)
 {
 sprintf(buf,"%d",x);
 outtextxy(100+x*10,90,buf);
 }
}
procvedi(area,x,y)
int area[20][20];
int *x,*y;
{
 char buf[10];
 settextstyle(0,0,0);
 setcolor(3+area[*x][*y]*3);
 outtextxy(100+10*(*x),100+10*(*y),"_");
 settextstyle(2,0,3);
 sprintf(buf,"%d",area[*x][*y]-1);
 setcolor(BLACK);
 outtextxy(101+10*(*x),99+10*(*y),buf);
 if(*x==18)return(1);
 else return(0);
}
procvedi2(area,x,y)
int area[20][20];
int *x,*y;
{
 setcolor(WHITE);
 setfillstyle(1,1);
 outtextxy(100+10*(*x),100+10*(*y),"_");
 setcolor(BLACK);
 outtextxy(101+10*(*x),101+10*(*y),"+");
}
ferormoni()
{
int k;
char buf[10];
settextstyle(2,0,6);
for(k=2;k<=16;k++)
  {
   setcolor(1);
   setfillstyle(1,3+k*3);
   fillellipse(8+k*30,460,10,10);
   setcolor(YELLOW);
   sprintf(buf,"%d",(k-1));
   outtextxy(3+k*30,430,buf);
  }
  setfillstyle(1,WHITE);
  fillellipse(10+18*30,460,10,10);
  setcolor(BLACK);
  line(10+18*30,455,10+18*30,465);
  line(5+18*30,460,15+18*30,460);
  setcolor(YELLOW);
  settextstyle(2,0,4);
  outtextxy(3+17*30,435,"Percorsi chiusi");
}
abbellimenti()
{
 int n,x,y;
 setcolor(BLUE);
 for(n=-600;n<=1000;n=n+5)
  {
  line(n,80,n+600,700);
  line(n,80,n-600,700);
  }
 setcolor(BLACK);
 for(y=0;y<=19;y++)
 {
  for(x=0;x<=19;x++)
  {
  outtextxy(102+x*10,102+y*10,"_");
  }
}
setfillstyle(1,1);
bar(0,0,680,80);
settextstyle(5,0,4);
setcolor(WHITE);
outtextxy(10,-10,"topo cibernetico.");
settextstyle(0,0,0);
}


Non e' cosi'.
Un albero binario e' una struttura dati che è naturalmente definita
ricorsivamente. E' costituito da un insieme finito di nodi ed e' vuoto
o costituito da un nodo (radice) con due alberi binari disgiunti,
chiamati sottoalbero sinistro e desto.
Dimmi tu come definisci un albero.
Fabio.
fabi...@rocketmail.com

 ...
Inoltre il fatto che sia una definizione ricorsiva lo rende piu'
facilmente e naturalmente percorribile con una funzione ricorsiva che
non con una iterativa. Infatti credo che tu non abbia bisogno di
manipolare byte, flags ecc (che oltretutto ti "sporcano"  la struttura
dati inserendovi campi che servono solo al calcolo).
Visto che da qualche parte hai citato Ricerca Operativa (esame che ho
fatto anche io) direi che danno talmente per scontato che l'albero
binario sia una definizione ricorsiva che non ci tornano nemmeno sopra
(= non si passa se l'esame di ricerca operativa se non si sa che
l'albero binario e' una struttura dati ricorsiva).
Ma ci sono anche altri esami come ad es. da noi era Sistemi Operativi
I che affrontano le strutture dati e le funzioni migliori per
utilizzerle in cui a proposito degli alberi (di cui i binari sono un
caso particolare) viene mostrata la differenza fra funzioni ricorsive
ed iterative proprio al fine di sconsigliare l'uso di queste ultime.
Forse questa discussione sta diventando un po' ot
Alessandro C.

 ot1+ot2+ot3. +.. + otk
1. Non esiste una definizione mia o tua di albero!
Leggersi Chomsky avanzatempo per la giusta definizione, e unica almeno in
termini matematici.
Se il suddetto risulta palloso, anche i fondamenti della logica formale ne
danno ampia descrizione.
 2. un albero non e' solo binario!  .. il fatto di essere binario e' anche
questa una mera caratteristica.
hai presente un labirinto? beh pure quello e' un albero. Anche un pero e' un
albero.. anche in termini matematici .. solo non binario.
Un cavolfiore, e il tessuto di un polmone, la curva di Peano alla ennesima
generazione sono alberi RICORSIVI invece.. non nel senso della ricorsione
classica da programmazione ma in quello della ripetitivita' degli elementi
basilari.
  Da questo punto vista anche un albero BINARIO completo E' una
struttura -ricorsiva- .. la' dove -ricorsivo- non vuol dire assolutamente
nulla di 'impilabile' o 'restituibile' o 'deducibile' o 'richiamabile'  ma
solo relativo alla geometria delle funzioni differenziali caotiche. (I
frattali, per parlare piu' semplicemente, ne sono un esempio banale.)
   Ricorsivo purtroppo e' un termine che l'informatica ha preso a prestito
dalla matematica per spiegare un fenomeno tecnicamente diverso o almeno
dissimile nella struttura portante.
   La funzione richiama se stessa == L'elemento si riproduce in forma
analoga
cio' NON E' VERO .. solo la mancanza di conoscenza in una delle due
cosapevolezze necessarie per capirlo (informatica   *   logica-matematica)
permette la visione di una ambiguità a questo riguardo.
Ambiguità che ovviamente non c'e'.
  .. non do' qui la spiegazione perche' non ce n'e' motivo .. ripeto il
punto 1  per approfondimenti.