Przechodzenie drzewa

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

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ść
 }