首页 文章

遍历包含两种类型值的BST

提问于
浏览 次
0

对于作业，我正在构建一个程序，将文本文档的单词加载到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函数，但是这给了我一个错误，说我正在传递一个"unresolved overloaded function type."供参考，这就是看起来像：

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

这显然是一个草率的解决方案，无论如何它都无法正常工作 . 我的问题是，有没有一种方法可以完成这项任务而无需创建一个全新的，非递归的inorder遍历函数？赋值来自遍历函数的原型，所以我试图找到是否有办法用提供的函数来完成它 .

tl; dr A BST拥有两种类型的数据成员，只按其中一种排序，如何使用其他成员进行搜索？

c++ binary-search-tree inorder

2 回答

  • 0

    我不确定你的BST解决的目的是什么 . BST将数据存储为键值对，其中树按键排序 . 如果需要搜索值，则必须遍历树或创建包含有关值的一些信息的新树，以便您可以使用BST结构快速获取所需信息 .

    另一个解决方案可能是 - 跟踪具有最大出现次数的节点（字数）最大值，同时添加新节点或更新现有节点，如果发现此节点的值超过之前的最大值，则只需需要更改跟踪对象/指针 .

    如果您的要求只是为了获得最大值的单词，那么您可以使用 Trie ，这将比BST更有效 .

    希望能帮助到你！

    回复于
  • 0

    更有帮助的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);});

    回复于

相关问题