Drzewa

Drzewa

Drzewa to jedne z najważniejszych struktur danych w informatyce. Można je wykorzystać do wielu celów, min. do reprezentacji hierarchii, sortowania, itd.

Drzewo_informatyka.png

Każde drzewo składa się z wierzchołków (ang. Node), oraz łączących je krawędzi.
Każdy wierzchołek może posiadać wielu przodków i potomków. Potomkowie „bezpośredni” (B, C, D dla A) to dzieci wierzchołka, a przodek bezpośredni (B dla E i F) to ojciec (każdy wierzchołek ma dokładnie jednego ojca). Wierzchołki nie posiadające dzieci to liście. Wierzchołek na najwyższym poziomie to korzeń.
Drzewo może posiadać wiele dzieci, choć są drzewa o ich określonej liczbie, np. binarne.
Ścieżka to „droga’ między dwoma wierzchołkami, gdy poruszamy się po krawędziach, długość ścieżki to ilość jej krawędzi. Długość ścieżki od korzenia do wierzchołka na najniższym poziomie to wysokość drzewa.

Drzewo binarne

Istnieje wiele rodzajów drzew. Jednym z najbardziej znanych jest drzewo binarne. Posiada ono tą właściwość, że każdy węzeł może mieć maksymalnie 2 dzieci, (prawe i lewe ;))

CompleteBinaryTree_1000.gif

Implementacja strukturowa:

struct Node
{
int Dane;
Node * Left;
Node * Right;
};

Struktura Node zawiera jakąś zmienną przechowującą dane, tutaj jest to zmienna Dane typu Integer. Poza tym mamy również dwa wskaźniki do dzieci węzła, które są tego samego typu, co cała struktura (taki typ rekurencyjny).

Przechodzenie po drzewie binarnym.

Wyróżniamy 3 podstawowe metody:

INORDER
void Inorder(Node * Wsk)
{
if(Wsk)
{
Inorder(Wsk->Left);
cout « Wsk->Dane « endl;
Inorder(Wsk->Right);
}
}

Procedura Inorder potrzebuje argumentu – wskaźnika do węzła na którym mamy zamiar coś robić. Pierwszy warunek sprawdza, czy wskaźnik nie jest NULL, czyli czy tam gdzie się znaleźliśmy naprawdę jest wierzchołek. Jeśli tak, to najpierw funkcja wywołuje się na lewym synu, następnie są jakieś operacje na bieżącym węźle (tu – wypisanie danych) i na końcu funkcja wywołuje się na prawym synu.

PREORDER
void Inorder(Node * Wsk)
{
if(Wsk)
{
cout « Wsk->Dane « endl;
Preorder(Wsk->Left);
Preorder(Wsk->Right);
}
}

POSTORDER
void Inorder(Node * Wsk)
{
if(Wsk)
{
Postorder(Wsk->Left);
Postorder(Wsk->Right);
cout « Wsk->Dane « endl;
}
}

Gdybyśmy zmodyfikowali Postorder i Preorder, aby przegladały wszystkie, a nie tylko 2 dzieci wierzchołka i uruchomili na drzewie z pierwszego rysunku, to kolejność przejść byłaby dla:
Preorder: ABEFCDGIHJKL
Postorder: EFBCIGJKLHDA

Powyższe trzy procedury różnią się momentem, kiedy pracujemy na danych obecnego wierzchołka. W Inorder jest to pomiędzy wywołaniami na dzieciach, w Preorder jest to przed, a w Postorder po wywołaniach.

Alternatywny sposób reprezentacji drzew

Załóżmy, że potrzebne nam jest drzewo o nie dwóch, jak w binarnym, synach, ale o ilości (dużo) większej. Nie możemy na stałe ustawić wskaźników w strukturze, bo nie wiemy ile ich bęziemy potrzebować. Co wtedy zrobić?
Z pomocą przychodzi sposób, w którym do zapisu drzewa używamy 2 lub 3 tablic.
Pierwsza z nich to LMC[] (rozw. ang. Left Most Child), w której dla wierzchołka o indeksie i w LMC[i] będzie się znajdował numer wierzchołka, który jest jego najbardziej lewym synem (kwestie moralne pomijamy ;P).
Druga tablica to RS[] (rozw. ang. Right Sibling), w ktorej dla wierzchołka o indeksie i w RS[i] będzie się znajdował jego prawy brat.
Trzecią (opcjonalną) tablicą jest P[], w której będziemy przechowywać rodziców i-tego wierzchołka.

Dla naszego przykładowego drzewa (pierwszy rysunek) tablice wyglądałyby tak:

Węzeł A B C D E F G H I J K L
LMC B E - G - - I J - - - -
RS - C D - F - H - - K L -
P - A A A B B D D G H H H

Wczytywanie jest dosyć proste. Jeżeli mamy podawane na wejściu np. dzieci każdego z wierzchołków, to operacja przedstawia się następująco (pseudokod):

1. Dla każdego z podanych dzieci wykonuj:
1. 1. Jeżeli (LMC[current] == NIL) to LMC[current] = podany syn;
Jeżeli nie to
it = LMC[current];
Dopóki (RS[it] != NIL) it = RS[it];
RS[it] = podany syn;

1. 2. P[podany syn] = current;

current - numer badanego wierzcholka w tablicy
it - iterator do poruszania się po tablicy RS, braci wierzchołków

Zapis jest być może nieco chaotyczny. Chodzi głównie o to, że gdy mamy podane dzieci wierzchołka, to jeżeli LMC[] obecnego węzła jest puste, czyli nie ma jeszcze dzieci, to ustawiamy LMC[] na pierwszy z podanych synów. Gdy LMC[] jest już zajęte, to sprawdzamy brata tego, ktory zajmuje LMC[] i staramy się wpisaćna RS, pętla umożliwia dojście do najbardziej wysunietego na prawo syna.

obrazek 1: pl.wikipedia.org
obrazek 2: mathworld.wolfram.com

autor: kam1l

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License