Podstawy Informatyki - Laboratorium
Politechnika Świętokrzyska, Wydział Elektrotechniki, Automatyki i Informatyki
Turbo Pascal
Instrukcja laboratoryjna nr 13
Opracował: dr inż. Grzegorz Słoń
kwiecień 2005 r.
Zmienne dynamiczne - drzewo binarne - cz. 1
Napisać program konstruujący doskonale zrównoważone drzewo binarne zawierające n liczb całkowitych oraz wyświetlający zawartość tego drzewa na ekranie monitora.
uses Crt;
type TWsk = ^TElement;
TElement = record
d: integer;
lewe,prawe: TWsk;
end;
var K: TWsk;
n: integer;
{-----}
function Drzewo(n: integer): TWsk;
var Q: TWsk;
dane: integer;
nl,np: integer;
begin
if n=0 then Drzewo:=NIL
else begin
nl:=n div 2;
np:=n-nl-1;
write('Kolejna liczba: '); readln(dane);
New(Q);
Q^.d:=dane;
Q^.lewe:=Drzewo(nl);
Q^.prawe:=Drzewo(np);
Drzewo:=Q;
end;
end;
{-----}
procedure Drukuj(K:TWsk; wciecie:integer);
var i:integer;
begin
if K<>NIL then with K^ do
begin
Drukuj(lewe,wciecie+1);
for i:=1 to wciecie do write(' ');
writeln(d:2);
Drukuj(prawe,wciecie+1);
end;
end;
{-----}
begin
ClrScr;
write('Ile bedzie liczb?: '); readln(n);
K:=NIL;
K:=Drzewo(n);
Drukuj(K,0);
ReadKey;
end.
Uzupełnić program o procedury lub funkcje realizujące następujące działania:
wyznaczenie sumy wszystkich elementów;
function Suma(K:TWsk): integer;
begin
if K=NIL then Suma:=0
else Suma:=Suma(K^.lewe)+K^.d+Suma(K^.prawe);
end;
wyznaczenie liczby elementów dodatnich.
function Ile_dod(K:TWsk): integer;
begin
if K=NIL then Ile_dod:=0
else if K^.d>0 then Ile_dod:=Ile_dod(K^.lewe)+1+Ile_dod(K^.prawe)
else Ile_dod:=Ile_dod(K^.lewe)+Ile_dod(K^.prawe);
end;
Zmodyfikować funkcje zdefiniowane w punkcie 2 tak, aby wykonywały działania zgodnie z porządkiem wzdłużnym oraz wstecznym.
Opracować program konstruujący drzewo poszukiwań przechowujące liczby typu integer.
uses Crt;
type TWsk = ^TElement;
TElement = record
d: integer;
lewe,prawe: TWsk;
end;
var K: TWsk;
i,n: integer;
liczba: integer;
{-----}
procedure Wstaw(element: integer; var P: TWsk);
begin
if P=NIL then begin
New(P);
P^.d:=element;
P^.lewe:=NIL; P^.prawe:=NIL;
end
else if element<P^.d then Wstaw(element,P^.lewe)
else Wstaw(element,P^.prawe);
end;
{-----}
procedure Drukuj(K:TWsk; wciecie:integer);
var i:integer;
begin
if K<>NIL then with K^ do
begin
Drukuj(prawe,wciecie+1);
for i:=1 to wciecie do write(' ');
writeln(d:2);
Drukuj(lewe,wciecie+1);
end;
end;
{-----}
begin
ClrScr;
K:=NIL;
write('Ile bedzie element˘w?: '); readln(n);
for i:=1 to n do
begin
write(i,' element: '); readln(liczba);
Wstaw(liczba,K);
end;
writeln;
Drukuj(K,0);
writeln; writeln('Nacisnij dowolny klawisz...');
ReadKey;
end.
Uzupełnić program z punktu 4 o procedurę usuwającą z drzewa element spełniający określone warunki.
procedure Usun(klucz:integer; var P:TWsk);
var Q: TWsk;
{***}
procedure Usun1(var R:TWsk);
begin
if R^.prawe<>NIL then Usun1(R^.prawe)
else begin
Q^.d:=R^.d;
Q:=R;
R:=R^.lewe;
end;
end;
{***}
begin
if P=NIL then writeln('Nie znaleziono wskazanego elementu.')
else if klucz<P^.d then Usun(klucz,P^.lewe)
else if klucz>P^.d
then Usun(klucz,P^.prawe)
else begin
Q:=P;
if Q^.prawe=NIL
then P:=Q^.lewe
else if Q^.lewe=NIL
then P:=Q^.prawe
else Usun1(Q^.lewe);
Dispose(Q);
end;
end;
Zmodyfikować program z poprzedniego punktu tak, aby możliwe było usunięcie wszystkich elementów spełniających zadany warunek.
Zmodyfikować program z poprzedniego punktu tak, aby było możliwe dodanie do drzewa dowolnej liczby elementów.
Uzupełnić program z poprzedniego punktu o procedury umożliwiające przechowywanie elementów w pliku o nazwie drzewo.dat.
Zmodyfikować program z poprzedniego punktu tak, aby każdy element, oprócz liczby, zawierał również krotność jej występowania.
str. 2/3 Turbo Pascal - Instrukcja nr 13
Turbo Pascal - Instrukcja nr 13 str. 3/3