2 (*****************************************************************************
\r
3 B O G D A N W I E R C Z Y N S K I
\r
5 Przedstawiony program umozliwia tworzenie drzewa BST oraz jego modyfikacje
\r
6 w celach dydaktycznych. Udostepnia cztery podstawowe operacje na tej
\r
7 strukturze danych:insert,delete,minimum i maximum. Struktora drzewa jest
\r
8 wyswietlana na ekranie i kazda akcja powodujaca jej zmiane wiaze sie ze
\r
9 zmiana drzewa na ekranie.
\r
10 ******************************************************************************)
\r
14 (* Klasa implementujaca BST jako abstrakcyjny typ danych z podstawowymi
\r
15 operacjami zwiazanymi z ta struktora. *)
\r
22 unit find:class(x:real;inout v:vertex);
\r
23 (* Wyszukanie w drzewie o korzeniu v wierzcholka z kluczem o wartosci x *)
\r
24 var father,(* Wskazanie na ojca szukanegoelementu *)
\r
25 znaleziony,(* Wskazanie na wierzcholek ktorego klucz ma wartosc x *)
\r
26 vpom:vertex,(* Zmienna pomocnicza *)
\r
27 lson:boolean;(* Zmienna informujaca ze znaleziony element jest
\r
31 father,znaleziony:=none;
\r
32 while vpom=/=none do
\r
33 if x<vpom.key then father:=vpom;vpom:=vpom.left;lson:=true
\r
35 if x>vpom.key then father:=vpom;vpom:=vpom.right;lson:=false
\r
36 else znaleziony:=vpom;exit
\r
42 unit delete:find procedure;
\r
43 (* Kasowanie wierzcholka ktorego wartosc klucza jest parametrem x w
\r
46 if znaleziony=/=none then
\r
47 if znaleziony.left=znaleziony.right then
\r
48 (* Usuwany element jest lisciem *) kill(znaleziony)
\r
50 if znaleziony.right=none then
\r
51 if father=none then v:=v.left
\r
52 (* Usuwany element jest korzeniem drzewa *)
\r
54 if lson then father.left:=znaleziony.left
\r
55 else father.right:=znaleziony.left
\r
60 vpom:=znaleziony.right;
\r
61 while vpom.left=/=none do
\r
64 znaleziony.key:=vpom.key;
\r
65 if vpom.right=none then kill(vpom)
\r
67 znaleziony:=vpom.right; (* Wykorzystanie zmiennej znaleziony
\r
68 jako zmiennej pomocniczej *)
\r
69 vpom.key:=znaleziony.key;
\r
70 vpom.left:=znaleziony.left;
\r
71 vpom.right:=znaleziony.right;
\r
79 unit insert:procedure(x:integer;inout v:vertex);
\r
80 (* Wstawienie do drzewa BST o korzeniu v elementu ktorego wartosc klucza
\r
84 if v=none then v:=new vertex; v.key:=x (* Puste drzewo *)
\r
89 if vpom.left=/=none then vpom:=vpom.left
\r
90 else vpom.left:=new vertex;
\r
95 if vpom.right=/=none then vpom:=vpom.right
\r
96 else vpom.right:=new vertex;
\r
105 unit minimum:function(v:vertex):integer;
\r
106 (* Znalezienie elementu o najmniejszym kluczu *)
\r
108 while v.left =/= none do
\r
114 unit maximum:function(v:vertex):integer;
\r
115 (* Znalezienie elementu o najwiekszym kluczu *)
\r
117 while v.right=/= none do
\r
126 unit SetCursor: procedure(x,y:integer);
\r
138 write(chr(27),"[",c,d,";",e,f,"H")
\r
141 unit inchar : IIUWgraph function : integer;
\r
142 (*podaj nr znaku przeslanego z klawiatury *)
\r
147 if i <> 0 then exit fi;
\r
152 unit ClearScreen: procedure;
\r
154 write(chr(27),"[2J")
\r
162 unit OpenWindow:procedure(x,y,height,width:integer);
\r
163 (* Otwarcie okienka ktorege lewy gorny rog ma wspolrzedne (x,y) i o wymiarach
\r
164 height x width (wysokosc x szerokosc) *)
\r
167 call SetCursor(x,y);
\r
169 for j:=2 to width-1 do write(chr(196)) od;
\r
171 for i:=2 to height-1 do
\r
172 call SetCursor(x+i-1,y);
\r
174 for j:=2 to width-1 do write(" ") od;
\r
177 call SetCursor(x+height-1,y);
\r
179 for j:=2 to width-1 do write(chr(196)) od;
\r
181 call SetCursor(x+1,y+1);
\r
184 unit CloseWindow:procedure(x,y,height,width:integer);
\r
185 (* Zamkniecie okienka ktorege lewy gorny rog ma wspolrzedne (x,y) i o wymiarach
\r
186 height x width (wysokosc x szerokosc) *)
\r
190 for i:=0 to height-1 do
\r
191 call SetCursor(x+i,y);
\r
192 for j:=1 to width do write(" ") od;
\r
196 unit negative:procedure;
\r
198 write(chr(27),"[7m");
\r
201 unit positive:procedure;
\r
203 write(chr(27),"[0m");
\r
206 unit MenuType:class;
\r
207 var beginingX,beginingY:integer,
\r
211 unit Inic:procedure;
\r
212 (* Zainicjowanie systemu,utorzenie odpowiednich danych, ich zainicjowanie,
\r
213 wyswietlenie menu . *)
\r
217 array Menu dim(0:4);
\r
218 for i:=0 to 4 do (* Wypelnienie tablicy menu *)
\r
219 Menu(i):=new MenuType;
\r
220 Menu(i).beginingX:=2; (* Wspolrzedne peczatku napisu opcji w menu *)
\r
221 Menu(i).beginingY:=8+i*16;
\r
222 case i (* Wstawienie odpowiedniego tekstu *)
\r
223 when 0: Menu(i).Name:="INSERT";
\r
224 when 1: Menu(i).Name:="DELETE";
\r
225 when 2: Menu(i).Name:="MINIMUM";
\r
226 when 3: Menu(i).Name:="MAXIMUM";
\r
227 when 4: Menu(i).Name:="EXIT";
\r
231 call SetCursor(1,1);
\r
236 call SetCursor(Menu(0).beginingX,Menu(0).beginingY);
\r
237 write(Menu(0).Name);
\r
240 call SetCursor(Menu(i).beginingX,Menu(i).beginingY);
\r
241 write(Menu(i).Name);
\r
243 call SetCursor(3,1);
\r
247 call SetCursor(Menu(0).beginingX,Menu(0).beginingY);
\r
250 unit printclass:class;
\r
251 (* Klasa ktora zajmuje sie wyswietlaniem drzewa na ekranie .
\r
252 (Mozna ja traktowac w pewnym sensie jak pprocedure) *)
\r
255 var i,j,last,przes,NumberOfVert:integer,
\r
256 VertCoord:array_of array_of integer,(*Tablica zawierajaca wspolrzedne
\r
257 wyswietlanych elementow *)
\r
258 queueForPrint:array_of vertex;(*kolejka elementow do wyswietlenia*)
\r
260 unit printTree:procedure(v:vertex);
\r
261 (* Procedura wyswietlajaca drzewo o podanym korzeniu *)
\r
263 isleft,isright:boolean;
\r
267 queueForPrint(last):=v;
\r
268 while first<=31 do (* Wstawianie 31 kolejnych wierzcholkow do kolejki
\r
269 i drukowanie ich.(Tylko tyle miesci sie na
\r
272 if queueForPrint(first)=none then
\r
273 queueForPrint(last+1),queueForPrint(last+2):=none;
\r
274 (*Niema synow wiec wstawiamy none *)
\r
276 queueForPrint(last+1):=queueForPrint(first).left;
\r
277 queueForPrint(last+2):=queueForPrint(first).right;
\r
278 isleft:=queueForPrint(first).left=/=none;
\r
279 isright:=queueForPrint(first).right=/=none;
\r
280 call Setcursor(VertCoord(X,first),VertCoord(Y,first)-1);
\r
281 (* Wypisanie elementu drzewa w odpowiednim formacie *)
\r
282 call format(queueForPrint(first).key);
\r
283 if isleft or_if isright then
\r
284 call Setcursor(VertCoord(X,first)+1,VertCoord(Y,first));
\r
287 call Setcursor(VertCoord(X,first*2)-1,VertCoord(Y,2*first));
\r
289 call Setcursor(VertCoord(X,first*2)-2,VertCoord(Y,2*first));
\r
291 for i:=1 to ( VertCoord(Y,first)-VertCoord(Y,2*first)-1) do
\r
295 if isleft and isright then write(chr(193))
\r
297 if isleft then write(chr(217))
\r
299 call Setcursor(VertCoord(X,first)+2,VertCoord(Y,first));
\r
304 for i:=1 to ( VertCoord(Y,2*first+1)-VertCoord(Y,first)-1) do
\r
308 call Setcursor(VertCoord(X,first*2+1)-1,
\r
309 VertCoord(Y,2*first+1));
\r
316 if queueForPrint(first)=/=none then
\r
317 call SetCursor(VertCoord(X,first),VertCoord(Y,first)-1);
\r
318 (* Wypisanie elementu drzewa w odpowiednim formacie *)
\r
319 call format(queueForPrint(first).key);
\r
320 if queueForPrint(first).left=/=none or_if
\r
321 queueForPrint(first).right=/=none then
\r
322 call Setcursor(VertCoord(X,first)+1,VertCoord(Y,first));
\r
332 unit format:procedure(x:integer);
\r
333 (* Procedura wybiera odpowiedni format wydruku w zaleznosci od liczby
\r
334 cyfr w liczbie x i wypisuje ja na ekran *)
\r
337 if x>999 then write(x:4)
\r
339 if x>99 then write(x:3)
\r
344 if x<-99 then write(x:4)
\r
346 if x<-9 then write(x:3)
\r
354 array VertCoord dim(1:2);
\r
355 for i:=1 to 2 do array VertCoord(i) dim(1:31);od;
\r
356 array queueForPrint dim(1:31);
\r
358 last,NumberOfVert:=1;
\r
359 (* Wypelnienie tablicy VertCoord wspolrzednymi wszystkich elementow
\r
360 ktore moga byc wyswietlone na ekranie *)
\r
362 for j:=1 to NumberOfVert do
\r
364 VertCoord(Y,last):=przes+(j-1)*2*przes;
\r
366 VertCoord(X,last):=i*4+7;
\r
369 NumberOfVert:=NumberOfVert*2;
\r
373 for last:=16 to 31 do
\r
374 VertCoord(Y,last):=2+przes;
\r
380 const IndicatorLeft=-75,(* Kody znakow wykorzystywanych przy poslugiwaniu *)
\r
381 IndicatorRight=-77,(* sie menu. *)
\r
384 ConstInsert=0,(* Indeksy tablicy Menu odpowiadajace opcjom *)
\r
390 var i,znak,AktPoz,key:integer,
\r
391 root:vertex,(* Korzen drzewa BST *)
\r
393 Menu :array_of MenuType;
\r
395 (********** POCZATEK PROGRAMU GLOWNEGO **********)
\r
397 print:=new printclass;
\r
402 when IndicatorRight:call SetCursor(Menu(AktPoz).beginingX,
\r
403 Menu(AktPoz).beginingY);
\r
404 write(Menu(AktPoz).Name);
\r
405 AktPoz:=(AktPoz+1) mod 5;
\r
406 call SetCursor(Menu(AktPoz).beginingX,
\r
407 Menu(AktPoz).beginingY);
\r
409 write(Menu(AktPoz).Name);
\r
411 call SetCursor(Menu(AktPoz).beginingX,
\r
412 Menu(AktPoz).beginingY);
\r
413 when IndicatorLeft: call SetCursor(Menu(AktPoz).beginingX,
\r
414 Menu(AktPoz).beginingY);
\r
415 write(Menu(AktPoz).Name);
\r
416 AktPoz:=(AktPoz+4) mod 5;
\r
417 call SetCursor(Menu(AktPoz).beginingX,
\r
418 Menu(AktPoz).beginingY);
\r
420 write(Menu(AktPoz).Name);
\r
422 call SetCursor(Menu(AktPoz).beginingX,
\r
423 Menu(AktPoz).beginingY);
\r
424 when Enter: if Aktpoz=ConstExit then call endrun
\r
426 call OpenWindow(3,Menu(AktPoz).beginingY,3,22);
\r
428 when ConstInsert:write("VALUE: ");
\r
430 call insert(key,root);
\r
431 call print.printtree(root);
\r
432 call SetCursor(Menu(AktPoz).beginingX,
\r
433 Menu(AktPoz).beginingY);
\r
434 when ConstDelete:write("VALUE: ");
\r
436 call delete(key,root);
\r
437 call CloseWindow(7,1,18,80);
\r
438 call print.printtree(root);
\r
439 call SetCursor(Menu(AktPoz).beginingX,
\r
440 Menu(AktPoz).beginingY);
\r
441 when ConstMinimum:if root =/= none then
\r
442 write(minimum(root):4," ")
\r
443 else write("Empty Tree ");
\r
445 write("press Esc");
\r
447 if inchar=Esc then exit fi;
\r
449 call SetCursor(Menu(AktPoz).beginingX,
\r
450 Menu(AktPoz).beginingY);
\r
451 when ConstMaximum:if root =/= none then
\r
452 write(maximum(root):4," ")
\r
453 else write("Empty Tree ");
\r
455 write("press Esc");
\r
457 if inchar=Esc then exit fi;
\r
459 call SetCursor(Menu(AktPoz).beginingX,
\r
460 Menu(AktPoz).beginingY);
\r
462 call CloseWindow(3,Menu(AktPoz).beginingY,3,22);
\r
463 call SetCursor(Menu(AktPoz).beginingX+1,
\r
464 Menu(AktPoz).beginingY);
\r
465 for i:=1 to 22 do write(chr(196)) od;
\r
466 call SetCursor(Menu(AktPoz).beginingX,
\r
467 Menu(AktPoz).beginingY);
\r