遍歷樹遍歷

我想弄清楚如何反向迭代，並通過這個或者至少調用一個方法來反向。遍歷樹遍歷

這是它是如何工作的。

小工具有一個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

回答

相關問題