Przeczytaj

Konstrukcja drzew binarnych

Jak wiemy, obiekty ze wskaźnikiem do innego obiektu tego samego typu można łączyć w strukturę danych zwaną listą (zagadnienie to zostało omówione w e‑materiale Podstawowe struktury danych: listaPuhk7mD92Podstawowe struktury danych: lista).

Jeśli w klasie obiektu zdefiniujemy dwa wskaźniki do obiektów tego samego typu, to otrzymamy struktury bardziej złożone listy jednokierunkowelista jednokierunkowalisty jednokierunkowe.

W programowaniu w języku C++ drzewo poszukiwań binarnychdrzewo binarnedrzewo poszukiwań binarnych realizuje się jako strukturę danych z dowiązaniami, w której każdy węzeł jest obiektem o trzech polach:

klucz – klucz węzła; przechowuje określoną wartość, np. typu stałoprzecinkowego;
lewy – wskaźnik do lewego syna;
prawy – wskaźnik do prawego syna.

R164iPX4pQL8n

Ilustracja przedstawia dowiązania węzłów drzewa binarnego. Jest to graf, w którym wierzchołki zapisane są w kwadratach oraz posiadają w lewym dolnym rogu napis left i prawy dolnym rogu napis right. Korzeń drzewa (wierzchołek sześć) posiada dwa rozgałęzienia. Po lewej stronie łączy się z wierzchołkiem cztery. Po prawej stronie łączy się z wierzchołkiem dwadzieścia. Wierzchołek dwadzieścia posiada dwa rozgałęzienia, łączy się z wierzchołkami jedenaście oraz dwadzieścia dwa. — Konstrukcja drzewa binarnego
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Zdefiniujmy klasę Wezel. Będzie zawierała trzy pola:

klucz – klucz węzła; przechowuje określoną wartość typu int,
lewy – wskaźnik do lewego syna,
prawy – wskaźnik do prawego syna.

Zawierać będzie również jedną metodę – konstruktor.

Do konstruktora klasy przekażemy tylko wartość klucza klucz typu int. Domyślnie pola lewy i prawy będą wskazywać na nullptr, co w języku C++ jest odpowiednikiem słowa kluczowego NULL.

class Wezel  {
	public:
		int klucz;
		Wezel* lewy;
		Wezel* prawy;
    
		Wezel(int klucz) {
			this->klucz = klucz;
			this->lewy = nullptr;
			this->prawy = nullptr;
		}
};

Zauważmy, że pola są dostępne publicznie z dowolnego miejsca w kodzie. Nie jest to obecnie najlepsze rozwiązanie, ale ułatwi dalszą pracę.

Operacje będziemy wykonywać na wskaźnikach do klasy Wezel. Aby uzyskać dostęp do pól obiektu z poziomu wskaźnika, używamy notacji ze strzałką w prawo (->).

Wezel* wezel = new Wezel(5);
cout << wezel->klucz; // wynik = 5

