用cpp语言制作一个程序,要求写出完整的代码,该程序先读取一个单词,该单词以字母开头,包括字母数字的任意序列.然后程序检查该单词是否位于树中.如果是,就使用半张开技术,重新组织树,并给这一单词的出现次数加1.注意单词向根部移动时,需要改变所涉及节点的连接关系,而不是将信息从一个节点传给它的父结点,再传给它的祖父节点.如果没有在树中找到单词,就为该单词创建一个新的叶子节点,将其插入树中.处理完所有的单词后,对树进行中序遍历,计算所有节点的频率,再把这些频率计数加在一起并输出,作为树中单词个数和文件中单词个数的最后结果.

以下是一种用 C++ 实现这一程序的方法：

#include <iostream>
#include <string>
#include <unordered_map>

using namespace std;

struct Node {
  int count;
  string word;
  Node *left;
  Node *right;

  Node(string w) : count(1), word(w), left(nullptr), right(nullptr) {}
};

class WordTree {
 public:
  WordTree() : root_(nullptr) {}

  void Insert(string word) {
    if (root_ == nullptr) {
      root_ = new Node(word);
      return;
    }

    InsertHelper(root_, word);
  }

  void Print() {
    cout << "Word counts: " << endl;
    PrintHelper(root_);
  }

  int Count() {
    return CountHelper(root_);
  }

 private:
  void InsertHelper(Node *node, string word) {
    if (word == node->word) {
      // 如果找到了单词, 则使用半张开技术将其移动到树的根节点
      node->count++;
      Rebalance(node);
      return;
    }

    if (word < node->word) {
      if (node->left == nullptr) {
        node->left = new Node(word);
      } else {
        InsertHelper(node->left, word);
      }
    } else {
      if (node->right == nullptr) {
        node->right = new Node(word);
      } else {
        InsertHelper(node->right, word);
      }
    }
  }

  void Rebalance(Node *node) {
    while (node->left != nullptr) {
      // 将 node 的左子树提到树的根节点
      auto left = node->left;
      node->left = left->right;
      left->right = node;
      node = left;
    }
  }

  void PrintHelper(Node *node) {
    if (node == nullptr) {
      return;
    }
    PrintHelper(node->left);
    cout << node->word << ": " << node->count << endl;
    PrintHelper(node->right);
  }

  int CountHelper(Node *node) {
    if (node == nullptr) {
      return 0;
    }
    return node->count + CountHelper(node->left) + CountHelper(node->right);
  }

  Node *root_;
};

int main() {
  WordTree tree;

  string word;
  while (cin >> word) {
    tree.Insert(word);
  }

  tree.Print();
  cout << "Total word count: " << tree.Count() << endl;

  return 0;
}

上述代码实现了