Pascal: Alberi

[gokan]

:sofico:

Sono alle prese con gli alberi.Non ho avuto grosse difficoltà ad implementare una procedura che mi consenta di calcolare la profondità di un nodo (il nodo lo devo scegliere io).

(P.S:La profondità(o livello) di un nodo n è la lunghezza del cammino che va dalla radice ad n . Segue che la profondità di un albero è la massima profondità dei suoi nodi.
)

Procedure profondita(p:pAlbero; valore,prof_nodo:integer);
begin
if p<>NIL then
  begin
  if valore=p^.info then writeln('nodo: ',valore,' di profondita: ', prof_nodo);
    profondita(p^.AlbSin,valore, prof_nodo+1);
    profondita(p^.AlbDes,valore,prof_nodo+1);
  end;
end;

Dall'immagine deduciamo questo:
ProfonditàNodo(6)=0
ProfonditàNodo(5,7)=1
ProfonditàNodo(3)=2
ProfonditàNodo(2,4)=ProfonditàAlbero=3

Come si vede dalla procedura la profondità non è altro che il numero di livelli che dobbiamo scendere prima di arrivare al nodo cercato, significa che inizializzando (fuori) prof_nodo:=0 ad ogni chiamata ricorsiva al nodo figlio (Sinistro o Destro) aumenta di uno la profondità.
Perchè sto spiegando tutto questo?
Adesso dovrei costruire una procedura che mi calcoli l'altezza di un nodo(sempre scelto da me).
(P.S:L'altezza di un nodo n è la lunghezza del cammino più lungo che va da n ad una foglia. Segue che l'altezza di un albero è l'altezza della sua radice.
)
Segue:
AltezzaNodo(6)=AltezzaAlbero=3
AltezzaNodo(5)=2
AltezzaNodo(3)=1
AltezzaNodo(2,4,7)=0

Che algoritmo dovrei seguire per calcolare l'altezza? Io pensavo che avendo (ad esempio) a disposizione la profondità dell'albero basterebbe fare una procedura simile a quella precedente con l'unica variante che ogni volta avviene un decremento.Questa idea funziona(dovrei però calcolarmi la profondità con un'altra funzione), ma volevo fare qualcosa di meno dispendioso.Consigliatemi.
Grazie

[monkey72]

Originariamente inviato da gokan
...Dall'immagine deduciamo questo:
ProfonditàNodo(6)=0
ProfonditàNodo(5,7)=1
ProfonditàNodo(3)=2
ProfonditàNodo(2,4)=ProfonditàAlbero=3
...

da quale immagine

p.s. stai parlando di alberi binari?

[monkey72]

p'.s'. imho l'altezza di un albero coincide con la profondità del nodo con max profondità...

[gokan]

Ho dimenticato di inserire l'immagine
Lo so che l'altezza di un albero coincide con la profondità di un albero.
Io devo costruire una procedura che esamini un determinato nodo scelto dall'utente e calcoli l'altezza di quel nodo.

[monkey72]

se albero = NIL altezza = 0
altrimenti altezza = 1 + max (altezza(sottoalberosx), altezza(sottoalberodx))

dove il nodo n di cui vuoi calcolare l'altezza è la radice di albero

[gokan]

Originariamente inviato da monkey72
se albero = NIL altezza = 0
altrimenti altezza = 1 + max (altezza(sottoalberosx), altezza(sottoalberodx))

dove il nodo n di cui vuoi calcolare l'altezza è la radice di albero

Function Calcola_Altezza(p:pAlbero):integer;
var
  AltezzaDestra: integer;
begin
if p= NIL then Calcola_altezza:=-1
else
  begin
  AltezzaDestra:= 1 + Calcola_altezza(p^.AlbDes);
  if (AltezzaDestra > Calcola_Altezza(p^.AlbSin)+1) then  Calcola_Altezza:= AltezzaDestra;
     end;
end;

Ho capito come si trova l'altezza dell'albero, il problema è trovare l'altezza di un nodo(diverso dalla radice) scelto dall'utente

Ciao

[bsummer]

