Na początek, jaka rekurencyjna procedura?
W przód jest prosto:

private void RecursiveSearch(TreeNode root, string text)
{
if (root.Text.Contains(text))
textBox1.AppendText(textBox1.Lines.Count()+1 + ": " +
root.Text + "\n");
for (int i = 0; i < root.Nodes.Count; i++)
RecursiveSearch(root.Nodes[i], text);
}

Tu trzeba by się ustawić na najniższym, ostatnim elemencie i iść w górę.

do góry

W dniu 21.04.2016 o 13:22, Borneq pisze:
> Na początek, jaka rekurencyjna procedura?

Po analizie wychodzi od razu procedura iteracyjna, i co ciekawe, bez
stosu (!)
Szukanie w tył:
ustawienie się na root->last->last->..->last
bierzemy jego indeks,
gdy ten indeks>0, przechodzmy do parent[index-1] i index--
gdy index=0, wtedy szukamy najbliższego parenta, dla którego linia
zawierająca
ten węzeł > 0 (= numer), i ustawiamy się na jego
node[numer-1]->last->last->..->last

Czyżby z powodu stosu szukanie iteracyjne w tył było łatwiejsze niż w
przód? A może coś przeoczyłem?

do góry

W dniu 21.04.2016 o 13:47, Borneq pisze:
> Czyżby z powodu stosu szukanie iteracyjne w tył było łatwiejsze niż w
> przód? A może coś przeoczyłem?

Może ten stos dawał to że przyśpieszał zamiast chodzenia najpierw w
kierunku korzenia a potem w kierunku liści?

do góry

On 21.04.2016 13:22, Borneq wrote:
> Na początek, jaka rekurencyjna procedura?
> W przód jest prosto:
>
> private void RecursiveSearch(TreeNode root, string text)
> {
> if (root.Text.Contains(text))
> textBox1.AppendText(textBox1.Lines.Count()+1 + ": " +
> root.Text + "\n");
> for (int i = 0; i < root.Nodes.Count; i++)
> RecursiveSearch(root.Nodes[i], text);
> }
>
> Tu trzeba by się ustawić na najniższym, ostatnim elemencie i iść w górę.


Po paru ostatnich wątkach mam wrażenie, jakbyś tracił zdolność
komunikacji:( Rozumiem, że opisanie problemu jest uciążliwe
i zajmie z 10-15 minut, ale nie pomijaj tego.

Nie wiem, co jest w drzewie, nie wiem, co jest wyszukiwanym obiektem,
nie wiem też, co rozumiesz przez w tył.

Pewnie bym się dowiedział, jakbym próbował rozszyfrować ten
kod i wczytał się w poprzedni wątek, ale... no bez jaj;]

pzdr
bartekltg

do góry

W dniu 21.04.2016 o 13:52, bartekltg pisze:
> Nie wiem, co jest w drzewie, nie wiem, co jest wyszukiwanym obiektem,
> nie wiem też, co rozumiesz przez w tył.

Drzewo to wizualne TreeView, w drzewie są napisy, wyszukać mam napisy.
W tył: normalnie szukając przechodzimy do następnych elementów, do
kolejnych gałęzi i podgałęzi, to zrobione, ale teraz mam szukać od
najniższej, ostatniej gałęzi w kierunku góry.
Wyobraźmy sobie drzewko rejestrów. Standardowy regedit gdy wciskamy F3
znajduje następne wystąpienie ciągu. Jednak nie działa tam Shift-F3
które mogło by szukać w tył, czyli znaleźć to wystąpienie, które
minęliśmy przy wyszukiwaniu.

do góry

On 21.04.2016 14:04, Borneq wrote:
> W dniu 21.04.2016 o 13:52, bartekltg pisze:
>> Nie wiem, co jest w drzewie, nie wiem, co jest wyszukiwanym obiektem,
>> nie wiem też, co rozumiesz przez w tył.
>
> Drzewo to wizualne TreeView, w drzewie są napisy, wyszukać mam napisy.
> W tył: normalnie szukając przechodzimy do następnych elementów, do
> kolejnych gałęzi i podgałęzi, to zrobione, ale teraz mam szukać od
> najniższej, ostatniej gałęzi w kierunku góry.
> Wyobraźmy sobie drzewko rejestrów. Standardowy regedit gdy wciskamy F3
> znajduje następne wystąpienie ciągu. Jednak nie działa tam Shift-F3
> które mogło by szukać w tył, czyli znaleźć to wystąpienie, które
> minęliśmy przy wyszukiwaniu.
>


Jak definiujesz kolejność w drzewie? Pre-order?

To odwrotnie wyjdzie, jeśli zrobisz przechodzenie
post-order, ale w ramach każdego wierzchołka listę
jego dzieci bedziesz przetwarzał od tyłu.



pzdr
bartekltg

do góry

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.

do góry

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

do góry

W dniu 22.04.2016 o 02:38, bartekltg pisze:
> Jakie opisanie problemu taka odpowiedź.
> Wręcz przeciwnie, podawałeś rekurencyjną wersję
> innego problemu jako wzorcową

Chciałem zacząć od standardowej rekurencyjnej procedury, potem przerobić
to na iteracyjną ze stosem a na koniec dodać wyskakiwanie i wskakiwanie.

do góry

On Friday, April 22, 2016 at 4:26:04 PM UTC+2, Borneq wrote:
> W dniu 22.04.2016 o 02:38, bartekltg pisze:
> > Jakie opisanie problemu taka odpowiedź.
> > Wręcz przeciwnie, podawałeś rekurencyjną wersję
> > innego problemu jako wzorcową
>
> Chciałem zacząć od standardowej rekurencyjnej procedury, potem przerobić
> to na iteracyjną ze stosem a na koniec dodać wyskakiwanie i wskakiwanie.

W QT nie stosowałem wyskakiwania i wskakiwania, używałem za to lowerBound i
upperBound.

Pozdrawiam

do góry