CODEWITHSUNDEEP
c++loopsfor-looptree
user1587451
user1587451

Reputation: 1008

For-loop going down a tree

I have a k-ary tree stored in a std::vector called tree:

0,                          1,                          2
3,       4,       5         6,       7,       8         9,       10,      11
12,13,14 15,16,17 18,19,20  21,22,23 24,25,26 27,28,29  30,31,32 33,34,35 36,37,38

tree.size() == 39 as sketched above

I'm searching for a loop similar to following:

for (size_t i=0,j=tree.size(); i!=j; i=some_magic()) // <<---here
{
  std::cout << i << std::endl;
}

Which should output:

0
3
12
13
14
4
15
...

Upvotes: 0

Views: 93

Answers (1)

Pubby
Pubby

Reputation: 53017

For depth-first search you'll need a stack of some kind.

int child(int i, int c) { return (i+1)*3+c; }

int main()
{
    std::vector<int> parents = { 2, 1, 0 };
    while(!parents.empty())
    {
        int i = parents.back();
        parents.pop_back();
        std::cout << tree[i] << std::endl;
        for(int c = 0; c != 3; ++c)
        {
            if(child(i, 2-c) < tree.size())
                parents.push_back(child(i, 2-c));
        }
    }
}

Upvotes: 1

Related Questions