Przechodzenie drzew - in-order, pre-order, post-order

1. Czym jest przechodzenie drzewa?

Przechodzenie (traversal) to proces odwiedzenia wszystkich węzłów drzewa w określonej kolejności.

Po co to robić?

  • Wyświetlanie zawartości drzewa
  • Wyszukiwanie określonych wartości
  • Modyfikacja danych w węzłach
  • Serializacja drzewa (np. do JSON)
  • Obliczenia na drzewie (suma, wysokość, itp.)

2. Dwa główne podejścia

2.1. DFS (Depth-First Search) – Przeszukiwanie w głąb

Idź głęboko w drzewo przed przejściem do rodzeństwa.

Rodzaje DFS: - In-order (Lewo → Środek → Prawo) - Pre-order (Środek → Lewo → Prawo) - Post-order (Lewo → Prawo → Środek)

2.2. BFS (Breadth-First Search) – Przeszukiwanie wszerz

Odwiedź wszystkie węzły poziom po poziomie.

3. In-Order Traversal (LNR)

Kolejność: Lewo → Node (środek) → Prawo

3.1. Wizualizacja:

        10
       /  \
      5    15
     / \   / \
    3   7 12  20

In-order: Lewo → Node → Prawo

1. Idź w lewo: 10 → 5 → 3
2. Odwiedź 3 (liść)
3. Wróć do 5, odwiedź 5
4. Idź w prawo: 5 → 7
5. Odwiedź 7
6. Wróć do 10, odwiedź 10
7. Idź w prawo: 10 → 15 → 12
8. Odwiedź 12
9. Wróć do 15, odwiedź 15
10. Idź w prawo: 15 → 20
11. Odwiedź 20

Wynik: [3, 5, 7, 10, 12, 15, 20]

3.2. Implementacja rekurencyjna:

3.3. Implementacja iteracyjna (stos):

3.4. Zastosowania In-Order:

✅ BST → posortowana lista

✅ Walidacja BST

4. Pre-Order Traversal (NLR)

Kolejność: Node (środek) → Lewo → Prawo

4.1. Wizualizacja:

        10
       /  \
      5    15
     / \   / \
    3   7 12  20

Pre-order: Node → Lewo → Prawo

1. Odwiedź 10 (korzeń)
2. Idź w lewo: 10 → 5
3. Odwiedź 5
4. Idź w lewo: 5 → 3
5. Odwiedź 3
6. Wróć do 5, idź w prawo: 5 → 7
7. Odwiedź 7
8. Wróć do 10, idź w prawo: 10 → 15
9. Odwiedź 15
10. Idź w lewo: 15 → 12
11. Odwiedź 12
12. Wróć do 15, idź w prawo: 15 → 20
13. Odwiedź 20

Wynik: [10, 5, 3, 7, 15, 12, 20]

4.2. Implementacja rekurencyjna:

4.3. Implementacja iteracyjna (stos):

4.4. Zastosowania Pre-Order:

✅ Kopiowanie drzewa

✅ Serializacja drzewa

✅ Prefiks wyrażeń matematycznych

5. Post-Order Traversal (LRN)

Kolejność: Lewo → Prawo → Node (środek)

5.1. Wizualizacja:

        10
       /  \
      5    15
     / \   / \
    3   7 12  20

Post-order: Lewo → Prawo → Node

1. Idź w lewo: 10 → 5 → 3
2. Odwiedź 3 (liść)
3. Wróć do 5, idź w prawo: 5 → 7
4. Odwiedź 7
5. Wróć do 5, odwiedź 5 (dzieci gotowe)
6. Wróć do 10, idź w prawo: 10 → 15 → 12
7. Odwiedź 12
8. Wróć do 15, idź w prawo: 15 → 20
9. Odwiedź 20
10. Wróć do 15, odwiedź 15 (dzieci gotowe)
11. Wróć do 10, odwiedź 10 (dzieci gotowe)

Wynik: [3, 7, 5, 12, 20, 15, 10]

5.2. Implementacja rekurencyjna:

5.3. Implementacja iteracyjna (dwa stosy):

5.4. Implementacja iteracyjna (jeden stos):

5.5. Zastosowania Post-Order:

✅ Usuwanie drzewa

✅ Obliczanie wysokości

✅ Postfix wyrażeń matematycznych

