Z Wikipedii

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

[edytuj] 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ść lewego syna n jest zawsze mniejsza od wartości n, a prawego syna zawsze większa od wartości n, inaczej: key(wierzchołek.lewy_syn) < key(wierzchołek) < key(wierzchołek.prawy_syn).

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

[edytuj] Sposoby przechodzenia drzewa o wielu dzieciach

Następujące algorytmy działają na ogólnym drzewie, którego każdy wierzchołek może mieć dowolnie wiele dzieci

• Pre-order

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

• Post-order

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

• Nie istnieje algorytm In-order dla drzewa nie będącego drzewem binarnym.

[edytuj] Przykład

W tym drzewie binarnym przechodzenie pre-order daje: F, B, A, D, C, E, G, I, H przechodzenie post-order daje: A, C, E, D, B, H, I, G, F przechodzenie in-order daje: A, B, C, D, E, F, G, H, I