Newsgroup: it.comp.lang.pascal
Titolo: Help Alberi Binari

Salve a tutto il ng
ho bisogno assolutamente e URGENTEMENTE di qualcuno che mi fornisca un paio
di algoritmi....
per calcolare la profondità di un albero
per calcolare la lunghezza del suo ramo più corto
Grazie a chi vorrà aiutarmi
Saluto
Rolando

per calcolare la lunghezza del suo ramo piy corto
uses crt;
type  ptr_nodo_albero = ^nodo_albero;
      nodo_albero = record
                      num : integer;
                      sinistra, destra : ptr_nodo_albero;
                    end;
var radice : ptr_nodo_albero;
    i : integer;
    max, min : word;
procedure inserimento(var nodo : ptr_nodo_albero; n : integer);
var nodo_temp : ptr_nodo_albero;
begin
  new(nodo_temp);
  nodo_temp^.num := n;
  nodo_temp^.sinistra := nil;
  nodo_temp^.destra := nil;
  if (nodo = nil) then
    nodo := nodo_temp
  else
  if (nodo^.num <= n) then
       inserimento(nodo^.sinistra, n)
  else
  inserimento(nodo^.destra, n)
end;
procedure scrivi_albero(nodo : ptr_nodo_albero);
begin
  if (nodo^.destra <> nil) then scrivi_albero(nodo^.destra);
  write(nodo^.num,',');
  if (nodo^.sinistra <> nil) then scrivi_albero(nodo^.sinistra);
end;
procedure calcola_profondita(nodo : ptr_nodo_albero;
                             var  min, max : word; l : word);
begin
  if (nodo = nil) then
  begin
    if (l < min) then min := l;
    if (l > max) then max := l;
  end
  else
  begin
    inc(l);
    calcola_profondita(nodo^.sinistra, min, max, l);
    calcola_profondita(nodo^.destra, min, max, l);
  end;
end;
begin
  randomize;
  clrscr;
  radice := nil;
  for i := 1 to 100 do
     inserimento(radice, random(100));
  scrivi_albero(radice);
  writeln;
  min := $FFFF;
  max := 0;
  calcola_profondita(radice, min, max, 0);
  writeln('profondita'' minima  : ', min);
  writeln('profondita'' massima : ', max);
end.
 ___
(___)
()__
(___)
 __()
(___)
Skyscraper
----------------------------------------------------------------
"Sopra il camper la capra campa, sotto il camper la capra crepa"
--
Posted from 
itaca.ulysse.it
 [195.223.254.1]
via Mailgate.ORG Server - 
http://www.mailgate.org

end;
Ho dei dubbi su questa procedura.
Ma mi potrei anche sbagliare.
Se do come input questo albero:
                     a
                 /         \
             b              c
               \           /    \
               d        e       f
             /     \
          g        h
(speriamo si capista bene)
Io suppongo che il ramo piu' corto sia quello che porta al nodo E (o
anche il nodo F )
La suluzione giusta dovrebbe essere
	min=3
	max=4
mentre ho l'impressione che la tua procedura dia:
	min=2
	max=4
considerando B la fine del ramo piu' corto.
A meno che io non sbagli nel considerare quale e' il ramo piu' corto,
la soluzione secondo me dovrebbe essere la seguente:
procedure   vista(p:ptr;  i:integer;  var  min,max:integer);
begin
	if p<>nil then begin
	   inc(i);
	   if  (p^.sx=nil) and (p^.dx=nil) then begin
		if (i>max) then max:=i;
		if (i<min) then min:=i
	   end;
	   visita(p^.sx,i,min,max);
	   visita(p^.dx,i,min,max)
	end
end;
begin   {  main     }
	i:=0;
	max:=0;
	min:=maxint;
	visita(radice,i,min,max);
	writeln('Profondita = ',max);
	writeln('Ramo piu corto = ',min);
end.
Ciao,  Fabio
fabi...@rocketmail.com

considerando B la fine del ramo piu' corto.
Esatto, hai ragione.
Ho riscritto il programma considerando esattamente il tuo albero :
uses crt;
type  ptr_nodo_albero = ^nodo_albero;
      nodo_albero = record
                      num : integer;
                      sinistra, destra : ptr_nodo_albero;
                    end;
procedure inserimento(var nodo : ptr_nodo_albero; n : integer);
var nodo_temp : ptr_nodo_albero;
begin
  new(nodo_temp);
  nodo_temp^.num := n;
  nodo_temp^.sinistra := nil;
  nodo_temp^.destra := nil;
  if (nodo = nil) then
    nodo := nodo_temp
  else
  if (n <= nodo^.num) then
     inserimento(nodo^.sinistra, n)
  else
  inserimento(nodo^.destra, n)
end;
procedure scrivi_albero(nodo : ptr_nodo_albero);
begin
  if (nodo^.sinistra <> nil) then scrivi_albero(nodo^.sinistra);
  write(nodo^.num,',');
  if (nodo^.destra <> nil) then scrivi_albero(nodo^.destra);
end;
procedure calcola_profondita(nodo : ptr_nodo_albero;
                             var  min, max : word; l : word);
begin
    inc(l);
    if (nodo^.sinistra <> nil) then
       calcola_profondita(nodo^.sinistra, min, max, l);
    if (nodo^.destra <> nil)
       then calcola_profondita(nodo^.destra, min, max, l);
    if (nodo^.sinistra = nil) and (nodo^.destra = nil) then
    begin
      if (l < min) then min := l;
      if (l > max) then max := l;
    end;
end;
var radice : ptr_nodo_albero;
    i : integer;
    max, min : word;
begin
  randomize;
  clrscr;
  radice := nil;
  inserimento(radice, 9);
  inserimento(radice, 5);
  inserimento(radice, 7);
  inserimento(radice, 6);
  inserimento(radice, 8);
  inserimento(radice, 11);
  inserimento(radice, 12);
  inserimento(radice, 10);
  scrivi_albero(radice);
  writeln;
  min := $FFFF;
  max := 0;
  calcola_profondita(radice, min, max, 0);
  writeln('profondita'' minima  : ', min);
  writeln('profondita'' massima : ', max);
end.
Skyscraper
---------------------------
andrea_...@bigfoot.com
