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
[edytuj | edytuj kod]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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d4/Sorted_binary_tree_preorder.svg/260px-Sorted_binary_tree_preorder.svg.png)
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/77/Sorted_binary_tree_inorder.svg/260px-Sorted_binary_tree_inorder.svg.png)
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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9d/Sorted_binary_tree_postorder.svg/260px-Sorted_binary_tree_postorder.svg.png)
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
[edytuj | edytuj kod]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
[edytuj | edytuj kod]![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/67/Sorted_binary_tree.svg/260px-Sorted_binary_tree.svg.png)
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
[edytuj | edytuj kod]in-order - notacja wrostkowa
[edytuj | edytuj kod](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 | edytuj kod]+ * 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)
[edytuj | edytuj kod]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
[edytuj | edytuj kod]![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d1/Sorted_binary_tree_breadth-first_traversal.svg/220px-Sorted_binary_tree_breadth-first_traversal.svg.png)
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 }