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

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.

2. Uzupełnić program o procedury lub funkcje realizujące następujące działania:

1. 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;

2. 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;

3. Zmodyfikować funkcje zdefiniowane w punkcie 2 tak, aby wykonywały działania zgodnie z porządkiem wzdłużnym oraz wstecznym.

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

5. 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;

6. Zmodyfikować program z poprzedniego punktu tak, aby możliwe było usunięcie wszystkich elementów spełniających zadany warunek.

7. Zmodyfikować program z poprzedniego punktu tak, aby było możliwe dodanie do drzewa dowolnej liczby elementów.

8. Uzupełnić program z poprzedniego punktu o procedury umożliwiające przechowywanie elementów w pliku o nazwie drzewo.dat.

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