Как не дублировать код для печати дерева
У меня есть функция, которая печатает узлы дерева слева направо.
void PrintTree()
{
...
Print(curentNode);
...
}
Но теперь я хочу добавить функцию, которая печатает узлы, соответствующие некоторому условию. Например, вывести только такие узлы, строки которых начинаются с заданной строки. Так это будет выглядеть
void PrintTreeByCondition(string a)
{
...
if (IsPrefix(a,curentNode->stringVar))
Print(curentNode);
...
}
Но тогда у меня есть две функции с одинаковым кодом, с разницей в одну строчку. Как мне избежать дублирования кода здесь?
UPD: Код траверса:
void BinTree::TraverseTree()
{
std::stack<TreeNode*> s;
s.push(root);
TreeNode* curentNode = s.top();
while (curentNode != nullptr|| s.empty() == false)
{
while (curentNode != nullptr)
{
s.push(curentNode);
curentNode = curentNode->GetLeft();
}
curentNode = s.top();
s.pop();
// do stuff
curentNode = curentNode->GetRight();
}
}
@PaulMcKenzie Я думал о чем-то подобном и решил использовать указатель на функцию, что-то вроде void TraverseTree(void (*f)(const CTreeNode*)) . Но после этого я не мог понять, как реализовать с ним второе поведение.
Хорошо, вы на правильном пути. Опубликуйте код обхода дерева (не функцию Print, а только код обхода).
@PaulMcKenzie добавил. Глядя на ответ, предоставленный Дитмаром Кюлем, я понимаю, что мне нужно добавить что-то вроде итераторов в мое дерево. Я могу сделать это, только добавив указатель на родителя узла в классе узла, верно?
UPD: понял, мои итераторы могут просто хранить стек, представляющий путь к корню, как я это делаю в своем обходе
Вы можете сделать что-то вроде этого: template <typename fn> void traverse( node *p, fn func) { if ( p ) {traverse(p->left, fn); fn(p); traverse(p->right, fn); }}, где fn — указатель на функцию, объект функции, лямбду и т. д. Это будет обход по порядку.
Но это не позволит моей лямбда-функции иметь другие параметры, верно? Как и в моем PrintTreeByCondition, у меня есть string a. Как мне реализовать что-то подобное с помощью лямбда-функции? Единственный способ, который я могу придумать, - это какая-то глобальная/статическая переменная, которая будет представлять string a, что, на мой взгляд, не лучшее решение.
Используйте объект, который operator() перегружен.
@IvanIvan: Предоставленный вами объект функции будет принимать аргументы, которые функция traverse() будет передавать ему для каждого узла. Например, если узлы вашего дерева содержат объекты T в качестве своего значения, функция, вероятно, примет T const& в качестве параметра. В зависимости от того, является ли функция traverse() шаблоном функции, она не будет принимать функцию посетителя либо в качестве параметра шаблона с [n подразумеваемой] концепцией возможности вызова с помощью T const&. Если это не шаблон, он, вероятно, примет std::function<void(T const&)> в качестве параметра.
Ответы 2
Способы С++ - создать итератор для обхода и использовать его для печати, а также для фильтрации или других целей. Обход дерева, вероятно, может быть выполнен в двунаправленном режиме, что позволит многим алгоритмам стать доступными и для дерева. На самом деле упорядоченные ассоциативные контейнеры (например, std::map, std::set) обычно реализуются как [сбалансированные] бинарные деревья, и их итераторы выполняют обход по порядку.
Детали итерации зависят от представления дерева. Ассоциативные контейнеры обычно реализуются с родительским указателем. Если такого указателя нет, каждый итератор должен будет поддерживать подходящее пространство для представления обратного пути к корню (контейнеры стандартной библиотеки не могут этого сделать, потому что у них есть требования к стабильности итератора, что предотвращает это). Немного странная вещь в обходе с использованием итераторов заключается в том, что она не поддается непосредственно реализации с использованием рекурсии. В свою очередь, контроль над итерацией передается пользователю итераторов.
Учитывая вашу функцию, другим подходом было бы заставить функцию TraverseTree принимать функцию для вызова после обнаружения узла:
template <typename fn>
void BinTree::TraverseTree(fn func)
{
std::stack<TreeNode*> s;
s.push(root);
TreeNode* curentNode = s.top();
while (curentNode != nullptr|| s.empty() == false)
{
while (curentNode != nullptr)
{
s.push(curentNode);
curentNode = curentNode->GetLeft();
}
curentNode = s.top();
s.pop();
func(currentNode); // call custom function
curentNode = curentNode->GetRight();
}
}
Тогда Print будет просто:
void Print(Node *n)
{
std::cout << n->data << "\n"; // assuming there is a "data" member
}
И последний звонок будет:
BinTree b;
//...
b.TraverseTree(&Print);
Если у вас есть другая информация для печати, передайте объект функции (класс с перегруженным operator()), а внутри объекта находится все необходимое для выполнения намеченной работы (обычно представленной в виде членов класса):
Например:
struct MyPrint
{
std::string some_value;
MyPrint(std::string s) : some_value(s) {}
void operator() (Node *n)
{
std::cout << some_value << " -- " << n->data << "\n";
}
};
Затем назовите это так:
BinTree b;
//...
MyPrint m("Testing testing");
b.TraverseTree(m);
Как не дублировать код для печати дерева. Как насчет кода, который обходит дерево в целом и вызывает функцию, предоставленную пользователем, при посещении узла? Это было бы намного лучше, общий подход. Что делать, если вы хотите сделать что-то с посещенным узлом, кроме как распечатать его? Давайте посмотрим код обхода.