[PASCAL] Alberi Binari

[leadergl]

raga sto correggendo un esercizio che ho fatto, ma per correggerlo devo riempire due Alberi Binari, uno ordinato e l'altro non.

Per riempire l'albero binario ordinato ho usato questa funzione:

Procedure InserisciOrd(VAR A:tipoalbero;elem:integer);
begin
     if A=NIL then
     begin
        new(A);
        A^.elem:=elem;
        A^.sx:=NIL;
        A^.dx:=NIL;
     end else if elem<A^.elem then
         InserisciOrd(A^.sx,elem)
     else
         InserisciOrd(A^.dx,elem);
end;

e tutto funziona perfettamente....ma adesso devo riempire un albero binario non ordinato...come si fa?
Il mio albero deve risultare così:

                          13
              7                      19    
         2        21                          24
    34      5                           2            5
                                    34     15

spero si capisca.......qualcuno sa dirmi l'algoritmo per riempirlo?

[leadergl]

...up...

[leadergl]

raga nessuno sa come riempire un albero binario?...

[dierre]

edit...un secondo.

[dierre]

ti va bene in C++?

void CaricaAlbero (record_albero &alb, record_albero aux, int att_liv, int pos_padre){
char c;
tipo_valore val;
if(att_liv == 0) { alb=new record_albero
                      cout << "Inserire la radice";
                      cin >> alb->info;
                      CaricaAlbero (alb, aux, 1, 1); }
                
               else { cout << "Esiste il figlio sinistro dell'elemento" << pos_padre << "del livello" << att_liv-1 << "?";
do c=getch();
while(!((c == 's')||(c=='S')||(c=='n')||(c=='N')));
if ((c=='s')||(c=='S')) { aux->sin=new record_albero;
                                cout << "inserire valore";
                                cin >> aux->sin->info;
                                CaricaAlbero(alb,aux->sin,att_liv+1,pos_padre*2-1); }
                         else aux->sin=NULL;

cout << "Esiste il figlio sinistro dell'elemento" << pos_padre << "del livello" << att_liv-1 << "?";
do c=getch();
while(!((c == 's')||(c=='S')||(c=='n')||(c=='N')));
if ((c=='s')||(c=='S')) { aux->des=new record_albero;
                                cout << "inserire valore";
                                cin >> aux->des->info;
                                CaricaAlbero(alb,aux->des,att_liv+1,pos_padre*2); }
                         else aux->des=NULL;
}
}

se ti serve ti scrivo la struttura dati utilizzata.

[leadergl]

ti ringrazio...mi sarà utile, certo un po complicato dato che non conosco il C...

non è che riesci a scriverlo anche in Pascal?

in ogni caso ti ringrazio molto

[dierre]

purtroppo non lo conosco il pascal, mi spiace.
In c++ è realizzato con struct e puntatori.

[trapanator]

[quote=leadergl]raga sto correggendo un esercizio che ho fatto, ma per correggerlo devo riempire due Alberi Binari, uno ordinato e l'altro non.

Per riempire l'albero binario ordinato ho usato questa funzione:

Procedure InserisciOrd(VAR A:tipoalbero;elem:integer);
begin
     if A=NIL then
     begin
        new(A);
        A^.elem:=elem;
        A^.sx:=NIL;
        A^.dx:=NIL;
     end else if elem<A^.elem then
         InserisciOrd(A^.sx,elem)
     else
         InserisciOrd(A^.dx,elem);
end;

scusa, ma il tuo codice se A è diverso da NIL non fa niente se non che chiamarsi all'infinito... o no?

[leadergl]

Ok...ho risolto, grazie al tuo algoritmo ne ho scritto uno in Pascal che poi ho leggermente modificato per farlo funzionare meglio in Pascal.

Ecco il codice:

Procedure Inserisci(VAR A:tipoalbero; Liv_Att,Pos_Padre:integer);
var       ElemTemp:integer;
          c:char;
