Двоичное дерево Хаффмана должно быть правильным?
Все примеры, которые я мог найти для кодирования Хаффмана, имели четное число символов для работы. Если это нечетное число символов, может ли последний внутренний узел, добавленный в дерево, иметь только одного ребенка? Или мне нужно добавить какой-нибудь узел NULL, чтобы все внутренние узлы имели ровно 2 дочерних узла?
Если это позднее, это кажется сбивающим с толку, потому что я не уверен, как вы могли бы иметь значение NULL для символа (потому что все значения используются в качестве допустимых кодов ASCII).
Решение
Нечетное число charс не проблема. Но это не привело бы к внутреннему узлу с одним ребенком.
/\
/ \
a ×
/ \
b c
Способ построения дерева гарантирует, что все внутренние узлы имеют двух дочерних элементов, независимо от того, сколько charс есть.
Один начинается со списка листьев, а затем на каждом шаге () два дерева с наименьшей частотой объединяются, делая их левыми, соответственно. правое поддерево нового — затем внутреннего — узла, пока не останется только одно дерево. Каждый внутренний узел в конечном результате возникает в результате объединения двух поддеревьев, следовательно, имеет двух дочерних элементов.
Другие решения
Других решений пока нет …