Politechnika Świętokrzyska w Kielcach Wydział Elektrotechniki,
Automatyki i Informatyki
Laboratorium Podstaw Programowania 2
Lab. nr 9
Drzewa
Data wykonania Data oddania Ocena :
dwiczenia : sprawozdania :
14.05.2012 24.05.2012
1.Przemysław Wolski
1. Wstęp teoretyczny.
Drzewo - jest zbiorem T jednego lub więcej elementów nazywanych węzłami, takich że:
istnieje jeden wyróżniony węzeł, nazywany korzeniem drzewa, oraz
pozostałe węzły (z wyłączeniem korzenia) są podzielone na rozłącznych zbiorów T1, ...,
Tm, z których każdy jest drzewem. Drzewa T1, ..., Tm są nazywane poddrzewami korzenia.
Stopniem węzła - nazywamy liczbę jego poddrzew. Węzły o stopniu większym od zera
nazywamy węzłami wewnętrznymi, natomiast węzły o stopniu
równym zero węzłami zewnętrznymi lub liśćmi.
Poziom węzła - jest wielkością zdefiniowaną rekurencyjnie: korzeń ma poziom równy zero, a
poziom każdego innego węzła jest o jeden większy niż poziom
korzenia w najmniejszym zawierajÄ…cym go poddrzewie.
Las - jest zbiorem rozłącznych drzew. Jeśli z jakiegoś drzewa usuniemy korzeń, wówczas
powstanie las.
Drzewo uporządkowane - to drzewo, w którym kolejność występowania poddrzew jest
ważna nazywamy drzewem uporządkowanym lub drzewem płaskim.
Drzewo binarne - jest skończonym zbiorem węzłów, który albo jest pusty, albo składa się z
korzenia i dwóch rozłącznych drzew binarnych nazywanych
lewym i prawym poddrzewem korzenia. Drzewa binarne przedstawione na rysunkach sÄ…
różnymi drzewami
Drzewo przeszukiwań binarnych, zwane również drzewem poszukiwań binarnych (ang.
binary search tree - BST) jest drzewem binarnym, w którym wartości węzłów są
przechowywane w taki sposób, że spełniona jest następująca własność:
Niech  x będzie węzłem drzewa BST. Jeśli  y jest węzłem znajdującym sie w lewym
poddrzewie węzła  x , to wartość(y)<=wartość(x). Jeśli  y jest węzłem znajdującym
się w prawym poddrzewie węzła  x , to wartość(x)<=wartość(y).
2. Przebieg laboratorium.
Zadanie 1.
Napisz program, który realizuje następujące zadania na drzewie BST:
·ð wstawianie wÄ™zÅ‚a;
·ð usuwanie wÄ™zÅ‚a;
·ð usuwania wszystkich elementów drzewa;
·ð wypisywanie zawartoÅ›ci wÄ™złów drzewa  liniowo (przedrostkowo, wrostkowo,
przyrostkowo);
·ð wyÅ›wietlanie struktury drzewa;
·ð wyszukiwania wÄ™zÅ‚a o zadanym kluczu w drzewie.
Zadanie 2.
Napisz funkcje, która oblicza liczbę liści w drzewie.
function LiczbaLiści(d:Drzewo):integer;
Zadanie 3.
Napisz procedurę przekształcającą zadane drzewo w jego odbicie lustrzane.
procedure Lustro(d:Drzewo);
program lab9zad1;
uses crt;
type Zdefiniowanie typu.
wskaznik = ^element;
element = record
dana:integer;
left:wskaznik;
right:wskaznik;
end;
procedure add_node(var n:wskaznik; a:integer); Procedura dodajÄ…ca kolejne liczby do
begin drzewa, jeśli element jest mniejszy niż
if n=nil then poprzednik to liczba dodawana jest po
begin lewej stronie jeśli większy to po prawej.
new(n);
n^.dana:=a;
n^.left:=nil;
n^.right:=nil;
end
else
if a < n^.dana then add_node(n^.left,a) else
add_node(n^.right,a);
end;
procedure add_node2(var n:wskaznik; a:integer); Procedura działająca podobnie jak
begin procedura wyżej z tym wyjątkiem że liczby
if n=nil then mniejsze dodaje z prawej strony a większe
begin z lewej tworzÄ…c tym samym odbicie
new(n); lustrzane poprzedniego drzewa.
n^.dana:=a;
n^.left:=nil;
n^.right:=nil;
end
else
if a > n^.dana then add_node2(n^.left,a) else
add_node2(n^.right,a);
end;
procedure show(r:wskaznik; x,y,i:byte); Procedura pokazujÄ…ca na ekranie 1
begin drzewo.
 if r<>nil then
