Konstrukcja drzew binarnych

Wiemy, że dla w definicji pewnej klasy możemy zaimplementować dwa wskaźniki do obiektów tego samego typu. W ten sposób możemy stworzyć bardziej złożone struktury niż listy jednokierunkowe.

Dwukierunkowe listy tworzymy, gdy w obiekcie pewnej klasy zdefiniujemy wskaźnik do innego obiektu tego samego typu. Obiekty 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).

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

1. klucz – klucz węzła; przechowuje określoną wartość, np.  typu stałoprzecinkowego;

2. lewy – odnośnik do lewego syna;

3. prawy – odnoś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.

Konstruktor klasy przyjmuje tylko wartość klucza.

Domyślnie atrybuty lewy i prawy będą ustawione na None

W języku Python klasa Wezel będzie reprezentować węzeł drzewa.

Konstruktor klasy przyjmuje tylko tylko wartość klucza klucz typu int. Domyślnie atrybuty lewy i prawy będą ustawione na None.

class Wezel:
    def __init__(self, klucz):
        self.klucz = klucz
        self.lewy = None
        self.prawy = None

Aby dodać pewien węzeł do drzewa binarnego, należy w polu lewy lub prawy już istniejącego węzła przypisać referencję do węzła, który chcemy dodać.

korzen = Wezel(6)
korzen.lewy = Wezel(4)
korzen.lewy.lewy = Wezel(1)
korzen.prawy = Wezel(20)
korzen.prawy.prawy = Wezel(22)

W celu zdefiniowania drzewa w języku Python zwykle stosuje się jedną zmienną korzen będącą referencją do korzenia drzewa. Z poziomu tej zmiennej możemy się dostać do dowolnego węzła w drzewie binarnym poprzez ciąg odwołań do synów korzenia.

Operacje na obiektach klasy Wezel wykonujemy poprzez tworzenie instancji tej klasy. Dostęp do pól obiektu uzyskujemy używając notacji kropkowej.

wezel = Wezel(5)
print(wezel.klucz)

Aby stworzyć reprezentację drzewa, które zostało zaprezentowane na ilustracji na początku e‑materiału, użyjemy klasy Wezel, utworzymy jej instancje dla każdego węzła i przypiszemy im odpowiednio lewe i prawe poddrzewa.

class Wezel:
    def __init__(self, klucz):
        self.klucz = klucz
        self.lewy = None
        self.prawy = None

korzen = Wezel(6)
korzen.lewy = Wezel(4)
korzen.lewy.lewy = Wezel(1)
korzen.prawy = Wezel(20)
korzen.prawy.prawy = Wezel(22)

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