Przechodzenie drzewa
| ||
Pre-order - jeden ze sposobów przechodzenia drzewa | ||
Rodzaj | przechodzenie | |
---|---|---|
Struktura danych | drzewo |
Przechodzenie drzewa (pot. przechodzenie po drzewie) – proces odwiedzania wszystkich węzłów drzewa.
Sposoby przechodzenia drzewa binarnego
Wyróż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
Nastę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
W 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
in-order - notacja wrostkowa
(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
+ * 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)
1 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
Istnieje 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 }
Media użyte na tej stronie
Sorted binary tree with first nine letters of alphabet, created with Graphviz neato
Sorted binary tree with first nine letters of alphabet, showing inorder traversal
Sorted binary tree with first nine letters of alphabet, showing post-order traversal
Sorted binary tree with first nine letters of alphabet, showing pre-order traversal
Autor: Rory O'Kane, Licencja: CC0
Sorted binary tree with first nine letters of alphabet, showing breadth-first traversal