begin
     if Liv_Att=0 then
     begin
          write('Inserire elemento radice: ');
          readln(elemtemp);
          Inserisci(A,1,elemtemp);
     end else
     begin
          if A=NIL then
          begin
               new(A);
               A^.elem:=pos_padre;
               A^.sx:=NIL;
               A^.dx:=NIL;
          end;
          write('Esiste il figlio sinistro dell''elemento ',pos_padre,' del livello ',liv_att-1,'? ');
          readln(c);
          if (c='s') OR (c='S') then
          begin
               write('Inserire valore: ');
               readln(elemtemp);
               Inserisci(A^.sx,liv_att+1,elemtemp);
          end;
          write('Esiste il figlio destro dell''elemento ',pos_padre,' del livello ',liv_att-1,'? ');
          readln(c);
          if (c='s') OR (c='S') then
          begin
               write('Inserire valore: ');
               readln(elemtemp);
               Inserisci(A^.dx,liv_att+1,elemtemp);
          end;
     end;
End;

[leadergl]

Originariamente inviato da trapanator

scusa, ma il tuo codice se A è diverso da NIL non fa niente se non che chiamarsi all'infinito... o no?

Se A<>NIL il codice scende all'interno dell'albero finchè non trova una foglia vuota...e ci scrive il nuovo contenuto...

[trapanator]

Originariamente inviato da leadergl

Se A<>NIL il codice scende all'interno dell'albero finchè non trova una foglia vuota...e ci scrive il nuovo contenuto...

hai ragione

ho programmato per anni in turbo pascal... bei tempi

[trapanator]

1 curiosità: fai l'ITC?

[leadergl]

no...per mia sfortuna il Turbo Pascal me lo fanno usare all'univ...

Cmq..tornarno al mio esercizio ho notato che non mi da il risultato voluto..
Allo stato attuale:
1) Creo bene i due alberi di test
2) Sembra tutto ok
3) Il risultato è completamente sbagliato ed è un numero casuale che sta in memoria...

vi propongo l'esercizio così magari riuscite a vedere l'errore che io non trovo...
Testo dell'esercizio:

Sia A un albero binario ed AO un albero binario ordinato, contenente interi. Scrivere una funzione ricorsiva che dica quante foglie di A sono presenti in AO ma non sono foglie di AO.

Questo è il mio codice:

{Esame di Programmazione Mod. B del 20/07/2005}
{Esercizio 5}
Program Esercizio5;
Uses CRT;
Type TipoAlbero=^nodoalbero;
     nodoalbero=RECORD
                      elem:integer;
                      sx, dx:TipoAlbero;
                END;
var Al,AlO:tipoalbero;
    totale,par:integer;

function Trova(AO:TipoAlbero; elem:integer):integer;
var trovato,temp:integer;
begin
     trovato:=0;
     if (AO<>NIL) AND (trovato=0) then
     begin
          if (AO^.elem=elem) then
             if ((AO^.sx=NIL) OR (AO^.dx=NIL)) then
                trovato:=1
          else
          begin
               trovato:=0;
               temp:=Trova(AO^.sx,elem);
               temp:=Trova(AO^.dx,elem);
          end;
     end;
     trova:=trovato;
end;

function Es5(A,AO:tipoalbero; VAR parziale:integer):integer;
var temp:integer;
begin
     if A<>NIL then
     begin
          if (A^.sx=NIL) AND (A^.dx=NIL) then
             parziale:=parziale+trova(AO,A^.elem)
          else
          begin
               temp:=Es5(A^.sx,AO,parziale);
               temp:=Es5(A^.dx,AO,parziale);
          end;
     end else
         Es5:=parziale;
end;

Procedure Stampa(A:tipoalbero);
begin
     if A<>NIL then
     begin
          Stampa(A^.sx);
          writeln(A^.elem);
          Stampa(A^.dx);
     end;
end;

Procedure InserisciOrd(VAR A:tipoalbero;elem:integer);
begin
     if A=NIL then
     begin
        new(A);
        A^.elem:=elem;
        A^.sx:=NIL;
        A^.dx:=NIL;
     end else if elem<A^.elem then
         InserisciOrd(A^.sx,elem)
     else
         InserisciOrd(A^.dx,elem);
end;

Procedure Inserisci(VAR A:tipoalbero; Liv_Att,Pos_Padre:integer);
var       ElemTemp:integer;
          c:char;
