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 Java 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 – referencja do lewego syna;

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

Klasą obiektu węzła będzie w naszej implementacji klasa Wezel. Do konstruktora klasy przekażemy tylko wartość klucza klucz typu int. Domyślnie pola lewy i prawy będą miały wartość null, co wskazuje na brak połączenia.

public class Wezel {
    int klucz;
    Wezel lewy, prawy;

    public Wezel(int klucz) {
        this.klucz = klucz;
        this.lewy = null;
        this.prawy = null;
    }
}

Wszystkie odwołania do obiektów w języku Java są referencjami i można ich używać jak wskaźników. Zatem w celu dodania pewnego węzła do drzewa binarnego, należy przypisać referencję do węzła, który chcemy dodać. Wykonujemy to w polu lewy lub prawy już istniejącego węzła.

public class DrzewoBinarne {
/* ... */
	public static void main(String[] args) {
		Wezel korzen = new Wezel(6);
		korzen.lewy = new Wezel(4);
		korzen.lewy.lewy = new Wezel(11);
		korzen.prawy = new Wezel(20);
		korzen.prawy.prawy = new Wezel(22);
	}
}

By zdefiniować drzewo binarne w kodzie, zwykle stosuje się jedną zmienną korzen będącą referencją do korzenia drzewa. Z tej zmiennej możemy się dostać do dowolnego węzła w drzewie binarnym poprzez ciąg odwołań do prawych i lewych synów.

Operacje będziemy wykonywać na referencjach obiektów klasy Wezel. Aby uzyskać dostęp do pól obiektu z poziomu referencji, używamy notacji kropkowej.

Wezel wezel = new Wezel(5);
System.out.println(wezel.klucz); // wynik = 5

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.

Implementacja drzewa binarnego zaprezentowanego na początku sekcji:

public class Wezel {
    int klucz;
    Wezel lewy, prawy;

    public Wezel(int klucz) {
        this.klucz = klucz;
        this.lewy = null;
        this.prawy = null;
    }

    public static void main(String[] args) {
		Wezel korzen = new Wezel(6);
		korzen.lewy = new Wezel(4);
		korzen.lewy.lewy = new Wezel(11);
		korzen.prawy = new Wezel(20);
		korzen.prawy.prawy = new 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