Aby stworzyć reprezentację drzewa przedstawionego na zamieszczonym wyżej rysunku, użyjemy klasy Wezel, utworzymy jej instancje dla każdego węzła i przypiszemy im odpowiednio lewe i prawe poddrzewa.

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. class Wezel otwórz nawias klamrowy. Linia 4. public dwukropek. Linia 5. int klucz średnik. Linia 6. Wezel asterysk lewy średnik. Linia 7. Wezel asterysk prawy średnik. Linia 9. Wezel otwórz nawias okrągły int klucz zamknij nawias okrągły otwórz nawias klamrowy. Linia 10. this minus zamknij nawias ostrokątny klucz znak równości klucz średnik. Linia 11. this minus zamknij nawias ostrokątny lewy znak równości nullptr średnik. Linia 12. this minus zamknij nawias ostrokątny prawy znak równości nullptr średnik. Linia 13. zamknij nawias klamrowy. Linia 14. zamknij nawias klamrowy średnik. Linia 16. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. prawy ukośnik prawy ukośnik Tworzenie korzenia drzewa i pozostałych węzłów. Linia 18. Wezel asterysk korzen znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 20. prawy ukośnik prawy ukośnik Dodawanie lewego i prawego syna do korzenia. Linia 21. korzen minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 22. korzen minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 20 zamknij nawias okrągły średnik. Linia 24. prawy ukośnik prawy ukośnik Zakładając przecinek że na ilustracji węzeł cudzysłów 11 cudzysłów jest lewym synem węzła cudzysłów 4 cudzysłów przecinek. Linia 25. prawy ukośnik prawy ukośnik a węzeł cudzysłów 22 cudzysłów jest prawym synem węzła cudzysłów 20 cudzysłów. Linia 26. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 11 zamknij nawias okrągły średnik prawy ukośnik prawy ukośnik lewy syn węzła cudzysłów 4 cudzysłów. Linia 27. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 22 zamknij nawias okrągły średnik prawy ukośnik prawy ukośnik prawy syn węzła cudzysłów 20 cudzysłów. Linia 29. prawy ukośnik prawy ukośnik Drzewo jest teraz utworzone zgodnie z ilustracją. Linia 31. prawy ukośnik prawy ukośnik Tutaj można dodać kod do operacji na drzewie przecinek jak wyświetlanie przecinek dodawanie czy usuwanie węzłów. Linia 33. return 0 średnik. Linia 34. zamknij nawias klamrowy.

#include <iostream>

class Wezel {
public:
    int klucz;
    Wezel* lewy;
    Wezel* prawy;

    Wezel(int klucz) {
        this->klucz = klucz;
        this->lewy = nullptr;
        this->prawy = nullptr;
    }
};

int main() {
    // Tworzenie korzenia drzewa i pozostałych węzłów
    Wezel* korzen = new Wezel(6);

    // Dodawanie lewego i prawego syna do korzenia
    korzen->lewy = new Wezel(4);
    korzen->prawy = new Wezel(20);

    // Zakładając, że na ilustracji węzeł "11" jest lewym synem węzła "4",
    // a węzeł "22" jest prawym synem węzła "20"
    korzen->lewy->lewy = new Wezel(11); // lewy syn węzła "4"
    korzen->prawy->prawy = new Wezel(22); // prawy syn węzła "20"

    // Drzewo jest teraz utworzone zgodnie z ilustracją

    // Tutaj można dodać kod do operacji na drzewie, jak wyświetlanie, dodawanie czy usuwanie węzłów

    return 0;
}

W zaprezentowanym kodzie tworzymy nowe węzły i przypisujemy im odpowiednio wartości klucza. Przypisujemy także węzły lewy i prawy do każdego utworzonego węzła, aby odtworzyć strukturę drzewa z ilustracji.

Słownik

drzewo

struktura danych, którą reprezentuje drzewo matematyczne; występują w niej wierzchołki, krawędzie, liście i korzeń

drzewo binarne

drzewo ukorzenione, w którym każdy węzeł ma najwyżej dwóch synów

korzeń

węzeł (element) w drzewie, który nie ma żadnego ojca; pierwszy element drzewa

lista jednokierunkowa

dynamiczna struktura danych, która ma przechowywać nieznane z góry ilości danych tego samego typu; zbudowana jest z węzłów, z których każdy składa się z pojedynczego elementu przechowywanego w liście oraz wskaźnika do kolejnego elementu listy

liść

węzeł (element) w drzewie, który nie ma żadnych synów (potomków); często liśćmi są węzły najbardziej oddalone od korzenia

wyciek pamięci (ang. memory leak)

część programu, która wykorzystuje zarezerwowaną pamięć bez jej ostatecznego zwalniania

Wprowadzenie

Prezentacja multimedialna

Konstrukcja drzew binarnych

Słownik