Итерация по дереву

Question

Я пытаюсь выяснить, как я могу выполнить итерацию в обратном порядке и пересылать через это, или, по крайней мере, вызвать метод в обратном порядке.

Вот как это работает.

Виджеты имеютstd :: vector Widget *, которые являются потомками этого элемента управления.Дочерний вектор имеет порядок z, что означает, что child [0] находится позади child [1] (в порядке рендеринга).Каждый элемент управления имеет указатель на своего родителя, за исключением корневого (фиктивного) виджета, чей родитель имеет значение NULL.

Для моего рендеринга мне нужно что-то вроде ступенчатой ​​итерации (задом наперед), например:1007 *

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];

Какую итерацию мне нужно выполнить эффективновышеуказанные 2 типа итераций?(спереди назад, спереди назад).

Спасибо

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, если переданный в виджет находится под мышью