时间戳

首页 > 解决方案 > 无法编写用于构建霍夫曼树的函数

c++ - 无法编写用于构建霍夫曼树的函数

问题描述

我有一个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;
};

在检查结果树的根时（它必须与单词中的字母数匹配），结果几乎总是不正确的。

UPD：我有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);
}

标签： c++algorithmbinary-treehuffman-code

解决方案

必须对数组进行排序，将出现次数最少的两个节点组成一个新节点，然后将其放回数组中。数组再次排序等等......因此它只是一个数组，即字母表

使用指向元素（元素*）的指针而不是仅元素，因为很容易将它们从数组切换到树。

创建节点类

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

推荐阅读