Как сгенерировать код префикса Хаффмана?

Как прокомментировал, я не уверен в понимании. Купить попробую …

Во-первых, я предполагаю, что вы уже правильно построили дерево.

Во-вторых, каждый лист содержит символ для кодирования. Код каждого символа определяется путем от корня до листа. Первоначально, когда вы находитесь в корне, код пуст. Если вы идете налево, то вы соединяете 0 к коду. Симметрично, если вы идете направо, то вы соединяете 1,

В-третьих, я предполагаю, что вы хотите список пар <symbol, code>, symbol это персонаж и code это строка, содержащая код префикса. Результатом является список всех символов, представленных деревом, вместе с их кодами.

Теперь алгоритм для создания этого списка будет использовать стек для хранения префикса от корня до текущего узла. Каждый раз, когда вы приходите к листу, код попадает в стек, но переворачивается. Такой алгоритм может быть следующим:

void codes(Node * root, stack<char> & s)
{
if (is_leaf(root))
{
auto symbol = // symbol stored in the node
string code = // the reversed stack content; that is the code of current leaf
cout << symbol << " = " << code << endl;
}

s.push('0');
codes(LLINK(root), s);
s.pop();

s.push('1');
codes(RLINK(root), s);
s.pop();
}

Я предлагаю стек, потому что это «естественная» структура данных для хранения частичного пути от корня к узлу. Тем не менее, может быть, было бы лучше vector<char>, В этом случае вы должны заменить push() от push_back() а также pop() от pop_back(), Но преимущество заключается в том, что вы можете создать код с помощью обратного итератора.

Также вместо инструкции cout ...Вы можете использовать список или вектор и вставить в него пару. После, если вы хотите, вы можете отсортировать его. В качестве альтернативы, вы можете использовать «естественно отсортированную» структуру данных, такую ​​как двоичное дерево поиска, и вы избегаете сортировки. Все это, конечно, если вы заинтересованы в том, чтобы производить сортировку по выводу символов.

Я надеюсь, что это было полезно