Przechodzenie drzewa
Przechodzenie drzewa (pot. przechodzenie po drzewie) – proces odwiedzania wszystkich węzłów drzewa.
Pre-order - jeden ze sposobów przechodzenia drzewa | |
Rodzaj |
przechodzenie |
---|---|
Struktura danych |
drzewo |
Sposoby przechodzenia drzewa binarnego
edytujWyróżnia się 3 sposoby rekursywnego przejścia drzewa binarnego:
- VLR – pre-order, przejście wzdłużne,
- LVR – in-order, przejście poprzeczne,
- LRV – post-order, przejście wsteczne,
gdzie: Visit – „odwiedź” węzeł, Left – przejdź lewe poddrzewo, Right – przejdź prawe poddrzewo.
W przypadku gdy dane drzewo jest binarnym drzewem AST przejścia określa się również:
- pre-order – prefiksowym, gdyż wynik odwiedzania poszczególnych węzłów jest trawestacją wyrażenia zawartego w strukturze AST do postaci przedrostkowej (notacji Łukasiewicza),
- in-order – infiksowym, gdyż trawestuje wyrażenie do postaci wrostkowej,
- post-order – postfiksowym, gdyż trawestuje wyrażenie do postaci przyrostkowej (odwrotnej notacji polskiej).
Niniejsze algorytmy rekurencyjne działają na drzewie binarnym:
- Pre-order
PRE-ORDER(wierzchołek_v) { wypisz wierzchołek_v.wartość jeżeli wierzchołek_v.lewy_syn != null to PRE-ORDER(wierzchołek_v.lewy_syn) jeżeli wierzchołek_v.prawy_syn != null to PRE-ORDER(wierzchołek_v.prawy_syn) }
Działanie jest wykonywane najpierw na rodzicu, następnie na synach.
- In-order
IN-ORDER(wierzchołek_v) { jeżeli wierzchołek_v.lewy_syn != null to IN-ORDER(wierzchołek_v.lewy_syn) wypisz wierzchołek_v.wartość jeżeli wierzchołek_v.prawy_syn != null to IN-ORDER(wierzchołek_v.prawy_syn) }
Najpierw wykonywane jest działanie na jednym z synów, następnie na rodzicu i na końcu na drugim synu. Przechodząc w ten sposób drzewo poszukiwań binarnych, otrzymuje się posortowane wartości wszystkich węzłów. Dzieje się tak dlatego, że w drzewie poszukiwań binarnych wartości lewego syna węzła n oraz wszystkich jego potomków są mniejsze od wartości n, a wartości prawego syna i jego potomków większe od wartości n.
- Post-order
POST-ORDER(wierzchołek_v) { jeżeli wierzchołek_v.lewy_syn != null to POST-ORDER(wierzchołek_v.lewy_syn) jeżeli wierzchołek_v.prawy_syn != null to POST-ORDER(wierzchołek_v.prawy_syn) wypisz wierzchołek_v.wartość }
Działanie jest wykonywane najpierw na wszystkich synach, na końcu na rodzicu.
Sposoby przechodzenia dowolnego drzewa
edytujNastępujące algorytmy działają na ogólnym drzewie, którego każdy wierzchołek może mieć dowolnie wiele synów:
- Pre-order
PRE-ORDER(wierzchołek_v) { wypisz wierzchołek_v.wartość dla każdego wierzchołka w będącego synem wierzchołka_v: PRE-ORDER(w) }
- Post-order
POST-ORDER(wierzchołek_v) { dla każdego wierzchołka w będącego synem wierzchołka_v: POST-ORDER(w) wypisz wierzchołek_v.wartość }
- Nie istnieje algorytm In-order dla drzewa niebędącego drzewem binarnym. Porządek in-order wymaga odwiedzenia węzła–rodzica po lewym a przed prawym dzieckiem. W drzewie nie binarnym, tj. gdy węzły mogą mieć więcej niż 2 potomków, nie da się jednoznacznie zdefiniować dziecka lewego i prawego (np. przy 3 węzłach–dzieciach (potomkach) będzie przynajmniej 2 dzieci lewych albo 2 dzieci prawych), stąd zasadnicza niemożność spełnienia tego porządku.
Przykład
edytujW tym drzewie binarnym podstawowe algorytmy odwiedzają węzły w następującej kolejności:
- pre-order: F, B, A, D, C, E, G, I, H
- post-order: A, C, E, D, B, H, I, G, F
- in-order: A, B, C, D, E, F, G, H, I
Przykład przejścia binarnego drzewa AST opisującego wyrażenie arytmetyczne
edytujin-order - notacja wrostkowa
edytuj(1*(2-3))+(4+5)
Notacja wrostkowa wymaga nawiasów do zdefiniowania kolejności wykonywania operacji.
Część nawiasów z powyższego zapisu może zostać opuszczona bez uszczerbku dla wyniku wyrażenia arytmetycznego. Jednak po usunięciu nadmiarowych (z punktu widzenia poprawności wyniku) nawiasów zapis przestanie być wzajemnie jednoznaczny z przytoczonym drzewem.
Konkretniej: z przytoczonego drzewa wynika, że operacja +(4,5) powinna zostać wykonana przed + z korzenia. Po opuszczeniu nawiasów powstałaby dowolność w kolejności wykonywania + i z zapisu bez 'nadmiarowych' nawiasów byłoby możliwe wyprowadznie więcej niż jednego drzewa. Inaczej: z łączności dodawania wynika, że na drzewie składniowym dopuszczalne są obroty operacji + względem siebie.
pre-order - notacja polska
edytuj+ * 1 - 2 3 + 4 5
lub nawiązując do języków programowania:
plus(razy(1,minus(2,3)),plus(4,5))
post-order - odwrotna notacja polska (RPN)
edytuj1 2 3 - * 4 5 + +
W latach 70. kalkulatory RPN były popularne w kręgach finansowych. Obliczenia z wykorzystaniem RPN używają stosu. Współcześnie powyższe wyrażenie może zostać wykonane przy pomocy kalkulatora dc.
$ dc
1 2 3 - * 4 5 + +
p
8
Komenda p zwraca wartość na wierzchołku stosu, czyli w tym przypadku ostateczny wynik wyrażenia.
Levelorder
edytujIstnieje również metoda przechodzenia levelorder, która polega na odwiedzaniu wierzchołków kolejno według wzrastającego poziomu zagłębienia. Jest ona implementowana przy użyciu algorytmu przeszukiwania wszerz (BFS), np. z wykorzystaniem kolejki. W przykładowym drzewie powyżej metoda ta odwiedza węzły w kolejności:
- level-order: F, B, G, A, D, I, C, E, H.
LEVEL-ORDER(wierzchołek_v) { utwórz kolejkę wierzchołków k wstaw wierzchołek_v do kolejki dopóki kolejka nie jest pusta: pobierz z kolejki wierzchołek w wypisz wierzchołek_w.wartość dla każdego wierzchołka u będącego potomkiem wierzchołka w: wstaw wierzchołek u do kolejki }