Przechodzenie drzewa

Przechodzenie drzewa

Przechodzenie drzewa, znane również jako odwiedzanie wszystkich węzłów drzewa, odbywa się na różne sposoby. Metody te są szczególnie istotne w kontekście drzew binarnych oraz ogólnych drzew. W przypadku drzew binarnych wyróżnia się trzy podstawowe metody rekursywne:

Sposoby przechodzenia drzewa binarnego

• Pre-order (VLR): odwiedzenie węzła, następnie lewe poddrzewo, a potem prawe.
• In-order (LVR): odwiedzenie lewego poddrzewa, następnie węzła, a na końcu prawego poddrzewa. Przy drzewach poszukiwań binarnych skutkuje to posortowanymi wartościami.
• Post-order (LRV): odwiedzenie najpierw lewego i prawego poddrzewa, a na końcu węzła.

Algorytmy dla drzew binarnych są następujące:

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)
}

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)
}

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

Sposoby przechodzenia dowolnego drzewa

Dla ogólnych drzew, które mogą mieć dowolną liczbę synów, dostępne są następujące metody:

• Pre-order: odwiedzenie węzła, a następnie wszystkich jego synów.
• Post-order: odwiedzenie wszystkich synów, a na końcu węzła.
• In-order nie jest stosowane w drzewach ogólnych, ponieważ nie można zdefiniować lewego i prawego dziecka.

Przykłady przechodzenia drzewa binarnego

Na podstawie przykładowego drzewa binarnego, algorytmy odwiedzają węzły w następujący sposób:

• Pre-order: F, B, A, D, C, E, G, I, H
• In-order: A, B, C, D, E, F, G, H, I
• Post-order: A, C, E, D, B, H, I, G, F

Level-order

Metoda level-order polega na odwiedzaniu węzłów w kolejności wzrastającego poziomu zagłębienia, implementowana za pomocą algorytmu przeszukiwania wszerz (BFS).

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
}