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 :confused:

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:muro:
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:mad:

[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... :rolleyes: 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 :cry:
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 :cry:
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 :confused: :confused:
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 :confused: :confused:
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 :D ).

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 :D ).

Aloha!

Azz.. sei il mago della ricorsione o cosa? :p
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 :D

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 ?

[bsummer]

:doh: e' vero ... è un albero binaro, che furbo che sono anch'io!
:(

[a2000]

comunque, in generale per tutti i grafi, per determinare tutti i cammini di n passi basta calcolare la potenza n-esima della matrice di vicinanza.

per matrici sparse, come nel caso degli alberi, può essere conveniente eseguire il prodotto tramite una struttura dati a puntatori.


certo i trenini di ricursive sono più perversi: come guardarsi il culo tra due specchi :D :D :oink:

[bsummer]

Cmq , per quanto sia efficente la soluzione a matrici penso che a Gokan non vada bene. A lui servono soluzioni che agiscano sugli alberi con la rappresentazione classica...Già la vedo la sua prof che gli riga tutto quanto perchè ha risolto il problema usando matrici e vettori invece di nodi...:D

[a2000]

alla prof di gokan gliela possiamo dare a matrici o a vettori, a strutture o ad oggetti, cotta o cruda, moscia o dura, dura o dura o dura o dura o dura

[a2000]

e quella che disegni l'albero con i cerchi e e i connettori di excel, nomini i nodi a cazzo tuo con stringhe alfanumeriche, e poi lui se lo legge e ti prompta la richiesta di quale nodo vuoi sapere altezza, profondità, temperatura, pressione e ciclo mestruale ?

[gokan]

Originariamente inviato da bsummer
Cmq , per quanto sia efficente la soluzione a matrici penso che a Gokan non vada bene. A lui servono soluzioni che agiscano sugli alberi con la rappresentazione classica...Già la vedo la sua prof che gli riga tutto quanto perchè ha risolto il problema usando matrici e vettori invece di nodi...:D
Infatti..ho bisogno delle più classiche rappresentazioni degli alberi....

[maxithron]

vedi un po se ti possono essere utili questi link:

http://www.dis.uniroma1.it/~pascal/programmi/strutdat/index.shtml#alberi


http://www.redangel.it/Click_file.asp?m=646

[a2000]

Originariamente inviato da gokan
Infatti..ho bisogno delle più classiche rappresentazioni degli alberi....

e cioè ?

comunque qualunque sia la rappresentazione la converti in una passata in una matrice di vicinanza o una matrice di puntatori (che poi sono le rappresentazioni standard dei grafi).

[cisc]

io parlavo di interfaccia perchè se si ricerca un nodo per il suo valore, il valore è ripetuto e l'albero non è ordinato (oppure lo è????:confused: ), si possono ottenere valori diversi a seconda dell'algoritmi che si usa nella ricerca del nodo.

anche se l'albero è ordinato, per ottenere un output "unico" biosogna non inserire un valore se già presente..........

[gokan]

Gli alberi che dobbiamo considerare nelle nostre funzioni e procedure sono dei semplici alberi binari di ricerca, sistemati in modo che un nodo con etichetta minore dell'etichetta del nodo radice va a sinistra, altrimenti a destra...come quello della figura nella prima pagina del post.

Per a2000
Ti ringrazio per l'aiuto, ma proferisco lavorare in maniera tradizionale, senza grafi e matrici di adiacenza...E' strano come sia semplice calcolare la profondità di un nodo mentre per l'altezza sto rincoglionendo..:eek:

[bsummer]

Ho cercato di trasformare le 3 funzioni che ti avevo postato in una unica...dovrebbe funzionare, ma come al solito l'ho fatto di getto e non l'ho provato...prova a darci un'occhiata...


function faccio_tutto(p: albero; var n: albero; valore: integer; stato: integer;altezza:integer):integer;

var tmp: integer;
max :integer;
max_sub_sx:integer;
max_sub_dx:integer;

begin

(* non ricordo come funziona il case in pascal...aggiustalo tu... )

case stato of

1: if (p= nil) then n :=nil
else
if p^.info=valore then n :=p
else
begin
tmp:= faccio_tutto(p^.AlbSin,n,valore,stato,0);
if n = nil then tmp:=faccio_tutto(p^.AlbDes,n,valore,stato,0);
end
stato := stato +1;
faccio_tutto := 0;
break;

2: max := altezza;
if n <> nil then
begin
max_sub_sx = faccio_tutto(nil,n^.albsin,0,stato,max+1);
max_sub_dx = faccio_tutto(nil,n^.albsin,0,stato,max+1);
if max_sub_dx>max_sub_sx then max := max_sub_dx
else max := max_sub_sx;
faccio_tutto := max;
end
else faccio_tutto:= max-1;
end case;

end



Ora basta chiamare la funzione con

risultato := faccio_tutto(p,n,valore,1,0);

[gokan]

Per bSummer
Mi spiegheresti come vuoi usare quell'istruzione Break? Non ho mai usato tale espressione, la guida in linea di Delphi dice:

procedure Break;

Description

The Break procedure causes the flow of control to exit a for, while, or repeat statement and continue at the next statement following the loop statement.

A call to Break must be contained in a for, while, or repeat statement, or the compiler reports an error.

Note: Break will not violate the flow of control dictated by a try..finally construct. If a break occurs inside a try..finally, the finally clause will be entered.

ESEMPIO

var

S: string;
begin
while True do
begin
ReadLn(S);
try
if S = '' then Break;
WriteLn(S);
finally
{ do something for all cases }
end;
end;
end;

[bsummer]

Emh... a nulla !:D
Te l'ho detto...non ricordo come funziona il case in pascal, così ho fatto na roba tipo C, dove dopo ogni statement del case ci va il break altrimenti si vanno ad eseguire anche le istruzioni dei casi seguenti...

Il break, serve solo a dire che il caso del "case" è terminato, ma questo in c,c++ e java. Ad esempio in vb non ci và, ed in pascal , vista la domanda, neppure :D :D :D

Perdono, è dai tempi delle superiori che non scrivo + nulla in pascal, e sono passati 8 anni!

Aloha!

[gokan]

Originariamente inviato da bsummer
Emh... a nulla !:D
Te l'ho detto...non ricordo come funziona il case in pascal, così ho fatto na roba tipo C, dove dopo ogni statement del case ci va il break altrimenti si vanno ad eseguire anche le istruzioni dei casi seguenti...

Il break, serve solo a dire che il caso del "case" è terminato, ma questo in c,c++ e java. Ad esempio in vb non ci và, ed in pascal , vista la domanda, neppure :D :D :D

Perdono, è dai tempi delle superiori che non scrivo + nulla in pascal, e sono passati 8 anni!

Aloha!
Ho capito
:sofico:
La tua funzione è sintatticamente corretta, purtroppo il valore restituito è sempre zero, probabilmente salta un piccolo passaggio....

[bsummer]

Forse ho capito il perchè...nella dichiarazione della funzione metti un "var" davanti a "stato:integer"...
Non essendo passato per riferimento, al ritorno dall'iterazione dove si è trovato il nodo cercato il valore torna a "1"...morale: non viene mai eseguito il codice del caso 2, ciè quello che calcola la profondità...:D

[gokan]

Così ci capiamo meglio

{Altezza Nodo}

program AltezzaNodo;
{$APPTYPE CONSOLE}
uses SysUtils;

type
pAlbero=^nodo;
nodo=record
info: integer;
AlbSin: pAlbero;
AlbDes: pAlbero;
end;



var
p,n:pAlbero;
valore,stato: integer;



Function crea_nodo (p: pAlbero; val: integer): pAlbero;
begin
{La creazione del primo nodo è un caso a parte, quindi è necessario effettuare
un test sul puntatore alla radice per vedere se l'albero ancora è vuoto}
if p=NIL then begin

//Creazione del nodo
new(p);
p^.info:= val; //Inserimento del valore nel campo infoormazione dell'elem.
p^.AlbSin:= NIL; //Marca di albero sinistro vuoto
p^.AlbDes:= NIL; //Marca di albero destro vuoto
end
else begin //se l'albero non è vuoto
(*Ricerca del punto di inserimento*)
if val > p^.info then
//visita il sottoalbero destro
p^.AlbDes:=crea_nodo(p^.AlbDes, val)
else
if val < p^.info then
//visita il sottoalbero sinistro
p^.AlbSin:=crea_nodo(p^.AlbSin, val);
end;

crea_nodo:=p; //Ritorna il puntatore alla radice
end;

Function alb_bin: pAlbero;
var
x: integer; //Contiene l'infoormazione immessa nell'albero

begin
p:=NIL; //Crea l'albero vuoto inizializzando a NIL il punt. alla radice

repeat
writeln;
write('Inserisci un valore(0 per finire): ');
readln(x);
if x<>0 then //Finchè il val. immesso è diverso da zero
p:=crea_nodo(p,x); //Viene invocata la funzione crea_nodo
until x=0;

alb_bin:=p; //Ritorna la radice
end;




function faccio_tutto(p: pAlbero; var n: pAlbero; valore: integer; var stato: integer;altezza:integer):integer;

var tmp: integer;
max :integer;
max_sub_sx:integer;
max_sub_dx:integer;

begin


case stato of

1:begin
if (p= nil) then n :=nil
else
if p^.info=valore then n :=p
else
begin
tmp:= faccio_tutto(p^.AlbSin,n,valore,stato,0);
if n = nil then tmp:=faccio_tutto(p^.AlbDes,n,valore,stato,0);
end;
stato := stato +1;
faccio_tutto := 0;
end;

2: begin
max := altezza;
if n <> nil then
begin
max_sub_sx := faccio_tutto(nil,n^.albsin,0,stato,max+1);
max_sub_dx := faccio_tutto(nil,n^.albsin,0,stato,max+1);
if max_sub_dx>max_sub_sx then max := max_sub_dx
else max := max_sub_sx;
faccio_tutto := max;
end
else faccio_tutto:= max-1;
end;
end;
end;



var
risultato:integer;
(*MAIN*)
begin
p:=alb_bin;
writeln('Inserisci il nodo di cui cercare l''altezza: ');
read(valore);
risultato := faccio_tutto(p,n,valore,stato,0); //così?
write(risultato);
readln;
readln;
end.

Con queste modifiche ritornano valori molto grandi!!

[bsummer]

Ti sei dimenticato di inizializzare stato a 1. Scrivi
Stato := 1

prima della chiamata a faccio_tutto.

Poi dimmi come va...

[gokan]

Originariamente inviato da bsummer
Ti sei dimenticato di inizializzare stato a 1. Scrivi
Stato := 1

prima della chiamata a faccio_tutto.

Poi dimmi come va...
Continua a restituire solo zero
:(

[bsummer]

mi sono accorto che in alcuni casi non funziona. Argh!:mad:

ok, se hai pazienza domani ti posto la versione testata e funzionante al 100%.

Aloha

[bsummer]

Allora, sono arrivato a questo, solo che non è una funzione ma una procedura...penso che si possa trasformare in funzione ma c'è da pensarci su un po'...

Cmq l'esercizio in sè non sarebbe per nulla difficile, ma lo diventa quando si impone la limitazione di fare tutto con una sola funzione...

Vabbeh, prova questa


Procedure proc(p :albero; val :integer; ap :integer; var mp :integer; found : boolean);
begin
if found = false then
begin
if p <> nil then
begin
if p^.info = val then proc(p,val,0,mp,true)
else
begin
proc(p^.sx, val,0,mp,false);
proc(p^.dx, val,0,mp,false);
end
end
end
else
begin
if p<>nil then
begin
if mp<ap then mp:=ap;
proc(p^.sx,val,ap+1,mp,true);
proc(p^.dx,val,ap+1,mp,true);
end
end
end


I parametri ap e mp sono rispettivamente l'altezza attuale e quella massima: si usano solo per tener traccia, una volta trovato il nodo interessato, a quale altezza si è giunti continuando a scorrere l'albero e qual'è il nodo più basso finora incontrato.

La procedura restituisce in mp l'altezza...Ricordati di inizializzare tale variabile a 0 prima di fare la chiamata alla proc.

Aloha!

[gokan]

adesso, funziona :D
Certo che se mi piazza una cosa simile all'esame..la prendo nel c...
Grazie tante per l'aiuto.
Ti disturberò ancora tra liste e alberi!!!
;)

[bsummer]

Come ho già detto, di per sè l'esercizio non è difficile...tuttavia mi sembra alquanto strano che ti forzino a creare un'unica funzione quando la scomposizione di un problema in parti più piccole sta alla base di una buona programmazione...

Beh, disturba pure quando vuoi ;)

Aloha!

[gokan]

Sono alle prese con l'ultimo (spero) esercizio sugli alberi. Devo calcolare l'ampiezza di un albero. Significa che devo costruire una funzione del tipoFunction Ampiezza(p:pAlbero,....,...):integer;
che restituisce il massimo numero di nodi di un livello.
In maniera del tutto teorica ho pensato che non dovrebbe essere complicato trovare l'ampiezza di un albero binario (che spesso man mano che si scende diventa più "folto"). La funzione dovrebbe essere una via di mezzo tra una funzione ContaNodi e quella del calcolo della Profondità. Secondo voi come conviene affrontare il problema? Devo scandire un livello, scendere di livello, memorizzare da qualche parte l'attuale max numero di nodi e scendere fino alle foglie...
:muro:

[cisc]

prova così (non l'ho testato, se trovi qualche problema prova a correggerlo tu ;) )


function prof (p: albero; lc.l:integer;):integer;
var r:integer;

begin
r:=0;
if p<>nil then
if lc=l then r:=1
else r:=prof (p^.dx,lc,l+1)+ prof (p^.sx,lc,l+1);
prof:=r;
end;

nel progamma principale si passa come livello iniziale l zero

[gokan]

Originariamente inviato da cisc
prova così (non l'ho testato, se trovi qualche problema prova a correggerlo tu ;) )


function prof (p: albero; lc.l:integer;):integer;
var r:integer;

begin
r:=0;
if p<>nil then
if lc=l then r:=1
else r:=prof (p^.dx,lc,l+1)+ prof (p^.sx,lc,l+1);
prof:=r;
end;

nel progamma principale si passa come livello iniziale l zero

Mi potresti fare qualche commento al tuo codice? Cosa rappresentano l ed lc ? Che ragionamento usi?
Grazie e Ciao

[cisc]

function prof (p: albero; lc,l:integer) :integer; {lc è il livello di cui
si vuole sapere il numero di nodi, mentre l è il livello attuale}
var r:integer;

begin
r:=0; {se p=nil, il valore di r rimane 0, quindi la funzione restituirà zero}
if p<>nil then
if lc=l then r:=1 { se lc ed l sono uguali, vuol dire che abbiamo trovato un nodo del livello che ci interessa, quindi restituiremo 1}
else r:=prof (p^.dx,lc,l+1)+ prof (p^.sx,lc,l+1); {altrimenti dobbiamo andare ancora più in profondità........}
prof:=r;
end;



ciao.

[a2000]

Originariamente inviato da gokan
....

Per a2000
Ti ringrazio per l'aiuto, ma proferisco lavorare in maniera tradizionale, senza grafi e matrici di adiacenza...E' strano come sia semplice calcolare la profondità di un nodo mentre per l'altezza sto rincoglionendo..:eek:

cioé, cazzo, è proprio vero che siamo all'inizio della fine ...

guarda che l'approccio più generale e potente (e non tradizionale ma fondamentale) alla soluzione dei problemi non degli alberi ma dei grafi in generale è proprio la rappresentazione con matrici di vicinanza (a valori reali).

comunque per matrici sparse (come nel caso degli alberi binari o no) si adotta spesso una rappresentazione a puntatori che è quella a cui mi sembra tu faccia riferimento e che è quella adottata nella funzione che ti ho proposto.

[a2000]

passando alle cose serie:
a Dineyland Paris, da cui sono tornato or ora, vi consiglio vivamente:

FantasyLand
Peter Pan's Flight
"it's a small world" (per gli amanti della programmazione OO)

AdventureLand
Pirates Of the Caribbean
Indiana Jones and the Temple of Peril
La Cabane de Robinson

FrontierLand
Big Thunder Muntain
Phantom Manor

DiscoveryLand
Star Tours
Autopia
Space Mountain

La parata e i fuochi di artificio della sera (rigorosamente ad alberi binari)


:p