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

Question

Я работаю над программой на C++ и над моей группой, и я не могу понять логику того, как генерировать префиксный код, используя обход inOrder. У нас есть дерево префиксного кода, и мы хотим сгенерировать из него коды.

Поскольку у нас возникают проблемы с логикой, я не знаю, нужно ли мне предоставлять какой-либо код. Если вам нужно, дайте мне знать.

Благодарю.

Answer 1

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

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

Во-вторых, каждый лист содержит символ для кодирования. Код каждого символа определяется путем от корня до листа. Первоначально, когда вы находитесь в корне, код пуст. Если вы идете налево, то вы соединяете 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 ...Вы можете использовать список или вектор и вставить в него пару. После, если вы хотите, вы можете отсортировать его. В качестве альтернативы, вы можете использовать "естественно отсортированную" структуру данных, такую ​​как двоичное дерево поиска, и вы избегаете сортировки. Все это, конечно, если вы заинтересованы в том, чтобы производить сортировку по выводу символов.

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