begin
     if Liv_Att=0 then
     begin
          write('Inserire elemento radice: ');
          readln(elemtemp);
          Inserisci(A,1,elemtemp);
     end else
     begin
          if A=NIL then
          begin
               new(A);
               A^.elem:=pos_padre;
               A^.sx:=NIL;
               A^.dx:=NIL;
          end;
          write('Esiste il figlio sinistro dell''elemento ',pos_padre,' del livello ',liv_att-1,'? ');
          readln(c);
          if (c='s') OR (c='S') then
          begin
               write('Inserire valore: ');
               readln(elemtemp);
               Inserisci(A^.sx,liv_att+1,elemtemp);
          end;
          write('Esiste il figlio destro dell''elemento ',pos_padre,' del livello ',liv_att-1,'? ');
          readln(c);
          if (c='s') OR (c='S') then
          begin
               write('Inserire valore: ');
               readln(elemtemp);
               Inserisci(A^.dx,liv_att+1,elemtemp);
          end;
     end;
End;


{Main dell'esercizio}
begin
     clrscr;
     writeln('Creazione e Riempimento Albero: AlO');
     InserisciOrd(AlO,28);
     InserisciOrd(AlO,15);
     InserisciOrd(AlO,31);
     InserisciOrd(AlO,13);
     InserisciOrd(AlO,20);
     InserisciOrd(AlO,34);
     InserisciOrd(AlO,5);
     InserisciOrd(AlO,14);
     InserisciOrd(AlO,33);
     writeln('Creazione e Riempimento Albero: Al');
     Inserisci(Al,0,0);
     writeln('Avvio Esercizio 5');
     par:=0;
     totale:=0;
     totale:=Es5(Al,AlO,par);
     writeln;
     writeln('Elementi di A non presenti in Al0 che soddisfano: ',totale);
     writeln;
     writeln('Premere un tasto per continuare!');
     readln;
end.

[trapanator]

credo che l'errore sia qui:

function Es5(A,AO:tipoalbero; VAR parziale:integer):integer;
var temp:integer;
begin
     if A<>NIL then
     begin
          if (A^.sx=NIL) AND (A^.dx=NIL) then
             parziale:=parziale+trova(AO,A^.elem)
          else
          begin
               temp:=Es5(A^.sx,AO,parziale);
               temp:=Es5(A^.dx,AO,parziale);
          end;
     end else
         Es5:=parziale;
end;

noto che non viene verificato se A^.sx oppure A^.dx sono nil

[leadergl]

In un Albero le Foglie sono quei nodi che non hanno figli ne sinistri ne destri...giusto?!

Per questo verifico che entrambi (AND) siano uguali a NIL

Cmq facendo del Debug ho notato che qui succede qualcosa di strano:

function Trova(AO:TipoAlbero; elem:integer):integer;
var trovato,temp:integer;
begin
     trovato:=0;
     if (AO<>NIL) AND (trovato=0) then
     begin
          if (AO^.elem=elem) then
             if ((AO^.sx=NIL) OR (AO^.dx=NIL)) then
                trovato:=1
          else
          begin
               trovato:=0;
               temp:=Trova(AO^.sx,elem);
               temp:=Trova(AO^.dx,elem);
          end;
     end;
     trova:=trovato;
end;

In pratica quando sta ad IF (AO^.elem=elem) Then sia che la condizione sia vera che falsa salta automaticamente tutto il blocco e va direttamente a trova:=trovato; il che è sbagliato...

ma non capisco perchè fa così...

[leadergl]

Modificando in questo modo la procedura funziona bene...bah...:

function Trova(AO:TipoAlbero; elem:integer):integer;
var trovato,temp:integer;
begin
     if (AO<>NIL) AND (trovato=0) then
     begin
          if (AO^.elem=elem) AND ((AO^.sx=NIL) OR (AO^.dx=NIL)) then
                trovato:=1
          else
          begin
               temp:=Trova(AO^.sx,elem);
               temp:=Trova(AO^.dx,elem);
          end;
     end;
     trova:=trovato;
end;