遍历一棵树

Question

我试图找出如何反向迭代并向前迭代，或者至少反向调用一个方法。

这是它的工作原理。

小部件有一个 Widget* 的 std::vector，它们是该控件的子控件。子向量按 z 顺序排列，这意味着 child[0] 位于 child[1] 之后（按渲染顺序）。每个控件都有一个指向其父控件的指针，但根（虚拟）控件除外，其父控件为 NULL。

对于我的渲染，我需要进行阶梯式迭代（从后到前）例如：

root->child[0];
root->child[0]->child[0];
root->child[0]->child[1];
root->child[1];
root->child[1]->child[0];
root->child[1]->child[1];

但是要找到鼠标下方的小部件，我必须从前到后进行矩形测试中的点：

   root->child[9]->child[1];
    root->child[9]->child[0];
    root->child[9];
    root->child[8]->child[2];
    root->child[8]->child[1];
    root->child[8]->child[0];
    root->child[8];

什么样的迭代会我需要有效地进行上述两种类型的迭代吗？ （从后到前，从前到后）。

谢谢

Answer 1

正向迭代：

void blah_forward(const Widget *p)
{
    p->do_something();
    std::for_each(p->children.begin(), p->children.end(), blah_forward);
}

反向迭代：（

void blah_reverse(const Widget *p)
{
    std::for_each(p->children.rbegin(), p->children.rend(), blah_reverse);
    p->do_something();
}

未经测试，但希望您明白）。

Answer 2

这里真正拥有的是一棵树，里面有有序的孩子。如果我理解正确的话，你想使用深度优先搜索访问孩子们来遍历它们以相反的顺序。因此，您只需要一些递归函数 widgetUnderMouse(Widget*) ，它按照您想要的顺序遍历树并检查当前小部件是否位于鼠标下方。我想是这样的。

Widget* widgetUnderMouse(Widget* root)
{
    if (root->hasChildren) 
    {
        vector<Widget*>::reverse_iterator rit;
        for (rit = root->child.rbegin(); rit < root->child.rend(); ++rit)
        {
            if (isWidgetUnderMouse(*rit)
            {
                return widgetUnderMouse(*rit);
            }
        }
    }
    else
    {
        return root;
    }
}

如果传入的小部件位于鼠标下方，则 isWidgetUnderMouse 返回 true 或 false