对于分配,我正在构建一个程序,该程序将文本文档的单词加载到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 a bst持有两种类型的数据成员,仅由其中一个分类,我如何使用其他数据成员进行搜索?
我不确定您的BST解决了什么用途。BST将数据存储为钥匙值对,其中树由密钥排序。如果您需要搜索一个值,则必须穿越树或制作一个新的树,其中包含有关该值的一些信息,以便您可以使用BST结构快速获取所需信息。
另一个解决方案可能是 - 跟踪具有最大出现(单词计数)的节点,同时添加新节点或更新现有节点,如果您发现该节点的值超过了先前的max的值然后,您只需要更改跟踪对象/指针。
如果您的要求仅仅是为了获得最大出现的单词,则可以使用 trie ,它比BST更有效。
希望它有帮助!
更有帮助的InorderTraverse签名
您有MaxOtherHelper
的编译错误的原因是它具有类型 void(BinarySearchTree<I, O>::*)(I&, O&)
而不是void(I&, O&)
。如果我们实现InorderTraverse
作为以下
template<class ItemType, class OtherType>
void BinarySearchTree<ItemType, OtherType>::InorderTraverse(std::function<void(ItemType&, OtherType&)> visit, 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());
}
}
这使我们可以在visit
上具有更大的灵活性,具体来说,我们可以使用std::bind
或使用lambda传递成员功能并访问this
,例如InorderTraverse([this](ItemType & item, OtherType & other){MaxOtherHelper(item, other);});