Rozdział 12
Programowanie dynamicznych struktur danych
z wykorzystaniem programowania obiektowego
.
.
.
12.4. Drzewa binarne
Drzewa binarne są strukturą danych umożliwiającą bardzo szybki
dostęp do żądanej informacji. Dla drzew wyważonych wyszukiwanie danego
elementu pod względem liczby wykonywanych operacji można porównać do
wyszukiwania binarnego dla tablic (wyszukiwanie binarne zostało omówione
w pierwszej książce z cyklu poświęconego nauce programowania [20]).
Przypominamy, że dla list wyszukiwania binarnego nie można zastosować.
Drzewo binarne jest to struktura danych, w której każdy z elementów
tej struktury może zawierać wskazania na dwa inne elementy: lewy i prawy.
Każdy z tych elementów może zawierać wskazania na następne dwa ele-
menty, tak że w rezultacie można powiedzieć, że każdy z elementów drzewa
może zawierać wskazania na dwa inne poddrzewa. Wszystkie poddrzewa
muszą mieć elementy różne. Pierwszy element drzewa nazywamy korze-
niem. Drzewo binarne ilustruje rys. 12.21.
Na rys. 12.21 w kółkach podano wartości przechowywane w węzłach
drzewa. Wskazania na kolejne węzły obrazują kreski.
Rysunek można obejrzeć w książce
Drzewo binarne przedstawione na rys. 12.21 posiada ważną cechę. Jest
ono uporządkowane tzn. w każdym lewym poddrzewie znajdują się wartości
mniejsze niż w prawym poddrzewie. Tworzenie uporządkowanego drzewa
binarnego jest bardzo proste. Każdy nowy element dopisujemy zgodnie z
regułą: mniejszy na lewo, większy na prawo. Dla drzewa przedstawionego
na rys.12.21 element 15 jest korzeniem, element 8 dodajemy na lewo (ponie-
waż jest mniejszy od 15), element 20 dodajemy na prawo, natomiast element
10 dodajemy do lewego poddrzewa elementu 15 i następnie do prawej gałęzi
odchodzącej od elementu 8.
Znajdowanie elementu w uporządkowanym drzewie binarnym jest rów-
nie proste. W celu znalezienia elementu o wartości x rozpoczynamy przeszu-
kiwanie od korzenia drzewa i następnie postępujemy zgodnie z następującą
regułą: jeśli x jest mniejsze od wartości przechowywanej w węźle przechodzi-
my na lewo, a jeśli większe na prawo.
Warto podkreślić, że wszystkie operacje na drzewach najwygodniej jest
wykonywać przy pomocy procedur rekurencyjnych. Procedury iteracyjne są
znacznie dłuższe i mniej czytelne.
Na początku tego podrozdziału wspomniano, że wyszukiwanie w upo-
rządkowanym drzewie binarnym jest bardzo szybkie, jeżeli drzewo jest
wyważone. Drzewo jest wyważone wtedy, gdy dla każdego węzła wysokości
dwóch jego poddrzew różnią się co najwyżej o 1. Wysokością drzewa jest
maksymalny poziom wszystkich jego elementów. Natomiast poziom definiuje
się w sposób następujący: jeśli węzeł x znajduje się na poziomie n, a y jest
umieszczony pod węzłem x to węzeł x jest na poziomie n+1. Algorytmami
konstrukcji drzewa wyważonego nie będziemy się w tej książce zajmować
(zainteresowanego Czytelnika odsyłamy do pracy [22]). Zwróćmy tylko
uwagę, że utworzenie drzewa wyważonego jest bardzo istotne z punktu
widzenia szybkości wyszukiwania. Problem ten ilustruje rys. 12.22., na
którym są przedstawione dwa drzewa: jedno wyważone i drugie utworzone
w postaci liniowej. Widać od razu, że wyszukiwanie dowolnego elementu w
drzewie wyważonym odbywa się znacznie szybciej niż w drugim drzewie.
Rysunek można obejrzeć w książce
Drzewo można reprezentować na różne sposoby. My wykorzystamy
podobną strukturę jak dla list. Każdy węzeł będzie zawierał wskazanie na
lewe i prawe poddrzewo oraz wskazanie na obiekt z danymi. Strukturę
węzła przedstawia rys.12.23.
Rysunek można obejrzeć w książce
Dane wskazywane przez każdy węzeł drzewa będą tak jak dla stosu i
kolejki obiektami z klasy Osoba_ob. Definicji tej klasy nie będziemy w tej
chwili przytaczać, zostanie ona podana w treści programu ilustrującego
wykorzystanie drzew. Zakładamy że kluczem, według którego będziemy
porządkować elementy drzewa, jest pole nazwisko.
Drzewo będziemy reprezentować przy pomocy obiektu klasy Drzewo_ob.
Klasa ta ma postać:
type
wsk_wezel = ^wezel;
wezel = record
lewe, prawe: wsk_wezel;
zawartosc: wsk_dane
end;
Drzewo_ob = object
pierwszy: wsk_wezel;
constructor Init;
destructor Koniec(nazwa_pliku:string; var st:integer);
procedure Dodaj(wsk_akt: wsk_dane);
procedure Wczytaj;
procedure Druk_drzewo(k:integer);
procedure Wyszukaj;
procedure Usun;
procedure Ster(nazwa:string);
procedure Odczytaj(nazwa_pliku: string);
function Poprzedza(tekst1,tekst2: string): boolean;
end;
Klasa Drzewo_ob zawiera metody, które umożliwiają wykonywanie
następujących operacji:
- zainicjowanie drzewa (metoda Init)
- usunięcie drzewa z pamięci wraz z zapisaniem danych do pliku (metoda
Koniec)
- dodanie węzła do drzewa (metoda Dodaj)
- wczytywanie danych wraz z utworzeniem nowego węzła drzewa (metoda
Wczytaj)
- wydruk drzewa (metoda Druk_drzewo)
- wyszukanie elementu w drzewie (metoda Wyszukaj)
- usunięcie elementu drzewa oraz odczytanie danych z pliku wraz z utworze-
niem drzewa (metoda Usun)
- odczyt danych z pliku i utworzenie uporządkowanego drzewa (metoda
Odczytaj)
- sterowanie wykonywaniem operacji (metoda Ster)
- sprawdzanie kolejności tekstów ( metoda Poprzedza)
Zwróćmy uwagę, że zbiór operacji jest dokładnie taki sam jak dla klasy
Lista_ob. Wśród metod znajduje się też funkcja Poprzedza() analogiczna jak
zaprojektowana w metodzie Sortuj dla klasy Lista_ob. Funkcja ta jest umie-
szczona teraz wśród metod, ze wzgledu na jej ogólniejsze zastosowanie.
Obecnie omówimy kolejno wszystkie metody z klasy Drzewo_ob. Rozpo-
czniemy od metody Init oraz Koniec. Zadaniem metody Init jest nadanie
wartości początkowej polu pierwszy, które wskazuje korzeń drzewa. Zada-
niem metody Koniec jest usunięcie drzewa z pamięci wraz z zapisaniem
danych do pliku. Operacje te najwygodniej jest wykonać wykorzystując
rekurencję. Ponieważ w metodzie Koniec muszą się znaleźć pewne instruk-
cje, które powinny być wykonane tylko raz, wewnątrz metody Koniec umieś-
cimy wewnętrzną rekurencyjną procedurę Usun_element. Procedura ta
wykonuje wszystkie podstawowe operacje związane z zapisywaniem danych
do pliku i usuwaniem elementów drzewa z pamięci.
Algorytm wykorzystany w procedurze Usun_element jest następujący:
Algorytm 12.4.
jeśli węzeł istnieje to
{
jeśli lewe poddrzewo nie jest puste to
przejdź do lewego poddrzewa
jeśli prawe poddrzewo nie jest puste to
przejdź do prawego poddrzewa
usuń dane i węzeł
}
Treści metod Init oraz Koniec są podane poniżej.
constructor Drzewo_ob.Init;
{ Inicjalizacja drzewa }
begin
pierwszy := nil
end;
destructor Drzewo_ob.Koniec(nazwa_pliku:string; var st:integer);
{ Usuwanie drzewa z pamięci i zapamiętywanie danych na dysku }
procedure Usun_element(w_wezel: wsk_wezel);
{ Usuwanie jednego elementu drzewa }
begin
if w_wezel <> nil then
begin
if w_wezel^.lewe <> nil then
{ przejście do lewego poddrzewa }
Usun_element(w_wezel^.lewe);
if w_wezel^.prawe <> nil then
{ przejście do prawego poddrzewa }
Usun_element(w_wezel^.prawe);
if w_wezel^.zawartosc <> nil then
begin
{ zapis danych w pliku }
write(baza, w_wezel^.zawartosc^.dane);
{ usunięcie obiektu z danymi }
Dispose(w_wezel^.zawartosc, Koniec)
end;
{ usunięcie węzła drzewa }
Dispose(w_wezel)
end
end;
begin
assign(baza,nazwa_pliku); { przyporządkowanie nazwy do pliku }
rewrite(baza); { otworzenie pliku }
{ wywołanie procedury rekurencyjnej wykonującej
wszystkie operacje }
Usun_element(pierwszy);
close(baza); { zamknięcie pliku }
st := 0
end;
Przed omówieniem następnych metod przypomnimy treść funkcji
Poprzedza() doskonale już znanej Czytelnikowi. Funkcja ta obecnie występu-
je w postaci metody.
function Drzewo_ob.Poprzedza(tekst1,tekst2: string): boolean;
{ Sprawdzanie czy tekst tekst1 występuje przed tekstem tekst2 }
var
k,l1,l2,min: integer;
pom: boolean;
begin
k := 1;
l1 := length(tekst1);
l2 := length(tekst2);
{ wyznaczenie minimalnej długości }
min := l1;
if l2 < l1 then
min := l2;
while(upcase(tekst1[k]) = upcase(tekst2[k] )) and ( k <= min ) do
inc(k);
if k <= min then { jeśli nie wyszliśmy poza krótszy tekst }
poprzedza := upcase(tekst1[k]) < upcase(tekst2[k])
else { wyszliśmy poza krótszy tekst }
if (l1 > l2) or (l1 = l2) then
poprzedza := false
else
poprzedza := true
end;
Kolejną metodą jest metoda Dodaj. Jej zadaniem jest utworzenie nowego
węzła drzewa wraz z wprowadzeniem go na właściwe miejsce. Przypomnij-
my, że drzewo powinno być uporządkowane według pola nazwisko. Podobnie
jak w metodzie Koniec najwygodniej będzie wykorzystać rekurencję. Ponie-
waż metoda Dodaj nie może być zaprojektowana w wersji rekurencyjnej, w
jej treści zdefiniujemy dodatkową rekurencyjną procedurę o nazwie Buduj,
która będzie wykonywała wszystkie podstawowe operacje.
Algorytm wykorzystany w procedurze Buduj jest następujący:
Algorytm 12.5.
jeśli klucz nowego węzła jest mniejszy od klucza korzenia to
{
jeśli lewe poddrzewo jest puste to
wstaw nowy węzeł
w przeciwnym przypadku
wywołaj procedurę Buduj dla lewego poddrzewa
}
w przeciwnym przypadku
{
jeśli prawe poddrzewo jest puste to
wstaw nowy węzeł
w przeciwnym przypadku
wywołaj procedurę Buduj dla prawego poddrzewa
Zwróćmy uwagę, że zdanie
wywołaj procedurę Buduj dla lewego poddrzewa
realizujemy w następujący sposób:
Buduj(startowy^.lewe,nowy);
Dla fragmentu drzewa przedstawionego na rys. 12.24 (na rysunku tym w
poszczególnych węzłach wpisano tylko wartość klucza) jeżeli startowy
wskazuje na węzeł o kluczu Kowalski, to po wywołaniu procedury Buduj dla
lewego poddrzewa korzeniem w tym poddrzewie będzie węzeł o kluczu
Grzybowski.
Rysunek można obejrzeć w książce
Treść metody Dodaj jest podana poniżej.
procedure Drzewo_ob.Dodaj(wsk_akt:wsk_dane);
{ Dodawanie nowego węzła do drzewa,
wsk_akt zawiera wskazanie na obiekt z danymi }
var
w_wezel: wsk_wezel; { nowo utworzony węzeł }
procedure Buduj(startowy, nowy: wsk_wezel);
{ Wstawianie węzła nowy do drzewa, którego korzeniem
jest węzeł startowy }
begin
{jeśli węzeł nowy powinien być umieszczony na lewo}
if Poprzedza(nowy^.zawartosc^.dane.nazwisko,
startowy^.zawartosc^.dane.nazwisko ) then
begin
{ jeśli lewe poddrzewo jest puste }
if startowy^.lewe = nil then
begin
{ wstawienie nowego węzła }
startowy^.lewe := nowy
end
else { lewe poddrzewo nie jest puste }
{ wywołanie procedury Buduj dla lewego poddrzewa }
Buduj(startowy^.lewe,nowy)
end
else { nowy węzeł powinien być umieszczony na prawo }
begin
{ jeśli prawe poddrzewo jest puste }
if startowy^.prawe = nil then
begin
{ wstawienie nowego węzła }
startowy^.prawe := nowy
end
else { prawe poddrzewo nie jest puste }
{ wywołanie procedury Buduj dla prawego poddrzewa }
Buduj(startowy^.prawe,nowy)
end
end;
begin
New(w_wezel); { utworzenie nowego węzła }
w_wezel^.prawe := nil;
w_wezel^.lewe := nil;
{ ustawienie wskazania na obiekt z danymi }
w_wezel^.zawartosc := wsk_akt;
if pierwszy = nil then { jeśli drzewo jest puste }
pierwszy := w_wezel
else
Buduj(pierwszy,w_wezel)
end;
Następną metodą, którą omówimy, jest metoda Druk_drzewo umożliwia-
jąca wydrukowanie danych wskazywanych przez wszystkie węzły drzewa.
Wykorzystamy w niej wewnętrzną rekurencyjną procedurę o nazwie
Druk_d. Algorytm zastosowany w tej procedurze jest podany poniżej. Warto
zwrócić uwagę na rolę zmiennej licznik, której wykorzystanie pozwala na
wstrzymanie wydruku po dojściu do końca ekranu.
Algorytm 12.6.
jeśli węzeł istnieje to
{
jeśli lewe poddrzewo nie jest puste to
drukuj lewe poddrzewo
jeśli doszliśmy do końca strony to
{
wstrzymaj wydruk
ustaw zliczanie wydrukowanych wierszy od początku
}
drukuj dane przechowywane w węźle
zwiększ wartość licznika wydrukowanych wierszy
jeśli prawe poddrzewo nie jest puste to
drukuj prawe poddrzewo
}
A oto treść procedury Druk_drzewo:
procedure Drzewo_ob.Druk_drzewo(k:integer);
{ Drukowanie danych wskazywanych przez wszystkie węzły
drzewa }
var
licznik: integer; { licznik wydrukowanych wierszy }
procedure Druk_d(w_wezel: wsk_wezel);
begin
if w_wezel <> nil then
begin
{ jeśli lewe poddrzewo jest niepuste }
if w_wezel^.lewe <> nil then
{ wywołanie procedury Druk_d dla lewego poddrzewa }
Druk_d(w_wezel^.lewe);
if licznik > k then { jeśli koniec strony }
begin
licznik := 0;
readln;
ClrScr
end;
{ wydrukowanie danych przechowywanych w węźle w_węzeł }
with w_wezel^.zawartosc^ do Drukuj;
licznik := licznik + 1;
{ jeśli prawe poddrzewo jest niepuste }
if w_wezel^.prawe <> nil then
{ wywołanie procedury Druk_d dla prawego poddrzewa}
Druk_d(w_wezel^.prawe)
end
end;
begin
ClrScr;
if pierwszy = nil then
begin
writeln('Drzewo jest puste');
exit
end;
DrukRamka(1,1,79,3);
DrukRamka(1,1,79,24);
gotoxy(2,2); writeln('Wydruk drzewa:');
gotoxy(2,24); write(' Naciśnij klawisz Enter ');
window(2,4,78,23); { ustawienie okna do wydruku danych }
licznik := 0;
Druk_d(pierwszy);
readln;
window(1,1,80,25); { ustawienie okna na cały ekran }
ClrScr
end;
W klasie Drzewo_ob znajdują się dwie metody wczytywania danych z
pliku lub monitora. Metoda Odczytaj umożliwia odczyt danych z pliku i
utworzenie uporządkowanego drzewa binarnego. Natomiast metoda Wczytaj
pozwala na wczytanie danych z monitora, które następnie będą umieszczone
w jednym węźle drzewa. Treści tych metod są przedstawione poniżej.
procedure Drzewo_ob.Odczytaj(nazwa_pliku: string);
{ Odczytanie danych z pliku i utworzenie uporządkowanego
drzewa binarnego }
var
kolejne: dane_rek;
begin
assign(baza,nazwa_pliku); { przypisanie nazwy }
reset(baza); { otworzenie pliku }
repeat
read(baza,kolejne); {odczytanie jednego rekordu}
{ utworzenie obiektu z danymi i nowego węzła oraz
dodanie węzła do drzewa na właściwe miejsce }
Dodaj(New(wsk_dane,Init(kolejne)));
until eof(baza);
close(baza) { zamknięcie pliku }
end;
procedure Drzewo_ob.Wczytaj;
{ Wczytanie danych umieszczonych w jednym węźle drzewa }
var
kolejne: dane_rek;
begin
ClrScr;
writeln(' Wczytywanie danych do węzła drzewa ');
DrukRamka(1,2,80,2);
writeln; writeln;
{ wczytanie danych do rekordu kolejne }
with kolejne do
begin
writeln('Podaj nazwisko:');
readln(nazwisko); writeln;
writeln('Podaj imię:');
readln(imie); writeln;
writeln('Podaj adres:');
readln(adres); writeln
end;
{ utworzenie obiektu z danymi i nowego węzła oraz
dodanie do drzewa na właściwe miejsce }
Dodaj(New(wsk_dane,Init(kolejne)))
end;
W omawianej klasie znajduje się również metoda Wyszukaj umożliwiają-
ca wyszukanie w drzewie węzła wskazującego na żądane dane. Tak jak
poprzednio wyszukiwanie będziemy wykonywać przy pomocy wewnętrznej
procedury rekurencyjnej o nazwie Wyszuk. Obecnie podamy najpierw algo-
rytm wykorzystany w tej procedurze zapisany w pseudo-kodzie, a następnie
jej treść.
Algorytm 12.7.
jeśli drzewo nie jest puste to
jeśli jest to szukany węzeł o właściwym kluczu to
zapamiętaj wskazanie na znaleziony węzeł
w przeciwnym przypadku
jeśli szukany węzeł leży w prawym poddrzewie to
wyszukuj w prawym poddrzewie
w przeciwnym przypadku
wyszukuj w lewym poddrzewie
wyprowadź wskazanie na znaleziony węzeł
procedure Drzewo_ob.Wyszukaj;
{ Wyszukanie w drzewie węzła wskazującego na żądanego dane }
var
nazw: string[20];
w_wezel,wskaznik: wsk_wezel;
function Wyszuk(startowy:wsk_wezel; nazw:string): wsk_wezel;
{ Funkcja rekurencyjna organizująca wyszukiwanie }
begin
wskaznik := nil;
if startowy <> nil then
{ jeśli jest to szukany węzeł o właściwym kluczu}
if startowy^.zawartosc^.dane.nazwisko = nazw then
{ zapamiętanie wskazania na znaleziony węzeł }
wskaznik := startowy
else
{ jeśli szukany węzeł leży w prawym poddrzewie }
if Poprzedza(startowy^.zawartosc^.dane.nazwisko, nazw)
then
{ wyszukiwanie w prawym poddrzewie }
wskaznik := Wyszuk(startowy^.prawe, nazw)
else
{ wyszukiwanie w lewym poddrzewie }
wskaznik := Wyszuk(startowy^.lewe, nazw);
wyszuk := wskaznik
end;
begin
ClrScr;
writeln(' Wyszukiwanie osób z drzewa o podanym nazwisku.');
DrukRamka(1,2,80,2);
writeln; writeln;
writeln('Podaj nazwisko');
readln(nazw); writeln;
if pierwszy = nil then
begin
writeln('Drzewo jest puste');
readln;
exit
end;
w_wezel := Wyszuk(pierwszy,nazw);
if w_wezel <> nil then
begin
writeln('Znaleziono osobę o podanym nazwisku');
with w_wezel^.zawartosc^ do Drukuj;
end
else
writeln('Nie znaleziono osoby');
writeln; writeln('Naciśnij klawisz Enter');
readln;
ClrScr
end;
A teraz przystąpimy do zaprojektowania najtrudniejszej metody zdefi-
niowanej w klasie Drzewo_ob. Jest to metoda o nazwie Usun umożliwiająca
usunięcie wskazanego węzła. Podstawowa trudność polega na tym, że należy
usunąć węzeł nie naruszając pierwotnej struktury drzewa i zachowując
wszystkie niezbędne połączenia w drzewie.
Przy usuwaniu węzła należy wyróżnić trzy przypadki:
1) w drzewie nie ma węzła o podanym kluczu
2) węzeł o kluczu równym podanemu ma tylko jedno poddrzewo
3) węzeł o kluczu równym podanemu ma dwa poddrzewa
Dwa ostatnie przypadki zilustrujemy na rysunkach. Na rys. 12.25
przedstawiono drzewo binarne, w którym dla jasności klucze są podane w
postaci liczb.
Rozważmy najpierw sytuację, gdy chcemy usunąć węzeł o kluczu 15.
Węzeł ten posiada tylko jedno poddrzewo i w celu usunięcia tego węzła
wystarczy wykonać instrukcję:
startowy := w_wezel^.lewe;
gdzie startowy jest korzeniem aktualnie badanego drzewa, a w_wezeł jego
kopią. Instrukcja ta powoduje przeniesienie wskazania z węzła 11 do 15 na
węzeł 11 do 13. W procedurze są jeszcze podane instrukcje umożliwiające
usunięcie węzła w_wezeł wraz z danymi wskazywanymi przez ten węzeł.
Drzewo po usunięciu węzła 15 przedstawia rysunek 12.26.
Rysunek można obejrzeć w książce
W przypadku gdy dany węzeł posiada dwa poddrzewa sytuacja jest o
wiele bardziej skomplikowana. Usuwany węzeł trzeba czymś zastąpić, ale
wcale nie węzłem będącym korzeniem któregoś z podrzew. Otóż usuwany
węzeł należy zastąpić węzłem o największym kluczu w lewym poddrzewie
lub węzłem o najmniejszym kluczu w prawym poddrzewie. Skoncentrujmy
się na przypadku, gdy usuwany węzeł zastępujemy węzłem o największym
kluczu w lewym poddrzewie. Węzeł o największym kluczu w lewym poddrze-
wie leży w skrajnej prawej gałęzi na samym jej końcu. Koniec można rozpo-
znać w ten sposób, że węzeł końcowy posiada tylko jedno poddrzewo. Drzewo
z rys. 12.25 po usunięciu węzła 16 jest pokazane na rys. 12.27.
Zastanówmy się nad realizacją opisanego algorytmu. Po znalezieniu w
rekurencyjny sposób węzła, który trzeba usunąć, należy znaleźć węzeł skra-
jny w prawej gałęzi lewego poddrzewa. Jak to zrobić zastanowimy się za
chwilę, a teraz omówimy operacje, które należy wykonać. Otóż należy tylko
zamienić usuwany węzeł ze znalezionym węzłem skrajnym i za węzeł skraj-
ny podstawić korzeń jego lewego poddrzewa. Przy usuwaniu węzła 16 z
drzewa pokazanego na rys. 12.25 węzeł skrajny to 15, czyli za węzeł 16
należy podstawić 15 wraz ze wskazywanymi danymi, a za węzeł 15 węzeł
13. Algorytm ten przedstawiony poniżej realizuje rekurencyjna procedura
Usun_d.
Algorytm 12.8.
jeśli korzeń jest pusty to
w drzewie nie ma węzła o podanym kluczu
w przeciwnym przypadku
jeśli węzeł do usunięcia leży w lewym poddrzewie to
przejdź do lewego poddrzewa
w przeciwnym przypadku
jeśli węzeł do usunięcia leży w prawym poddrzewie to
przejdź do prawego poddrzewa
w przeciwnym przypadku
{
zrób kopię korzenia
jeśli prawe poddrzewo jest puste to
za korzeń przyjmij korzeń lewego poddrzewa
w przeciwnym przypadku
jeśli lewe poddrzewo jest puste to
za korzeń przyjmij korzeń prawego poddrzewa
w przeciwnym przypadku
wyznacz skrajny prawy węzeł w lewym poddrzewie i
zamień go z węzłem usuwanym oraz za skrajny
prawy węzeł podstaw korzeń jego lewego poddrzewa
usuń kopię węzła wraz ze wskazywanymi danymi
}
Wyznaczenie skrajnego prawego węzła w lewym poddrzewie zrealizuje-
my również w sposób rekurencyjny przy pomocy procedury Skrajne. Algo-
rytm zastosowany w tej procedurze polega na znalezieniu skrajnego węzła w
prawej gałęzi przy pomocy instrukcji:
if pomoc^.prawe <> nil then
Skrajne(pomoc^.prawe);
a następnie na wykonaniu operacji opisanych zamian.
A oto treść metody Usun.
procedure Drzewo_ob.Usun;
{ Usuwanie z drzewa węzła o podanym kluczu, kluczem jest nazwisko }
var
nazw: string[20];
w_wezel,pom,pom1,pom2: wsk_wezel;
procedure Usun_d(var startowy: wsk_wezel; nazw: string);
{ Wewnętrzna procedura organizująca usuwanie }
var
w_wezel: wsk_wezel;
procedure Skrajne(var pomoc: wsk_wezel);
{ Znajdowanie skrajnego prawego elementu lewego poddrzewa }
begin
if pomoc^.prawe <> nil then
{ przejście do prawego poddrzewa }
Skrajne(pomoc^.prawe)
else { skrajny prawy element }
begin
{ zamiana danych wskazywanych przez węzeł
usuwany i znaleziony skrajny }
w_wezel^.zawartosc^.dane :=
pomoc^.zawartosc^.dane;
{ zapisanie za węzeł usuwany węzła skrajnego }
w_wezel := pomoc;
{ zapisanie za węzeł skrajny korzenia jego
lewego poddrzewa }
pomoc := pomoc^.lewe
end
end;
begin
if startowy = nil then
writeln('W drzewie nie ma węzła o podanym kluczu')
else
{ jeśli węzeł do usunięcia leży w lewym
poddrzewie }
if Poprzedza(nazw,startowy^.zawartosc^.dane.
nazwisko) then
{ przejście do lewego poddrzewa }
Usun_d(startowy^.lewe, nazw)
else { jeśli węzeł leży w prawym poddrzewie }
if Poprzedza(startowy^.zawartosc^.dane.
nazwisko,nazw) then
{ przejście do prawego }
Usun_d(startowy^.prawe, nazw)
else { jest to węzeł do usunięcia }
begin
{ zrobienie kopii korzenia }
w_wezel := startowy;
{ jeśli prawe poddrzewo jest puste }
if w_wezel^.prawe = nil then
{ usunięcie węzła }
startowy := w_wezel^.lewe
else
{ jeśli lewe poddrzewo jest puste }
if w_wezel^.lewe = nil then
{ usunięcie węzła }
startowy := w_wezel^.prawe
else { istnieją oba poddrzewa }
{ wyznaczenie skrajnego prawego
węzła w lewym poddrzewie }
Skrajne(w_wezel^.lewe);
{usunięcie obiektu z danymi oraz węzła}
if w_wezel^.zawartosc <> nil then
Dispose(w_wezel^.zawartosc, Koniec);
writeln('Usunięto węzeł o podanym',
' kluczu');
dispose(w_wezel)
end
end;
begin
ClrScr;
writeln(' Usuwanie osób z drzewa o podanym nazwisku');
DrukRamka(1,2,80,2);
writeln; writeln;
writeln('Podaj nazwisko:');
readln(nazw);
if pierwszy = nil then
begin
writeln('Drzewo jest puste');
readln;
exit
end;
{ usunięcie węzła o kluczu nazw }
Usun_d(pierwszy,nazw);
writeln('Naciśnij klawisz Enter');
readln;
ClrScr
end;
Ostatnią metodą jest metoda Ster analogiczna do metody o tej samej
nazwie zdefiniowana w klasie Lista_ob. Treść tej metody dla kompletu
zamieszczono poniżej.
procedure Drzewo_ob.Ster(nazwa:string);
{ Sterowanie pracą programu }
var
k:integer;
Menu_sys: Menu1; info: SearchRec;
begin
Menu_sys.Init;
Menu_sys.Dodaj(30,10,'Dodaj ');
Menu_sys.Dodaj(30,11,'Wyszukaj');
Menu_sys.Dodaj(30,12,'Usun ');
Menu_sys.Dodaj(30,13,'Drukuj ');
Menu_sys.Dodaj(30,14,'Zakoncz ');
FindFirst(nazwa_pliku,Archive,info);
if DosError <> 18 then { jeśli plik istnieje }
Odczytaj(nazwa); { odczytanie zawartości pliku }
k := 1;
while k <> 0 do
begin
ClrScr;
writeln('Obsługa drzewa binarnego. Autor: Walczak');
writeln; writeln('Lista zapisywana jest w pliku: ', nazwa);
writeln;
writeln('Wybierz zadaną operację posługując się',
' strzałkami.');
writeln;
DrukRamka(28,9,39,15);
Menu_sys.Wybierz;
k := Menu_sys.Podaj;
case k of
1: Wczytaj;
2: Wyszukaj;
3: Usun;
4: Druk_drzewo(15);
5: Koniec(nazwa,k)
end
end
end;
Obecnie możemy już przystąpić do przedstawienia programu ilustrujące-
go wykorzystanie klasy Drzewo_ob. W programie tym deklarujemy obiekt
Drzewo_A, na którym można wykonywać wszystkie operacje określone w
klasie Drzewo_ob. Przypomnijmy, że sterowanie wykonaniem tych operacji
zapewnia metoda Ster.
program Drzewo;
{ Program operacje na drzewie binarnym }
uses Crt, Dos, men1;
type
wsk_wezel = ^wezel;
wsk_dane = ^dane_ob;
wezel = record
lewe, prawe: wsk_wezel;
zawartosc: wsk_dane
end;
Drzewo_ob = object
pierwszy: wsk_wezel;
constructor Init;
destructor Koniec(nazwa_pliku:string; var st:integer);
procedure Dodaj(wsk_akt: wsk_dane);
procedure Wczytaj;
procedure Druk_drzewo(k:integer);
procedure Wyszukaj;
procedure Usun;
procedure Ster(nazwa:string);
procedure Odczytaj(nazwa_pliku: string);
function Poprzedza(tekst1,tekst2: string): boolean;
end;
dane_rek = record
nazwisko,
imie,
adres:
string[20]
end;
Dane_ob = object
dane: dane_rek;
constructor Init(dane_akt: dane_rek);
destructor Koniec;
procedure Drukuj;
end;
var
drzewo_A: Drzewo_ob;
baza: file of dane_rek;
{ W tym miejscu powinny być zamieszczone treści metod:
Init
Koniec
Dodaj
Wczytaj
Druk_drzewo
Wyszukaj
Usun
Ster
Odczytaj
Poprzedza
Treści te zostały podane wyżej w tym rozdziale }
constructor Dane_ob.Init(dane_akt: dane_rek);
begin
dane := dane_akt
end;
destructor Dane_ob.Koniec;
begin
end;
procedure Dane_ob.Drukuj;
begin
with dane do
writeln(nazwisko:20,imie:15,adres:35)
end;
begin
Drzewo_A.Init;
Drzewo_A.Ster('b1')
end.