For循环下树

Question

我有一个 k-ary 树存储在一个名为 tree 的 std::vector 中：

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 如上草图

我正在搜索类似于以下内容的循环：

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

应该输出：

Answer 1

对于深度优先搜索，您需要某种堆栈。

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));
        }
    }
}

For循环下树

For-loop going down a tree

c++

tree

loops

for-loop