-
Data: 2016-04-22 02:38:58
Temat: Re: Szukanie drzewka w tył
Od: bartekltg <b...@g...com> szukaj wiadomości tego autora
[ pokaż wszystkie nagłówki ]On 21.04.2016 14:58, Borneq wrote:
> W dniu 21.04.2016 o 14:36, bartekltg pisze:
>> To odwrotnie wyjdzie, jeśli zrobisz przechodzenie
>> post-order, ale w ramach każdego wierzchołka listę
>> jego dzieci bedziesz przetwarzał od tyłu.
>
> Aha, to wyjdzie rekurencja i teraz będę musiał to jakoś przerobić na
> iterację ze stosem. Potrzebna iteracja, aby móc za pomocą jednego return
> wyjść z szukania a tym bardziej wskoczyć w środek szukania.
Jakie opisanie problemu taka odpowiedź.
Wręcz przeciwnie, podawałeś rekurencyjną wersję
innego problemu jako wzorcową
Nie opisałeś tego w na początku, to skad mam wiedzieć.
Bez stosu też się to prosto implementuje, tylko zamiast
wyjścia z funkcji rekurencyjnej masz przejscie poziom wyzej.
Jedyny problem, to odpowiednie ustawienie indeksu na dziecko,
z którego właśnie wróciłeś.
Wyszukiwanie tego dziecka zmieni algorytm w kwadratowy,
więc odpada.
Pozostaje stos (co też pozbywa nas problemy czy
TreeNode ma wskażnik do ojca. Nie napisałeś.)
gdzie trzymamy też liczby "i" z kazdego poziomu.
Rozpoczęcie od zadanego TreeNode (bo chyba o to chodzi,
nie wyjaśniesz, nie opisujesz). To już wymaga znajomości
ojca. Przechodzisz w górę i wypełniasz stos.
Pesymistycznie jest to liniowe (na danym poziomie musisz
przeszukać listę dzieci, by znaleźć dziecko, które właśnie
opuściłeś) ale wykonywane tylko raz... ale jednak lepiej
byłoby trzymać ten stos zapamiętany.
BTW, to drzewo nie ma iteratora? Takiego ++ i --? :-)
pzdr
bartekltg
Następne wpisy z tego wątku
Najnowsze wątki z tej grupy
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
Najnowsze wątki
- 2024-12-31 Szukam: czujnik ruchu z możliwością zaączenia na stałe
- 2024-12-31 Warszawa => Solution Architect (Java background) <=
- 2024-12-31 Warszawa => Starszy Konsultant AWS <=
- 2024-12-31 Warszawa => International Freight Forwarder <=
- 2024-12-31 Odpowiedzialność w spółce z oo
- 2024-12-31 Warszawa => Spedytor Międzynarodowy <=
- 2024-12-31 Błonie => Analityk Systemów Informatycznych (TMS SPEED) <=
- 2024-12-31 Warszawa => Specjalista ds. bezpieczeństwa informacji i ciągłości
- 2024-12-31 8%
- 2024-12-31 Błonie => Administrator systemów <=
- 2024-12-31 Błonie => IT System Administrator <=
- 2024-12-31 Mińsk Mazowiecki => Area Sales Manager OZE <=
- 2024-12-31 Wrocław => Specjalista ds. Sprzedaży (transport drogowy) <=
- 2024-12-31 Warszawa => Helpdesk - I linia wsparcia <=
- 2024-12-31 kabelek - kynar ?