Se l'albero è del tipo rappresentato in figura allora è molto semplice.

Dato il valore ricercato, devi scendere nel ramo di destra se il nodo corrente ha un valore minore o a sinistra se maggiore: se non è nè minore nè maggiore allora l'hai trovato .
Il nodo radice ha profodnità 0 ed ogni volta che scendi incrementi tale valore di 1.

Per un albero generico invece puoi lavorare su puntatori.
Sia P il valore del puntatore del nodo cercato.

Puoi crearti una funzione ricorsiva che confronta il puntatore del nodo corrente con quello del nodo cercato...se i due puntatori non puntano alla stessa locazione allora richiami la funzione ricorsivamente passando come nodo radice quello del sotto albero sinistro (se esiste) o destro (se esiste). Nel caso non vi siano sottoalberi nel nodo corrente e questo non sia il nodo cercato la funzione restituisce un valore negativo (ad esempio -1) e si ritorna su di un nodo. Per come è costruita la funzione ricercherà il nodo su tutta la struttura dell'albero fino a trovarlo. Quando l'avrà trovato restituirà la profondità.

E' più semplice a farla che a spiegarla (te la scrivo in pseudo codice perchè il pascal non le ricordo +)

funzione ricerca(albero, nodo, prof) :integer

var r :integer

begin

se albero ==nil then restituisci -1
altriementi
begin
se albero == nodo then restituisci prof
altrimenti
begin
r=ricerca(albero.sinistro,nodo, prof+1)
se r=-1 then r=ricerca(albero.destro,nodo,prof+1)
restituisci r
end
end
end

Dovrebbe essere così...

Aloha

[bsummer]

dannazione...non imparerò mai a formattare il testo

[monkey72]

Originariamente inviato da gokan
(P.S:L'altezza di un nodo n è la lunghezza del cammino più lungo che va da n ad una foglia. Segue che l'altezza di un albero è l'altezza della sua radice.
)

L’altezza di un albero binario è la lunghezza del più
lungo cammino della radice ad una foglia + 1
verifica bene la definizione di altezza... ci sono in giro definizioni diverse, cmq cambia poco...

Originariamente inviato da gokan
Ho capito come si trova l'altezza dell'albero, il problema è trovare l'altezza di un nodo(diverso dalla radice) scelto dall'utente

infatti... applicando la funzione che ti ho suggerito...
i nodi 2 e 4 hanno altezza 1
il nodo 3 ha altezza 2
il nodo 5 ha altezza 3
il nodo 7 ha altezza 1
la radice ha altezza 4
se poi vuoi applicare la tua definizione parti con altezza della foglia = -1.
Se il tuo codice funziona per l'intero albero funzionerà anche per l'albero che ha radice il nodo di cui vuoi calcolare l'altezza... no?

[cisc]

penso che gokan (correggimi se sbaglio) abbia problemi nel trovare il nodo scelto dall'utente, e non nel calcolarne l'altezza.

se è così, il problema deve essere risolto conoscendo l'interfaccia del programma e quindi conoscendo come l'utente può scegliere un nodo....

[gokan]

Originariamente inviato da cisc
penso che gokan (correggimi se sbaglio) abbia problemi nel trovare il nodo scelto dall'utente, e non nel calcolarne l'altezza.

se è così, il problema deve essere risolto conoscendo l'interfaccia del programma e quindi conoscendo come l'utente può scegliere un nodo....

Finalmente uno che mi capisce
Il problema è proprio questo!!
Avevo pensato a qualcosa di simile:

Function Calcola_Altezza(p:pAlbero; valore:integer):integer;
 var
   AltezzaDestra,AltezzaSinistra: integer;
begin
 if p=NIL then Calcola_Altezza:=-1
 else
   begin
   if valore=p^.info then
     begin
     AltezzaDestra:=Calcola_Altezza(p^.AlbDes,valore)+1;
     AltezzaSinistra:=Calcola_Altezza(p^.AlbSin,valore)+1;
     if AltezzaDestra>=AltezzaSinistra then Calcola_Altezza:=AltezzaDestra
     else Calcola_Altezza:=AltezzaSinistra;
     end
   else if valore<p^.info then Calcola_Altezza:=Calcola_Altezza(p^.AlbSin,valore)
   else if valore>p^.info then Calcola_Altezza:=Calcola_Altezza(p^.AlbDes,valore);
  end;
