Создать дерево кода Хаффмана из min-heap C++

Question

Скажем, у вас есть программа на С ++, которая должна читать текст из заданного .txt-файла. Программа будет:

• вычислить число появлений каждого полукокса в файле, то каждый уникального полукокс (и его частоту) будет сохранена в качестве нового узла дерева
• Затем программа строит мин-кучу, содержащую эти узлы, то Дерево кодов Хаффмана строится с использованием этой мини-кучи.
• Переходы (предварительный заказ и порядок) будут записаны в выходной файл. Каждый внутренний узел дерева будет иметь метку I: xxx, где xxx - это метка int, а листья имеют L: xxx
• Программа, наконец, создает таблицу, содержащую кодировку (на основе ASCII, а не true .bin version) каждого символ хранится в виде строки

Я полагаю, я бы хранить каждый узел в пределах HUFFMAN класса, как это:

struct CharNode { 

     char value; 
     int frequency; 
     bool internal; 
     int label; 
     CharNode *parent; 
     CharNode *left_child; 
     CharNode *right_child; 
}; 

Я точно не знаю, куда двигаться. Любая помощь приветствуется!

Answer 1

Начните с использования массива, который достаточно длинный, чтобы иметь один элемент для каждого символа, который должен быть распознан вашим приложением. Теперь перейдем к строке, чтобы увеличить элементы массива, соответствующие их значениям ASCII. (Вам может потребоваться вычесть определенную базовую сумму начального значения ASCII, поэтому вы начинаете считать первый элемент массива для 'a')

Эта часть также может быть выполнена довольно легко на C, поскольку она использует символы и ints в качестве эквивалентов.

После того, как вы сделали все, у вас есть все символы и их количество вхождений. Теперь вы можете выполнять итерацию через массив после начала создания узлов дерева. И используйте ваши алгоритмы кучи на этом дереве.

Или просто отсортируйте массив, чтобы построить свое дерево оттуда.

Удачи и счастливого кодирования :)