Przechodzenie drzewa

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

Sposoby przechodzenia drzewa binarnego[edytuj | edytuj kod]

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ż:

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Przykładowe drzewo binarne

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[edytuj | edytuj kod]

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.