Przeszukanie drzewa binarnego {grafy}

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
khaotic
Witam na forum
Witam na forum
Posty: 9
Rejestracja: 30 gru 2018, 13:24
Podziękowania: 4 razy

Przeszukanie drzewa binarnego {grafy}

Post autor: 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.

Obrazek

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.

Awatar użytkownika
lambdag
Czasem tu bywam
Czasem tu bywam
Posty: 106
Rejestracja: 18 paź 2017, 19:40
Podziękowania: 26 razy
Otrzymane podziękowania: 15 razy

Post autor: 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 ;).

khaotic
Witam na forum
Witam na forum
Posty: 9
Rejestracja: 30 gru 2018, 13:24
Podziękowania: 4 razy

Post autor: khaotic » 15 sty 2019, 20:19

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

Czy prawidłowa odpowiedź to 5.) ?