Przechodzenie drzewa

Z Wikipedii, wolnej encyklopedii.

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

Sposoby przechodzenia drzewa binarnego

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.

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.

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.

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