Politechnika Świętokrzyska w Kielcach Wydział Elektrotechniki, Automatyki i Informatyki
Laboratorium Podstaw Programowania 2
Lab. nr 9
Data wykonania ćwiczenia : 14.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 wskaznik = ^element; element = record dana:integer; left:wskaznik; right:wskaznik; end; procedure add_node(var n:wskaznik; a:integer); begin if n=nil then begin 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); begin if n=nil then begin new(n); 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); begin 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); begin 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); begin if r<>nil then begin inorder(r^.left); write(r^.dana:3); inorder(r^.right); end; end; procedure postorder(r:wskaznik); begin if r<>nil then begin postorder(r^.left); postorder(r^.right); write(r^.dana:3); end; end; procedure preorder(r:wskaznik); begin if r<>nil then begin write(r^.dana:3); preorder(r^.left); preorder(r^.right); end; end; procedure delete_node(var r:wskaznik; a:integer); var tmp:wskaznik; 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<r^.dana then delete_node(r^.left,a) else 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); begin if r<>nil then begin remove_tree(r^.right); remove_tree(r^.left); dispose(r); end; end; function locate(r:wskaznik; x:integer):wskaznik; var found:boolean; 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; function policz_liscie(ws:wskaznik):integer; begin 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^.right); end; procedure glowny; var klawisz:byte; wsk,wsk2:wskaznik; 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 glowny; readln; end.

Zdefiniowanie typu. Procedura dodająca kolejne liczby do drzewa, jeśli element jest mniejszy niż poprzednik to liczba dodawana jest po lewej stronie jeśli większy to po prawej. Procedura działająca podobnie jak procedura wyżej z tym wyjątkiem że liczby mniejsze dodaje z prawej strony a większe z lewej tworząc tym samym odbicie lustrzane poprzedniego drzewa. Procedura pokazująca na ekranie 1 drzewo. Procedura pokazująca na ekranie 2 drzewo (odbicie lustrzane). Wypisanie na ekran zawartości węzłów w sposób następujący: Odwiedź lewe poddrzewo --> Odwiedź korzeń --> Odwiedź prawe poddrzewo Wypisanie na ekran zawartości węzłów w sposób następujący: Odwiedź lewe poddrzewo --> Odwiedź prawe poddrzewo --> Odwiedź korzeń Wypisanie na ekran zawartości węzłów w sposób następujący: Odwiedź korzeń --> Odwiedź lewe poddrzewo --> Odwiedź prawe poddrzewo Procedura usuwająca pojedynczy element drzewa. Procedura usuwająca całe drzewo a także jego odbicie. Procedura wyszukiwania węzła o zadanym kluczu w drzewie. Procedura licząca liście w drzewie (najprostszy sposób każdy inny jest bez sensu). Procedura "program glowny" 2 wskazniki na 2 drzewa. Wywołanie programu głównego.

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.