Przechodzenie drzewa

Przechodzenie drzewa
Ilustracja
Pre-order - jeden ze sposobów przechodzenia drzewa
Rodzajprzechodzenie
Struktura danychdrzewo

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

Niniejsze algorytmy rekurencyjne działają na drzewie binarnym:

  • Pre-order
Pre-order: F, B, A, D, C, E, G, I, H.
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: A, B, C, D, E, F, G, H, I.
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: A, C, E, D, B, H, I, G, F.
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

Sorted binary tree.svg

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

(1*(2-3))+(4+5)

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

Level-order: F, B, G, A, D, I, C, E, H.

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
 }

Media użyte na tej stronie

Sorted binary tree.svg
Sorted binary tree with first nine letters of alphabet, created with Graphviz neato
Sorted binary tree inorder.svg
Sorted binary tree with first nine letters of alphabet, showing inorder traversal
Sorted binary tree postorder.svg
Sorted binary tree with first nine letters of alphabet, showing post-order traversal
Sorted binary tree preorder.svg
Sorted binary tree with first nine letters of alphabet, showing pre-order traversal
Sorted binary tree breadth-first traversal.svg
Autor: Rory O'Kane, Licencja: CC0
Sorted binary tree with first nine letters of alphabet, showing breadth-first traversal