Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > pl.comp.programming > #28515
| From | bartekltg <bartekltg@gmail.com> |
|---|---|
| Newsgroups | pl.comp.programming |
| Subject | Re: Szukanie drzewka w tył |
| Date | 2016-04-22 02:38 +0200 |
| Organization | ATMAN - ATM S.A. |
| Message-ID | <nfbrr2$r8q$1@node1.news.atman.pl> (permalink) |
| References | <nfad6g$7b2$3@node2.news.atman.pl> <nfaeul$bj8$1@node1.news.atman.pl> <nfafl1$c8o$1@node1.news.atman.pl> <nfahgj$e8o$1@node1.news.atman.pl> <nfaipk$fgq$1@node1.news.atman.pl> |
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
Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Szukanie drzewka w tył Borneq <borneq@antyspam.hidden.pl> - 2016-04-21 13:22 +0200
Re: Szukanie drzewka w tył Borneq <borneq@antyspam.hidden.pl> - 2016-04-21 13:47 +0200
Re: Szukanie drzewka w tył Borneq <borneq@antyspam.hidden.pl> - 2016-04-21 13:52 +0200
Re: Szukanie drzewka w tył bartekltg <bartekltg@gmail.com> - 2016-04-21 13:52 +0200
Re: Szukanie drzewka w tył Borneq <borneq@antyspam.hidden.pl> - 2016-04-21 14:04 +0200
Re: Szukanie drzewka w tył bartekltg <bartekltg@gmail.com> - 2016-04-21 14:36 +0200
Re: Szukanie drzewka w tył Borneq <borneq@antyspam.hidden.pl> - 2016-04-21 14:58 +0200
Re: Szukanie drzewka w tył bartekltg <bartekltg@gmail.com> - 2016-04-22 02:38 +0200
Re: Szukanie drzewka w tył Borneq <borneq@antyspam.hidden.pl> - 2016-04-22 16:26 +0200
Re: Szukanie drzewka w tył "M.M." <mmarszik@gmail.com> - 2016-04-22 09:45 -0700
csiph-web