Przechodzenie drzewa

Przechodzenie drzewa (przechodzenie po drzewie) to w informatyce proces odwiedzania wszystkich węzłów drzewa.

Sposoby przechodzenia drzewa binarnego

Istnieje 6 sposobów przejścia drzewa binarnego: VLR, LVR, LRV, VRL, RVL, RLV, gdzie: Visit - "odwiedź" węzeł, Left - idź w lewo, Right - idź w prawo. Wyróżnia się 3 pierwsze:

• VLR - pre-order, przejście wzdłużne
• LVR - in-order, przejście poprzeczne
• LRV - post-order, przejście wsteczne

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)

Podane 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 potomków

• Pre-order

PRE-ORDER(wierzchołek_v)
 {
    wypisz wierzchołek_v.wartość
    dla każdego wierzchołka w będącego potomkiem wierzchołka_v:
        PRE-ORDER(w)
 }

• Post-order

POST-ORDER(wierzchołek_v)
 {    
    dla każdego wierzchołka w będącego potomkiem wierzchołka_v:
        POST-ORDER(w)
    wypisz wierzchołek_v.wartość
 }

• Nie istnieje algorytm In-order dla drzewa nie bę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

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). 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.