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