begin
gotoxy(x,y);
write(r^.dana);
show(r^.left, x-i, y+2,i div 2);
show(r^.right, x+i, y+2,i div 2);
end;
end;
procedure show2(r:wskaznik; x,y,i:byte); Procedura pokazujÄ…ca na ekranie 2 drzewo
begin (odbicie lustrzane).
if r<>nil then
begin
gotoxy(x,y);
write(r^.dana);
show2(r^.left, x-i, y+2,i div 2);
show2(r^.right, x+i, y+2,i div 2);
end;
end;
procedure inorder(r:wskaznik); Wypisanie na ekran zawartości węzłów w
begin sposób następujący:
if r<>nil then Odwiedz
lewe poddrzewo --> Odwiedz

begin korzeo --> Odwiedz
prawe poddrzewo
inorder(r^.left);
write(r^.dana:3);
inorder(r^.right);
end;
end;
procedure postorder(r:wskaznik); Wypisanie na ekran zawartości węzłów w
begin sposób następujący:
if r<>nil then Odwiedz
lewe poddrzewo --> Odwiedz

begin prawe poddrzewo --> Odwiedz
korzeo
postorder(r^.left);
postorder(r^.right);
write(r^.dana:3);
end;
end;
procedure preorder(r:wskaznik); Wypisanie na ekran zawartości węzłów w
begin sposób następujący:
if r<>nil then Odwiedz
korzeo --> Odwiedz
lewe
begin poddrzewo --> Odwiedz
prawe poddrzewo
write(r^.dana:3);
preorder(r^.left);
preorder(r^.right);
end;
end;
procedure delete_node(var r:wskaznik; a:integer); Procedura usuwajÄ…ca pojedynczy element
var tmp:wskaznik; drzewa.
 procedure del(var p:wskaznik);
