Przeszukanie drzewa binarnego {grafy}

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij Thank icon

Przeszukanie drzewa binarnego {grafy}

Postprzez khaotic » 14 Sty 2019, 15:00

Na rysunku znajduje się drzewo binarne o v = 8 wierzchołkach i e = 7 krawędziach.
Przeprowadzamy procedurę przeszukania drzewa binarnego stosując algorytm przeszukiwania drzewa „w głąb” odwiedziając poszczególne wierzchołki i dokonując operacji dodawania wierzchołka na stos lub zdejmując element ze stosu. Po wykonaniu pierwszej operacji na stosie znajduje się korzeń λ, a po wykonaniu n = 16 operacji stos jest pusty.

Image

Podać która z odpowiedzi jest poprawna.
1)Po operacji 12 stos ma postać 5 3 1
2)Po operacji 9 stos ma postać 3 1
3)Po operacji 13 stos ma postać 3 1
4)Po operacji 8 stos ma postać 1
5)Po operacji 10 stos ma postać 7 5 3 1

Jakbym mógł jeszcze prosić o objaśnienie to będę super wdzięczny.
khaotic
Dopiero zaczynam
Dopiero zaczynam
 
Posty: 9
Dołączenie: 30 Gru 2018, 13:24
Otrzymane podziękowania: 0

Postprzez lambdag » 14 Sty 2019, 17:10

Przeanalizuj ten graf https://eduinf.waw.pl/inf/alg/001_search/0125.php a napewno ten też zrobisz sam ;).
Awatar użytkownika
lambdag
Stały bywalec
Stały bywalec
 
Posty: 106
Dołączenie: 18 Paź 2017, 19:40
Otrzymane podziękowania: 15

Postprzez khaotic » 15 Sty 2019, 20:19

Ok dzięki, trochę mi to rozjaśniło temat...

Czy prawidłowa odpowiedź to 5.) ?
khaotic
Dopiero zaczynam
Dopiero zaczynam
 
Posty: 9
Dołączenie: 30 Gru 2018, 13:24
Otrzymane podziękowania: 0


Powróć do Pomocy! - matematyka dyskretna



Kto jest na forum

Użytkownicy przeglądający to forum: Brak zarejestrowanych użytkowników oraz 1 gość