Drzewo Binarne

Opis

Drzewo binarne jest to struktura danych, która pozwala na przechowywanie danych w pewnej hierarchii. Może zostać użyte nie tylko do przechowywania danych, ale również posortowania danych.

Słownictwo

Tak jak w prawdziwym w życiu drzewo binarne posiada swój pewien korzeń, gałęzie oraz liście. Drzewo Binarne jest szczególnym przypadkiem gdzie z dowolnego węzła mogą wychodzić maksymalnie dwie gałęzie. Od strony technicznej korzeń jest to wtedy punkt początkowy drzewa. Gałęzie to połączenie pomiędzy odpowiednimi węzłami. Łączą one rozgałęzienie z kolejnym rozgałęzieniem, albo z liśćmi. W tym przypadku liść jest pewną informacją zapisaną w drzewie. W celu uporządkowania drzewa traktujemy, że każde rozgałęzienie ma liście. Oto przykład drzewa binarnego w którym są przechowywane pewne liczby.

Drzewo jest wysokości h = 4. Zielone kółka nazywamy węzłami. Każdy węzeł może posiadać pewną wartość. Niekonicznie musi to być liczba. Pomiędzy dwoma dowolnymi węzłami prowadzi dokładnie jedna droga. Niektóre węzły mają dwie gałęzie, są takie co mają jedno, a jeszcze inni nie mają wogle.

Implementacja

Węzeł

W celu implementacji Drzewa Binarnego w programie należy utworzyć klase węzeł. Zgodnie z specyfiką Drzewa taki węzeł ma pewną wartość i może mieć dwóch potomków. Przypuśćmy, że program będzie przechowywać liczby całkowite tak jak na przykładzie.

1. class Wezel {
2. public:
3.   int wartosc;
4.   Wezel* lewy;
5.   Wezel* prawy;
7.   Wezel(int wartosc) {
8.     this->wartosc = wartosc;
9.     this->lewy = NULL;
10.     this->prawy = NULL;
11.   }
12. };

Nie jest to zalecane, ale na potrzeby przykładu wszystkie zmienne pozostają publiczne. Deklarowana (3.) jest zmienna do przechowywania pewnej wartości oraz wskaźniki (4.) na lewego i (5.) prawego potomka. (7. - 11.) W chwili tworzenia wskaźniki powinny wskazywać na NULL, ponieważ nie znamy węzła z którym się łączą.

Drzewo

Najprostsza implementacja drzewa może posiadać jedynie konstruktor. W konstruktorze wartość korzenia powinna zostać ustawiona na pustą. Będzie to oznacza, że drzewo jest puste. Dodatkowo zostanie dopisana funkcja czyPuste(), która zwróci czy drzewo jest puste.

1. class Drzewo {
2. public:
3.   Wezel* korzen;
4.   Drzewo() {
5.     korzen = NULL;
6.   }
8.   bool czyPuste() {
9.     return korzen == NULL;
10.   }
11. };

Drzewo jedyne co musi przechowywać to (3.) korzeń tj. główny węzeł, który jest najwyżej w hierarchii. Potem w konstruktorze (4. - 6.) korzeń deklaruje się na wartość NULL czyli korzeń nie ma żadnego potomka. Dodatkowa funkcja (8. - 10.) czyPuste() zwraca czy istnieje jakikolwiek potomek korzenia.

Testowanie funkcji

Poniższy kod przedstawia przykładowe wykorzystanie drzewa poprzez jego deklarację, a następnie dodaniu trzech potomków. Potem program wypisuje wartości węzłów.

1. int main() {
2.   Drzewo d;
3.   d.korzen = new Wezel(5);
4.   d.korzen->lewy = new Wezel(1);
5.   d.korzen->prawy = new Wezel(2);
6.   cout << "Wartość korzenia: " << d.korzen << endl;
7.   cout << "Lewy potomek korzenia: " << d.korzen << endl;
8.   cout << "prawy potomek korzenia: " << d.korzen << endl;
9.   system("pause");
10.   return 0;
11. }

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz wersję klasy, która pozwala zdefiniować jaki typ danych będzie przechowywany w klasie. Przetestuj działanie programu dla wybranego typu danych.

• Kod źródłowy Zadanie 1