Pascal: Alberi

[bsummer]

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

[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...

[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...

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/p...x.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 è???? ), 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..

[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 !
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

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 !
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

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

Aloha!

Ho capito

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à...

[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!

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!