Доказательство. а) Пусть – префиксный код, тогда для него существует кодовое дерево, висячим вершинам которого соответствуют кодовые слова

а) Пусть – префиксный код, тогда для него существует кодовое дерево, висячим вершинам которого соответствуют кодовые слова. Рассмотрим фрагмент этого дерева (рис. 52).

Рис. 52

Если убрать вершины и вместе с инцидентными ребрами, вершина станет висячей, мы получим кодовое дерево для кода , в котором кодовым словам соответствуют только висячие вершины, следовательно, код – префиксный.

Наоборот, если – префиксный, то вершина, соответствующая кодовому слову , висячая. Добавив к этой вершине два ребра, получим две висячие вершины и , а слово в код не входит, вновь получим кодовое дерево для префиксного кода.

б) Найдем цену кодирования кода .

.