遍历树遍历

我想弄清楚如何反向迭代，并通过这个或者至少调用一个方法来反向。遍历树遍历

这是它是如何工作的。

小工具有一个std :: vector的Widget *，它是那个控件的子元素。子向量是z排序的，这意味着子[0]在子[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];

我需要什么样的迭代才能有效地完成上述两种类型的迭代？（从前到后）。

感谢

来源

2010-10-15 jmasterx

我不知道我理解的问题下。这里没有链接列表;你有'std :: vector's，你可以在任何方向上迭代。 – 2010-10-15 23:36:09

@Oli查尔斯沃思但每个std :: vector有孩子，也有孩子，你不能访问某个孩子，而无需迭代父亲因此链表， – jmasterx 2010-10-15 23:37:42

我认为可能需要一些类型的递归，像while（children.size （）> 0） – jmasterx 2010-10-15 23:39:15

向前迭代：

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

（未经测试，但希望你的想法）。

来源

2010-10-15 23:41:44

但是，如果p有孩子，这些只做迭代，它将需要递归 – jmasterx 2010-10-15 23:43:37

@Milo：这些是递归的。 – 2010-10-15 23:44:26

反过来，在遍历子节点后，必须“do_something（）”。显示的结果是在后序。 – 2010-10-15 23:46:50

你真的在这里是一棵树，有秩序的孩子。如果我理解正确，你想用Depth First Search以相反顺序访问孩子来遍历它们。所以你只需要一些递归函数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如果在小部件是通过鼠标

来源

2010-10-15 23:56:00

这里不需要'unsigned'。这正是STL算法设计用于避免车轮重塑和随后的笨拙的原因...... – 2010-10-16 00:00:13

回答

相关问题