Для задания я создаю программу, которая загружает слова текстового документа в BST, а также строки, в которых они встречаются в документе, поэтому узлы имеют два члена данных: строку (слово) и Очередь целых чисел (каждая строка, в которой встречается слово, с дубликатами). Класс BST также является классом-шаблоном. Для одной из частей задания мне нужно найти слово с максимальным количеством вхождений и распечатать его. Однако дерево сортируется по первому члену данных (строкам), поэтому я знаю, что поиск очереди с наибольшей длиной означает обход всего дерева. Определение частной функции обхода, которое было включено в незавершенное, имело следующую подпись:
BinarySearchTree<ItemType, OtherType>::Inorder(void visit(ItemType&, OtherType&), BinaryNode<ItemType, OtherType>* node_ptr) const
Итак, я сделал такие функции:
public:
template<class ItemType, class OtherType>
void BinarySearchTree<ItemType, OtherType>::InorderTraverse(void visit(ItemType&, OtherType&)) const
{
Inorder(visit, root_);
} // end inorderTraverse
private:
template<class ItemType, class OtherType>
void BinarySearchTree<ItemType, OtherType>::Inorder(void visit(ItemType&, OtherType&), BinaryNode<ItemType, OtherType>* node_ptr) const
{
if (node_ptr != nullptr)
{
Inorder(visit, node_ptr->GetLeftPtr());
ItemType item = node_ptr->GetItem();
OtherType other = node_ptr->GetOther();
visit(item, other);
Inorder(visit, node_ptr->GetRightPtr());
}
}
Таким образом, передается клиентская функция, которая может выполнять некоторые операции с данными-членами каждого узла. Однако я не могу придумать, как создать функцию, которая сравнивает элементы данных в каждом узле. Я попытался добавить два члена данных для хранения соответствующей информации и использовать функцию-член в классе BST и передать ее функции Inorder, но это дало мне ошибку, говорящую о том, что я передаю «неразрешенный тип перегруженной функции». Для справки, вот как это выглядит:
public:
template<class ItemType, class OtherType>
bool BinarySearchTree<ItemType, OtherType>::GetMaxOther(ItemType& theItem, OtherType& theOther)
{
if(root_ == nullptr)
return false;
InorderTraverse(MaxOtherHelper);
theItem = maxOtherItem;
theOther = maxOther;
return true;
}
private:
template<class ItemType, class OtherType>
void BinarySearchTree<ItemType, OtherType>::MaxOtherHelper(ItemType& theItem, OtherType& theOther)
{
if(theOther.Length() > maxOther.Length())
{
maxOther = theOther;
maxOtherItem = theItem;
}
}
Это явно небрежное решение, и оно все равно не работает. Мой вопрос в том, есть ли способ выполнить эту задачу без создания совершенно новой, нерекурсивной функции обхода? Назначение пришло с прототипом функции обхода, поэтому я пытаюсь выяснить, есть ли способ сделать это с помощью предоставленной функции.
tl; dr BST содержит два типа членов данных, сортируется только по одному из них, как мне искать, используя другие?