Temat 4

Question 1

Czym różnią się przejścia przez drzewo: wszerz, wgłąb, pre-order, post-order, in-order, best-first?

Answer 1

Przejście wszerz (BFS): Węzły na jednym poziomie
Przejście wgłąb (DFS): Wezły wzdłuż każdej gałęzi
Przejście pre-order (Przedorderowe): Obecny - Lewy- Prawy węzeł
Przejście post-order (Postorderowe): Lewy - Prawy- Obecny węzeł
Przejście in-order (Inorderowe): Lewy - Obecny - Prawy węzeł
Przejście best-first (Najlepsze pierwsze): Najbardziej obiecujący (wartosciowy)

Question 2

Jakim grafem jest drzewo?

Answer 2

Graf nieskierowany, spójny i acykliczny

Question 3

Jakie jest drzewo pełne, a jakie jest zupełne?

Answer 3

Pełne drzewo ma wszystkie liście na tym samym poziomie i do tego wszystkie nie liście mają dwoje dzieci.

Zupełne drzewo ma liście na ostatnim poziomie, które zaczynają się od lewej strony.

Question 4

Jak najszybciej zbudowac kopiec?

Answer 4

Najpierw należy dodać elementy do struktury, a potem zastosować heapify

Question 5

Czy drzewo jest strukturą danych, czy ADT?

Answer 5

Może być tym i tym, to zależy od kontekstu, jednakże kiedy chodzi nam o drzewo w kontekście grafu, to drzewo jest typem strukturalnym.