Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #28507 > unrolled thread

Szukanie drzewka w tył

Back to article view | Back to pl.comp.programming

Contents

  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

#28507 — Szukanie drzewka w tył

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ę.

[toc] | [next] | [standalone]

#28508

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?

[toc] | [prev] | [next] | [standalone]

#28509

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?

[toc] | [prev] | [next] | [standalone]

#28510

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

[toc] | [prev] | [next] | [standalone]

#28511

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.

[toc] | [prev] | [next] | [standalone]

#28512

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

[toc] | [prev] | [next] | [standalone]

#28513

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.

[toc] | [prev] | [next] | [standalone]

#28515

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

[toc] | [prev] | [next] | [standalone]

#28516

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.

[toc] | [prev] | [next] | [standalone]

#28518

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

[toc] | [prev] | [standalone]

Back to top | Article view | pl.comp.programming

csiph-web