c++ - AVL树:词典的实际使用

Question

我想使用AVL树结构作为字典下的基础。
我的课:

template <typename keyType, typename dataType>
class AVLTree
{
  class Node
  {
  public:
         keyType key;
         dataType data;
         short int balanceFactor;
         Node * left;
         Node * right;

         Node(const keyType & newKey, const dataType & newData) : key(newKey), data(newData), balanceFactor(0), left(NULL), right(NULL) {};
  };
  Node * Root;
***methods
void insert(AVLTree<keyType, dataType>::Node* & subtreeRoot,  const keyType & newKey, const dataType & newData); //insert new element
  void clear(AVLTree<keyType, dataType>::Node* & subtreeRoot); //clear whole tree
  void graph(AVLTree<keyType, dataType>::Node* const & subtreeRoot, int indent) const; //print tree
  void printDes(AVLTree<keyType, dataType>::Node* const & subtreeRoot) const; //print in descending order
  void printAsc(AVLTree<keyType, dataType>::Node* const & subtreeRoot) const; //print in ascending order
...
public:
  void search(const keyType & findKey) const;
...};

假设我有一个句子:

我喜欢绿草和绿树。

当我删除标点符号('。')并降低所有单词时，我得到:

我喜欢绿草和绿树

我想将每个单词放入AVL树的结构中，并将其打印为升序列表:

和-1

草-1

绿色-2

我-1

喜欢-1

树-1

其中第二个“参数”是出现的次数，即 绿色为2。

我已经将其作为单个链接列表的映射进行了处理，但是现在我想实现AVL树，我想知道下一步应该做什么。我计划使用几种方法(包括此方法)制作外部类COUNTER。我的点子:

遍历句子；如果单词(键)不存在(搜索方法返回通知-应该转换为 bool(boolean) 值？)，则将其添加到树中(插入方法)。

(如果已经存在)，增加第二个参数(在这种情况下，为 data )-如何？
如果尚未添加，请使用data = 1将其添加到树中。

因此，最后一个问题是:我的想法正确吗？如果是这样，那么如何增加模板的第二个参数呢？迭代器是解决方案吗？

编辑:
这是我使用单链接列表的实现，但是没有使用INFO:

template <typename key>
class counter {
sequence<key> list;
std::map<string, int> map;

public:
void add_word(key new_word) {
    list.insertEnd(new_word);

    auto iterator = map.find(new_word);
    if (iterator != map.end()) {
        iterator->second++;
    } else {
        map.insert({new_word, 1});
    }
}

我想知道它是否可行:

template <typename key, typename info>
class counter {
AVLTree<key, info> dict;
std::map<string, int> map;

public:
void add_word(key new_word) {
    dict.insert(new_word,1);

    auto iterator = map.find(new_word);
    if (iterator != map.end()) {
        iterator->second++;
    } else {
        map.insert({new_word, 1});
    }
}
...}

但我想它不会那样工作

Answer 1

因此，给定data是您要增加的值，并且它是某种整数类型，您可以简单地执行

++found_node->data; 

这是“增加模板的第二个参数”的意思吗？

请注意，您的代码示例中的 search方法不会返回任何内容。它可能应该向找到的节点(或 Node* / end-iterator)返回 nullptr或某些迭代器。

这对您有帮助吗？