Вопрос о дизайне C ++ по обходу двоичных деревьев

Question

У меня есть двоичное дерево T, которое я хотел бы скопировать в другое дерево.

Предположим, у меня есть метод посещения, который оценивается на каждом узле:

struct visit 
{
 virtual void operator() (node* n)=0;

};

и у меня есть алгоритм посетителя

void visitor(node* t, visit& v)
{
//do a preorder traversal using stack or recursion
 if (!t) return;
 v(t);
 visitor(t->left, v);
 visitor(t->right, v);

}

У меня есть 2 вопроса:

1. Я остановился на использовании подхода, основанного на функторе, потому что я вижу, что граф повышения делает это (посетители вершин). Также я склонен повторять один и тот же код, чтобы пройтись по дереву и делать разные вещи на каждом узле. Это хороший дизайн, чтобы избавиться от дублированного кода? Какие еще есть альтернативные конструкции?
2. Как я могу использовать это для создания нового двоичного дерева из существующего? Я могу держать стек на Посетите функтор, если хотите, но он привязан к алгоритму в посетителе.
3. Как бы я включил здесь обходы после заказа? Еще один класс функторов?

Answer 1

3: создайте дополнительный метод для каждого типа обхода, который вы хотите выполнить, и переставьте вызовы посетителя:

void preorder_visitor(node* t, visit& v)
{
 if (!t) return;
 v(t);
 visitor(t->left, v);
 visitor(t->right, v);
}

void postorder_visitor(node* t, visit& v)
{
 if (!t) return;
 visitor(t->left, v);
 visitor(t->right, v);
 v(t);
}

Answer 2

1. Подкласс посетителя и предоставить разные посетители для каждой отдельной задачи, а также объединить похожие (или связанные) задачи в одного посетителя Лучший подход во многом зависит от того, что вы пытаетесь сделать.
2. Посетитель может построить другое дерево. Когда он посещает узлы, он создает новые копии узлов и связывает их в «правильном» порядке.
3. Вы переписываете порядок посещения узлов.

Посетитель - это техника. Похоже, вы перепутали технику с конкретным решением. Использование посетителя означает, что некоторые навигационные услуги предоставляются структурой данных, которая будет взаимодействовать с внешним объектом (посетителем) посредством обратного вызова.