begin
if p^.right <> nil then del(p^.right)
else
begin
tmp^.dana:=p^.dana;
tmp:=p;
p:=p^.left;
end;
end;
begin
if r=nil then writeln('Nie ma takiego elementu w
drzewie.') else
if a if a>r^.dana then delete_node(r^.right,a) else
begin
tmp:=r;
if tmp^.right=nil then r:=tmp^.left else
if tmp^.left=nil then r:=tmp^.right else
del(tmp^.left);
dispose(tmp);
end;
end;
procedure remove_tree(var r:wskaznik); Procedura usuwająca całe drzewo a także
begin jego odbicie.
if r<>nil then
begin
remove_tree(r^.right);
remove_tree(r^.left);
dispose(r);
end;
end;
function locate(r:wskaznik; x:integer):wskaznik; Procedura wyszukiwania węzła o
var found:boolean; zadanym kluczu w drzewie.
begin
found:=false;
while (r<>nil) and not found do
begin
if r^.dana=x then found:=true else
if r^.dana > x then r:=r^.left else r:=r^.right;
end;
locate:=r;
end;
Procedura licząca liście w drzewie
function policz_liscie(ws:wskaznik):integer;
(najprostszy sposób każdy inny jest bez
begin
sensu).
if ws=nil then policz_liscie:=0
else
if (ws^.right=nil) and (ws^.left=nil) then
policz_liscie:=1
else
policz_liscie:=policz_liscie(ws^.left)+policz_liscie(ws^.ri
ght);
end;
procedure glowny; Procedura "program glowny"
var
klawisz:byte;
wsk,wsk2:wskaznik; 2 wskazniki na 2 drzewa.
liczba:integer;
begin
wsk:=nil;
wsk2:=nil;
repeat
begin
clrscr;
textcolor(white);
writeln('1.Dodaj wezel');
writeln('2.Usun wezel');
writeln('3.Usun wszystko');
writeln('4.Pokaz Przedrostkowo');
writeln('5.Pokaz Wzrostkowo');
writeln('6.Pokaz Przyrostkowo');
writeln('7.Pokaz Strukture');
writeln('8.Pokaz Wezel');
writeln('9.Policz liscie drzewa');
writeln('10.Pokaz Strukture Odbita (lustro)');
writeln('0.Zakoncz');
writeln;
write('Twoj wybor: ');
read(klawisz);
if klawisz=1 then
begin
textcolor(yellow);
write('Wpisz liczbe: ');
textcolor(white);
read(liczba);
add_node(wsk,liczba);
add_node2(wsk2,liczba);
end;
if klawisz=2 then
begin
textcolor(yellow);
write('Wpisz liczbe: ');
textcolor(white);
read(liczba);
delete_node(wsk,liczba);
end;
if klawisz=3 then
begin
 remove_tree(wsk);
remove_tree(wsk2);
end;
if klawisz=4 then
begin
textcolor(yellow);
writeln('Przedrostkowo');
textcolor(white);
preorder(wsk);
readln;
end;
if klawisz=5 then
begin
textcolor(yellow);
writeln('Wzrostkowo');
textcolor(white);
inorder(wsk);
readln;
end;
if klawisz=6 then
begin
textcolor(yellow);
writeln('Przyrostkowo');
textcolor(white);
postorder(wsk);
readln;
end;
if klawisz=7 then
begin
textcolor(green);
show(wsk,50,10,4);
textcolor(white);
readln;
end;
if klawisz=8 then
begin
write('Podaj liczbe: ');
read(liczba);
locate(wsk,liczba);
readln;
end;
if klawisz=9 then
begin
textcolor(yellow);
write('Libcza lisci: ');
textcolor(white);
write(policz_liscie(wsk));
readln;
end;
if klawisz=0 then break;
readln;
end;
if klawisz=10 then
begin
textcolor(green);
show2(wsk2,50,10,4);
textcolor(white);
readln;
end;
until klawisz=0;
end;
begin Wywołanie programu głównego.
glowny;
readln;
end.
3. Wnioski.
Struktury drzewiaste można stosować do reprezentacji zbiorów elementów,
w których obowiązuje pewien rodzaj hierarchii. Drzewa BST, ze względu na
uporządkowanie ich węzłów, umożliwiają szybkie wyszukiwanie zawartych w nich informacji.
W tzw. pełnych drzewach, czyli w drzewach o strukturze zbliżonej do tej
jaką mają drzewa z rysunku objaśniającego działanie procedury usuwania, pesymistyczny
czas wyszukiwania elementu o zadanej wartości wynosi __ __ __ , gdzie
 n oznacza liczbę elementów w drzewie, a  lg logarytm przy podstawie dwa. Jeśli do
drzewa wstawiamy elementy o wartościach znajdujących się już w porządku
rosnącym lub malejącym, wówczas takie drzewo przyjmuje strukturę listy linowej i ma taki
sam czas wyszukiwania elementów jak ona. Wszystkie procedury i funkcje
rekurencyjne, które zostały na tym i poprzednim wykładzie zaprezentowane dają się
przekształcić do podprogramów iteracyjnych. Procedury i funkcje rekurencyjne
można stosować również do innych struktur danych niż drzewo, jak choćby do wcześniej już
przez nas poznanych list. Drzewa można reprezentować również za pomocą
tablic i taka reprezentacja zostanie przedstawiona w niedługim czasie.