Должно быть, должно быть двоичное дерево Хаффмана?

Question

Все примеры, которые я смог найти для кодирования Хаффмана, имели четное количество символов для работы. Если это нечетное число символов, последний последний узел, добавленный к дереву, имеет только один ребенок? Или мне нужно добавить NULL-узел какого-то типа, чтобы все внутренние узлы имели ровно 2 ребенка?

Если это позже, это кажется запутанным, потому что я не уверен, как у вас будет значение NULL для символа (потому что все значения используются как действительные коды ASCII).

Answer 1

Нечетное число char s без проблем. Но это не привело бы к внутреннему узлу с одним ребенком.

/\ 
/\ 
a × 
    /\ 
    b c 

Путь дерево строится гарантирует, что все внутренние узлы имеют двух детей, независимо от того, сколько char s есть.

Первый начинается со списка листьев, а затем на каждом шаге (два) два дерева с самой низкой частотой объединяются, делая их левыми соответственно. правое поддерево нового - затем внутреннего узла, пока не останется только одно дерево. Каждый внутренний узел в конечном результате возникает из объединения двух поддеревьев, поэтому имеет двух детей.