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

Question

[sresort]

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

Как красиво элегантно декодировать? Может ли пригодится стэк?

Answer 1

[Wataru]

Может. Надо опять же через dfs рекурсией пройтись по дереву. Абсолютно тот же алгоритм что при кодировании, только вместо вывода бит - ввод. Вместо проверки вершины, ее создание.

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

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

Comments

[sresort]

https://pastebin.com/Y5L8J8M1 Что я делаю идейно не так?

[Wataru]

sresort, Что этот код дложен делать? Что за f_get_bit? Что означают параметры?

[sresort]

Wataru, Это рубо говоря кусок кода, который если видит 1чку считывает дополнительно следующие 8 бит из файла, потому что мы знаем что бит 1чка это лист, а за ним 8 битов - сам символ
Я пытаюсь рекурсивно декодировать

[Wataru]

sresort, В случае, если вы прочитали 1, то вы должны создать вершину и вернуть ее. Не заполнять у какой-то вершины левого ребенка рекурсивно, а просто вернуть.

Ну и еще, ваша функция не должна принимать никаких node. Что оно означает вообще? Функция просто возвращает корень поддерева. Вы же при вызове присваиваете уже node->left тому что функция вернула. Зачем туда еще что-то передавать.

[sresort]

Wataru, Как это зачем заполнять? Нужно же связать... Что-то я запутался в рекурсии немного как грамотно это сделать.. Помогите распутаться, пожалуйста

[Wataru]

sresort, Функция restore_tree возвращает корень поддерева. В функции, если прочли 1 - создали лист, заполнили символ, вернули. Иначе создаем лист и рекурсивно заполняем его детей. Буквально:

bit = readbit();
if (bit) {
  data = ...;
  return new Node(data);
}
Node* node = new Node();
node->left = restore_tree(file);
node->right = restore_tree(file);
return node;

все.

[sresort]

Wataru, Что за нода передается в restore_tree, что за file

[Wataru]

sresort, file - это этот ваш T_bit_file из которого вы читаете. Никакой ноды в restore_tree не передается. Она создает внутри новую вершину и возвращает ее.

[sresort]

Wataru, А как связывание будет происходить? https://pastebin.com/p2BHebiD Чет не до конца понимаю что вы имеете в виду

[Wataru]

sresort, Связывание просиходит в момент присваивания node->left и node->right.

Только удалите аргумент node. Вообще. Он вам не нужен. Остальной код вроде похож на правду.

[sresort]

Wataru, https://pastebin.com/MP95yaTJ Так?
101100011011000110110001 - вот файл в бинарном виде, который я обрабатываю
Чет вообще связывания не происходит

[Wataru]

sresort,

Стоп, что это за строка вообще? Почему она с листа начинается? 10001 в конце не хватает четырех - бит.

Вы как вообще кодируете-то? Каким обходом. Надо сначала выписывать текущую вершину и потом рекурсивно двух детей.

[sresort]

Wataru, 01 01100001 01 10000101 1 00001011
ой я там действительно немного в алгоритме кодирования наврал? А вот так?

[Wataru]

sresort, Ну, так должно создать дерево из 5 вершин с тремя листьями.