Przechodzenie drzewa

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
 }