Pull to refresh

Обход дерева без рекурсии и без стека

Reading time 3 min
Views 28K
Придумал простой итератор для обхода произвольного дерева:
(для облегчения кода прежде всего)

struct Document<br/>{<br/>    Concept *root;<br/>    struct Iter<br/>    {<br/>        Concept *start;<br/>        Concept *cur;<br/>        Concept *bottom;<br/>    }iter;<br/> <br/>    Concept* Begin(Concept *c)<br/>    {<br/>        iter.start = c;<br/>        iter.cur = c;<br/>        iter.bottom =  0;<br/>        return Next();<br/>    }<br/>    Concept * Next()<br/>    {<br/>        if (!iter.cur) return  0;<br/> <br/>        while (iter.cur != iter.bottom && iter.cur->first_child)<br/>            iter.cur = iter.cur->first_child;<br/> <br/>        Concept *ret = iter.cur;<br/> <br/>        if (iter.cur == iter.start)<br/>            iter.cur =  0;<br/>        else if (iter.cur->next)<br/>            iter.cur = iter.cur->next;<br/>        else <br/>        {<br/>          iter.cur = iter.cur->parent;<br/>          iter.bottom = iter.cur;<br/>        }<br/>        return ret;<br/>    }<br/>};<br/> <br/>

Эта фича позволяет сильно облегчить код и делать так:
Concept *clicked = ConceptFromMouse();<br/>for (Concept *c = document->Begin(clicked); c; c=document->Next())<br/>{<br/>     DoSomething( c );<br/>} <br/>

Обходит дерево в таком же порядке как и такая рекурсия:
void DoSomethingHelper(root)<br/>{<br/>     for (Concept *c = root; c; c=c->next)<br/>     {<br/>          DoSomethingHelper(c->first_child);<br/>     }<br/>     DoSomething(root);<br/>}<br/> <br/>

Описание работы:


1. проваливаемся в самый низ по цепочке first_child->first->child->… (это самая левая ветка если картинку нарисовать)
2. запоминаю, что надо вернуть найденный элемент
3. переключаю итератор на следующий элемент, который верну при след. Next()
при этом, если поднимаюсь наверх — ставлю защиту от проваливания вниз в то же место — ставлю iter.bottom
(при этом если у него есть дети — то он опять провалится вниз, как и надо, при вызове Next())

Применение:


Это офигенно удобно, когда нужно сделать много разных действий с деревом в разных местах кода. Особенно, когда доступ к дереву нужен из других классов.
Если использовать способ с рекурсией — то придется писать кучу неудобных, некрасивых вспомогательных функций. А так — работа с деревом через простой итератор:

void DocumentEditor::OnDrag( Concept *con, float dx, float dy )<br/>{<br/>      // drag with childs<br/>      for (Concept *c = document->Begin(con); c; c=document->Next())<br/>      {<br/>           c->x += dx;<br/>           c->y += dy;<br/>      }<br/>} <br/>

UPD:
[14:26:11] Petrov: вот мне встречались такого типа алгоритмы про это:
www.perlmonks.org/?node_id=600456
Tags:
Hubs:
0
Comments 20
Comments Comments 20

Articles