我有一个 struct element
,其中包括有关树元素的信息。
struct element
{
char ch; //Letter
int left; //Number in array
int right; //Number in arry
int count; //Count letter in word
};
另外,我还有一个函数 MakeAlphabet
,它为 std::string
生成一个字母表:std::vector<element> MakeAlphabet(std::string str) //РАБОТАЕТ!
{
std::vector<element> alphabet;
ranges::sort(str);
for(auto ch : str | ranges::views::unique)
{
alphabet.push_back(element{ch, -1, -1, static_cast<int>(ranges::count(str, ch))});
}
return alphabet;
};
最后,我有一个函数 MakeBinaryTree
:std::vector<element> MakeBinaryTree(std::string str)
{
std::vector<element> result;
std::vector<element> alphabet = MakeAlphabet(str);
std::sort(alphabet.begin(), alphabet.end());
result = alphabet;
int size = alphabet.size();
result = alphabet;
for(int i = 0; i < size; i+=2) //I think problem is here!
{
alphabet.push_back(element{-1, i, i+1, (alphabet[i].count + alphabet[i+1].count)});
alphabet.erase(alphabet.begin(), alphabet.begin() + 1);
result.push_back(*(alphabet.end()-1));
}
return result;
};
在检查结果树的根时(它必须与单词中的字母数匹配),结果几乎总是不正确的。升级版:
我有
std::sort(alphabet.begin(), alphabet.end());
的重载运算符.bool operator<(const element &first, const element &second)
{
return (first.count < second.count);
}
bool operator==(const element &first, const element &second)
{
return (first.count == second.count);
}
最佳答案
必须对数组进行排序,将出现次数最少的两个节点组成一个新节点,该新节点放回数组中。数组再次排序,依此类推......
因此它只有一个数组,即字母表
使用指向元素 (element*) 的指针而不是仅使用元素,因为很容易将它们从数组切换到树。
创建节点类
class node{
};
class inner_node: public node
{
node *left, *right;
int count; //Count letter in word
};
class element: public node
{
public:
char ch; //Letter
int count; //Count letter in word
};
std::vector<node*> MakeAlphabet(std::string str) //РАБОТАЕТ!
{
std::vector<node*> alphabet;
ranges::sort(str);
for(auto ch : str | ranges::views::unique)
{
element *e = new element();
e->ch = ch;
e->static_cast<int>(ranges::count(str, ch));
alphabet.push_back(e);
}
return alphabet;
}
std::vector<node*> MakeBinaryTree(std::string str)
{
std::vector<node*> alphabet = MakeAlphabet(str);
// keep going until there is only the huffman tree root left in the vector
while(alphabet.size() > 1)
{
std::sort(alphabet.begin(), alphabet.end());
// Takes last two elements and remove them
inner_node *first = (inner_node*) alphabet.back();
alphabet.pop_back();
inner_node *second = (inner_node*) alphabet.back();
alphabet.pop_back();
// Creates tree node and put in the vector
inner_node *n = new node();
n->left = first;
n->right = second;
n->count = first->count + second->count;
alphabet.push_back(n);
}
return alphabet;
}
关于c++ - 无法编写用于构建霍夫曼树的函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/61442902/