✅ Obliczanie rozmiaru drzewa

6. Level-Order Traversal (BFS)

Kolejność: Poziom po poziomie (od lewej do prawej)

6.1. Wizualizacja:

        10        ← Poziom 0
       /  \
      5    15     ← Poziom 1
     / \   / \
    3   7 12  20  ← Poziom 2

Level-order: [10, 5, 15, 3, 7, 12, 20]

6.2. Implementacja (kolejka):

6.3. Level-order z poziomami:

6.4. Level-order poziom za razem:

6.5. Zastosowania Level-Order:

✅ Znajdowanie wysokości drzewa

✅ Znajdowanie węzła na określonym poziomie

✅ Szerokość drzewa (maximum width)

7. Porównanie metod przechodzenia

7.1. Wizualne porównanie:

        10
       /  \
      5    15
     / \   / \
    3   7 12  20

In-order:    [3, 5, 7, 10, 12, 15, 20]  ← Posortowane (BST)
Pre-order:   [10, 5, 3, 7, 15, 12, 20]  ← Korzeń pierwszy
Post-order:  [3, 7, 5, 12, 20, 15, 10]  ← Korzeń ostatni
Level-order: [10, 5, 15, 3, 7, 12, 20]  ← Poziom po poziomie

7.2. Tabelaryczne porównanie:

Metoda Kolejność Struktura danych BST → Sortowanie Zastosowania
In-order L → N → R Stos (rek./it.) TAK ✅ Sortowanie BST, walidacja
Pre-order N → L → R Stos NIE Kopiowanie, serializacja
Post-order L → R → N Stos NIE Usuwanie, obliczanie wysokości
Level-order Poziom po poziomie Kolejka (FIFO) NIE BFS, szerokość, poziomy

7.3. Złożoność:

Wszystkie metody: - Złożoność czasowa: O(n) – odwiedzamy każdy węzeł raz - Złożoność pamięciowa: - DFS (rekurencja): O(h) – wysokość drzewa (stos wywołań) - DFS (iteracja): O(h) – stos - BFS: O(w) – szerokość drzewa (kolejka)

8. Aplikacje praktyczne

8.1. Obliczanie wyrażeń matematycznych:

8.2. Walidacja BST:

8.3. Serializacja i deserializacja:

8.4. Znajdowanie ścieżki do węzła:

9. Morris Traversal (O(1) pamięci)

Morris Traversal umożliwia in-order bez stosu/rekurencji – tylko O(1) pamięci!

9.1. Idea:

Wykorzystaj prawe wskaźniki liści do tworzenia tymczasowych linków.

9.2. Implementacja (in-order):

Zalety: - O(1) pamięci (bez stosu/rekurencji)! ✅

Wady: - Bardziej skomplikowane - Modyfikuje drzewo (tymczasowo)

10. Podsumowanie

Przechodzenie drzew:

Metoda Kolejność Zastosowania Stos/Rekurencja
In-order L → N → R BST → sortowanie, walidacja TAK ✅
Pre-order N → L → R Kopiowanie, serializacja TAK ✅
Post-order L → R → N Usuwanie, wysokość, obliczenia TAK ✅
Metoda Kolejność Zastosowania Kolejka FIFO
Level-order Poziom po poziomie BFS, szerokość, poziomy TAK ✅

Złożoność: - Wszystkie metody: O(n) czas, O(h) lub O(w) pamięć - Morris Traversal: O(n) czas, O(1) pamięć ✅

Kluczowe obserwacje:

Wybór metody:

  • Sortowanie BST? → In-order
  • Kopiowanie/serializacja? → Pre-order
  • Usuwanie/obliczenia od liści? → Post-order
  • Przeszukiwanie poziomami? → Level-order (BFS)

Rekurencja vs Iteracja:

  • Rekurencja: Prostsza, czytelniejsza
  • Iteracja: Lepsza kontrola, unikanie przepełnienia stosu

Co dalej warto poznać:

  • Morris Traversal – O(1) pamięci dla in-order
  • Threaded Binary Trees – stałe linki do poprzednika/następnika
  • Zig-zag level order – level-order na przemian lewo-prawo
  • Vertical order traversal – przechodzenie pionowe
  • Boundary traversal – przechodzenie po obrzeżach drzewa
Wróć do spisu lekcji