Zadanie 2 (egzamin poprawkowy z WDI 8.09.2011)
Drzewo BST o kluczach całkowitych jest k-rzadkie, jeśli moduł różnicy kluczy z każdych dwóch różnych wierzchołków jest większy od k.
Napisz procedurę, która dla danego drzewa BST o kluczach całkowitych i liczby k sprawdzi czy to drzewo jest k-rzadkie.
Opis algorytmu : tworze z drzewa liste posortowana rosnaco a nastepnie sprawdzam kazde sasiadujace ze soba elementy tej listy,
jesli modul roznicy kazdych dwoch sasiadujacych ze soba elementow jest wiekszy od k to jest ona k-rzadka.
Kod: Zaznacz cały
function zad2(r:wsk; k:integer):boolean;
var
l:lista;
procedure dodaj na liste(i:integer);
var
t:lista;
begin
new(t);
t^.liczba:=i;
t^.next:=l;
l:=t;
end;
procedure stworz_liste(v:wsk);
begin
if v<>nil then begin
stworz_liste(v^.lewy);
dodaj na liste(v^.liczba);
stworz_liste(v^.prawy);
end;
end;
function sprawdz_liste(c:lista):boolean;
var
z:boolean;
d:integer;
begin
if c<>nil then
if c^.next=nil then z:=false {lista ma jeden element czyli drzewo nie jest k-rzadkie}
else begin
z:=true;
while (z=true) and (c^.next<>nil) do begin
if (c^liczba-c^.next^.liczba<0) then d:=c^.next^.liczba-c^.liczba
else d:=c^liczba-c^.next^.liczba;
if d>k then c:=c^.next
else z:=false;
end;
end
else z:=false;
sprawdz_liste:=z;
end;
begin
l:nil;
stworz_liste(r);
zad2:=sprawdz_liste(l);
end;