end;

volevo sfruttare il caso base (in cui il nodo scelto dall'utente sia giusto giusto la radice) e poi estenderlo al sotto albero sin e des. Purtroppo non funziona. Con il calcolo della profondità è stato più facile perchè man mano che scendevamo di livello bastava incrementare un parametro profondità, nel caso dell'altezza è come se dovessimo partire dal basso, cioè, se guardiamo la figura i nodi(foglie) 2 e 4 hanno altezza 0, il nodo 3 altezza 1...
Il prob è partire dal nodo scelto è poi scendere giù, non scendere giù fino a quando trovavamo il nodo scelto come per la profondità..

Nel Main del programma, prima di chiamare la procedura faccio un semplice :
write('Inserisci il nodo di cui vuoi conoscere l''altezza: ');
read(valore);
Basta così

[bsummer]

Vediamo se stavolta ho capito...

- l'utente inserisce un valore che rappresenta il valore contenuto in un nodo dell'albero.

- a questo punto tu devi cercare tale nodo

-una volta trovato tale nodo devi calcolare l'altezza dell'albero che si sviluppa da quel nodo fino alla sua foglia più bassa?

[monkey72]

Originariamente inviato da gokan
Finalmente uno che mi capisce
Il problema è proprio questo!!

cioè conoscere il nodo scelto dall'utente?????????
ma non è quello che tu chiami valore nel codice postato quì sotto!

Originariamente inviato da gokan
Avevo pensato a qualcosa di simile:

Function Calcola_Altezza(p:pAlbero; valore:integer):integer;
 var
   AltezzaDestra,AltezzaSinistra: integer;
begin
 if p=NIL then Calcola_Altezza:=-1
 else
   begin
   if valore=p^.info then
     begin
     AltezzaDestra:=Calcola_Altezza(p^.AlbDes,valore)+1;
     AltezzaSinistra:=Calcola_Altezza(p^.AlbSin,valore)+1;
     if AltezzaDestra>=AltezzaSinistra then Calcola_Altezza:=AltezzaDestra
     else Calcola_Altezza:=AltezzaSinistra;
     end
   else if valore<p^.info then Calcola_Altezza:=Calcola_Altezza(p^.AlbSin,valore)
   else if valore>p^.info then Calcola_Altezza:=Calcola_Altezza(p^.AlbDes,valore);
  end;
end;

se non erro il tuo ragionamento vuole essere questo: parti dalla radice e ogni nodo che incontri controlli che sia quello scelto dall'utente (verificando che p^.info=valore), nel qual caso ne calcoli l'altezza incrementando di 1 l'altezza max dei sottoalberi.

Originariamente inviato da gokan
volevo sfruttare il caso base (in cui il nodo scelto dall'utente sia giusto giusto la radice) e poi estenderlo al sotto albero sin e des. Purtroppo non funziona. Con il calcolo della profondità è stato più facile perchè man mano che scendevamo di livello bastava incrementare un parametro profondità, nel caso dell'altezza è come se dovessimo partire dal basso, cioè, se guardiamo la figura i nodi(foglie) 2 e 4 hanno altezza 0, il nodo 3 altezza 1...
Il prob è partire dal nodo scelto è poi scendere giù, non scendere giù fino a quando trovavamo il nodo scelto come per la profondità..

Nel Main del programma, prima di chiamare la procedura faccio un semplice :
write('Inserisci il nodo di cui vuoi conoscere l''altezza: ');
read(valore);
Basta così

allora di che interfaccia hai bisogno?
gokan xchè non rispondi direttamente a chi partecipa alla discussione invece di fare confusione ulteriore?
forse hai bisogno di accedere direttamente al nodo selezionato dall'utente e quindi di una sorta di visita dell'albero fino ad arrivare al nodo scelto dall'utente e quindi calcolarne l'altezza
se non è così spiegati meglio

[gokan]

Originariamente inviato da bsummer
Vediamo se stavolta ho capito...

- l'utente inserisce un valore che rappresenta il valore contenuto in un nodo dell'albero.

- a questo punto tu devi cercare tale nodo

-una volta trovato tale nodo devi calcolare l'altezza dell'albero che si sviluppa da quel nodo fino alla sua foglia più bassa?

Esattamente questo vorrei fare.

[gokan]

Originariamente inviato da monkey72
allora di che interfaccia hai bisogno?
gokan xchè non rispondi direttamente a chi partecipa alla discussione invece di fare confusione ulteriore?
forse hai bisogno di accedere direttamente al nodo selezionato dall'utente e quindi di una sorta di visita dell'albero fino ad arrivare al nodo scelto dall'utente e quindi calcolarne l'altezza
se non è così spiegati meglio

Scusa se non sono riuscito a spiegarmi bene prima, adesso hai capito quello che vorrei fare. La mia funzione sopra non funziona come vorrei, tutto il problema sta nel momento in cui trovo il nodo cercato (a cui è associata una etichetta di tipo integer, cioè valore) è poi calcolare l'altezza di quel nodo.

[bsummer]

Allora, 3 funzioni:

function cerca_nodo(p: albero; valore: integer):albero;
var tmp :albero;
begin
  if (p= nil) then tmp :=nil
  else
    if p^.info=valore then tmp=p
      else
        begin
          tmp:=cerca_nodo(p^.AlbSin,valore);
	  if tmp = nil then tmp:=cerca_nodo(p^.AlbDes,valore);
	end
  cerca_nodo := tmp;
end



function cerca_altezza(p: albero; altezza:integer) : integer;
var max :integer;
    max_sub_sx:integer;
    max_sub_dx:integer

begin
  max := altezza;
  if p <> nil then
  begin
    max_sub_sx = cerca_altezza(p^.albsin,max+1);
    max_sub_dx = cerca_altezza(p^.albsin,max+1);
    if max_sub_dx>max_sub_sx then max := max_sub_dx
      else max:= max_sub_sx;
   cerca_altezza:= max;
  end
  else cerca_altezza:= max-1;
end
  

function cerca_altezza_nodo(p:albero; valore:integer):integer;
var nodo :albero;
    altezza: integer;

begin
  nodo = cerca_nodo(p,valore);
  if nodo = nil then cerca_altezza_nodo := -1
  else 
    begin
      altezza :=cerca_altezza(nodo,0);
      cerca_altezza_nodo := altezza;
    end
end

La prima ad essere_chiamata è cerca_altezza_nodo.
All'interno di questa verrà chiamata cerca_nodo il cui compito è ricercare dov'è all'interno dell'albero il nodo selezionato dall'utente. Se lo trova restituisce il puntatore a tale nodo.
Ora usando sto benedetto nodo come radice del sottoalbero che parte da esso viene richiamata la funzione cerca_altezza che retituisce l'altezza che c'è tra la radice (in tal caso il nodo selezionato) e la sua foglia più bassa. Nota: se alla funzione cerca_altezza viene passato un albero vuoto, questa restituirà -1.

Se hai problemi nel capire il codice (ho fatto ampio uso di ricorsione) son qua. Spero funzioni (in linea teorica mi pare di si, ma non avendolo effettivamente testato potrei aver commesso qualche errore ).

Aloha!

[gokan]

Originariamente inviato da bsummer
Allora, 3 funzioni:

function cerca_nodo(p: albero; valore: integer):albero;
var tmp :albero;
begin
  if (p= nil) then tmp :=nil
  else
    if p^.info=valore then tmp=p
      else
        begin
          tmp:=cerca_nodo(p^.AlbSin,valore);
	  if tmp = nil then tmp:=cerca_nodo(p^.AlbDes,valore);
	end
  cerca_nodo := p;
end



function cerca_altezza(p: albero; altezza:integer) : integer;
var max :integer;
    max_sub_sx:integer;
    max_sub_dx:integer

begin
  max := altezza;
  if p <> nil then
  begin
    max_sub_sx = cerca_altezza(p^.albsin,max+1);
    max_sub_dx = cerca_altezza(p^.albsin,max+1);
    if max_sub_dx>max_sub_sx then max := max_sub_dx
      else max:= max_sub_sx;
   cerca_altezza:= max;
  end
  else cerca_altezza:= max-1;
end
  

function cerca_altezza_nodo(p:albero; valore:integer):integer;
var nodo :albero;
    altezza: integer;

begin
  nodo = cerca_nodo(p,valore);
  if nodo = nil then cerca_altezza_nodo := -1
  else 
    begin
      altezza :=cerca_altezza(nodo,0);
      cerca_altezza_nodo := altezza;
    end
end

La prima ad essere_chiamata è cerca_altezza_nodo.
All'interno di questa verrà chiamata cerca_nodo il cui compito è ricercare dov'è all'interno dell'albero il nodo selezionato dall'utente. Se lo trova restituisce il puntatore a tale nodo.
Ora usando sto benedetto nodo come radice del sottoalbero che parte da esso viene richiamata la funzione cerca_altezza che retituisce l'altezza che c'è tra la radice (in tal caso il nodo selezionato) e la sua foglia più bassa. Nota: se alla funzione cerca_altezza viene passato un albero vuoto, questa restituirà -1.

Se hai problemi nel capire il codice (ho fatto ampio uso di ricorsione) son qua. Spero funzioni (in linea teorica mi pare di si, ma non avendolo effettivamente testato potrei aver commesso qualche errore ).

Aloha!

Azz.. sei il mago della ricorsione o cosa?
ti ringrazio tanto per la tua disponibilità, purtroppo non posso(devo) fare uso di funzioni di appoggio per calcolarmi l'altezza. Devi fare conto che mi sto preparando per un esame dove la prof. mi da l'intestazione della funzione o procedura ed io la devo implementare senza far uso di aiuti esterni..
Il tuo codice è comunque utile, può darmi nuovi spunti per trovare la soluzione tanto cercata.
Ciao

[bsummer]

Volendo c'è il modo di fregare la tua prof

E' sufficiente fare una unica funzione che lavora a stati.
Mi spiego meglio: come parametro alla funzione passi un valore che indica il suo stato attuale: all'inzio gli passerai come valore "cercanodo" e poi "trova latezza". All'interno la funzione avrà un case che in base allo stato eseguirà solo il codice interessato. Il problema è uniformare la funzione unica in modo che i paramtri ed il valore restituito si possano adattare a tutti e due gli scopi. Il problema maggiore è che una funzione restituisce un nodo, mentre l'altra un intero...certo che se la funzione altezza restituisse un nodo il cui campo info rappresenta l'altezza...

Aloha

[a2000]

Const II = 7
Dim p(0 To II, 1 To 2)



Sub ppp()
 p(6, 1) = 5: p(6, 2) = 7
 p(5, 1) = 3: p(5, 2) = 0
 p(3, 1) = 2: p(3, 2) = 4

 k = 5
 hh = f_altezza(k, p)
 Stop

End Sub



Function f_altezza(k, p())
 ReDim pn(0 To II, 1 To 2), pn(0 To II, 1 To 2)
 
  pn = p
  
  For n = 1 To II
   HH = 2 ^ n
   sk = 0
   For h = 1 To HH
    sk = sk + pn(k, h)
   Next h
   If sk = 0 Then f_altezza = n - 1: Exit Function
   
   ReDim pn1(0 To II, 1 To 2 * HH)
   For i = 1 To II
    For h = 1 To HH
     pn1(i, h) = pn(p(i, 1), h)
     pn1(i, HH + h) = pn(p(i, 2), h)
    Next h
   Next i
   pn = pn1
  
  Next n
 

End Function

[a2000]

domani vado a Disneyland:

ti interessa l'input del grafo, pardon, dell'albero sotto forma grafica disegnando nodi (pallocchi) e connettori ?