@sresort

Можно ли восстановить дерево хаффмана с помощью стэка?

Здравствуйте! Кодирую дерево хаффмана побитово так
0 если нода, 1 если лист, а потом 8 битиков - символ
через dfs

Как красиво элегантно декодировать? Может ли пригодится стэк?
  • Вопрос задан
  • 104 просмотра
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Может. Надо опять же через dfs рекурсией пройтись по дереву. Абсолютно тот же алгоритм что при кодировании, только вместо вывода бит - ввод. Вместо проверки вершины, ее создание.

Можно вместо рекурсии использовать стек вручную.

Edit: а вручную будет примерно так: Читаем бит. Если 0, то кладем в стек 0. Если 1, то текущий стек - код симола по следующим 8 битам и удаляем из стека все 1 сверху до первого нуля. Нуль меняем на 1.
Правда это даст не дерево а только коды символов. Чтобы получить дерево надо будет в стеке хранить указатели на вершины.
Ответ написан
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы