用cpp语言制作一个程序,要求写出完整的代码,该程序先读取一个单词,该单词以字母开头,包括字母数字的任意序列.然后程序检查该单词是否位于树中.如果是,就使用半张开技术,重新组织树,并给这一单词的出现次数加1.注意单词向根部移动时,需要改变所涉及节点的连接关系,而不是将信息从一个节点传给它的父结点,再传给它的祖父节点.如果没有在树中找到单词,就为该单词创建一个新的叶子节点,将其插入树中.处理完所有的单词后,对树进行中序遍历,计算所有节点的频率,再把这些频率计数加在一起并输出,作为树中单词个数和文件中单词个数的最后结果.
时间: 2023-01-11 17:55:36 浏览: 60
下面是使用 C++ 实现这个程序的代码示例:
```cpp
#include <iostream>
#include <string>
struct Node {
std::string word;
int count;
Node* left;
Node* right;
Node(std::string w) : word(w), count(1), left(nullptr), right(nullptr) {}
};
class Tree {
public:
Tree() : root_(nullptr) {}
~Tree() {
DestroyTree(root_);
}
void AddWord(std::string word) {
Node* node = FindNode(word);
if (node) {
// 单词已经在树中,使用半张开技术重新组织树
MoveToRoot(node);
++node->count;
} else {
// 单词不在树中,新建一个叶子节点插入树中
node = new Node(word);
InsertNode(node);
}
}
int GetTotalCount() {
int count = 0;
CalculateCount(root_, count);
return count;
}
private:
Node* root_;
void DestroyTree(Node* node) {
if (!node) return;
DestroyTree(node->left);
DestroyTree(node->right);
delete node;
}
Node* FindNode(std::string word) {
Node* node = root_;
while (node) {
if (word == node->word) return node;
if (word < node->word) {
node = node->left;
} else {
node = node->right;
}
}
return nullptr;
}
void MoveToRoot(Node* node) {
if (node == root_) return;
Node* parent = GetParent(node);
if (parent->left == node) {
parent->left = node->right;
} else {
parent->right = node->right;
}
node->right = root_;
root_ = node;
}
Node* GetParent(Node* node) {
if (node == root_) return nullptr;
Node* parent = root_;
while (parent) {
if (parent->left == node || parent->right == node) return parent;
if (node->word < parent->word) {
parent = parent->left;
} else {
parent = parent->right;
}
}
return nullptr;
}
void InsertNode(Node* node) {
if (!root_) {
root_ = node;
return;
}
Node* parent = root_;
while (true) {
if (node->word < parent->word) {
if (parent->left) {