SICP по-русски

Дерево кодирования из примера изображено на рисунке ниже:

При декодировании последовательности

0 1 1 0 0 1 0 1 0 1 1 1 0

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

Сначала, пройдем по левой ветке (0) и попадем в лист А:

0 1 1 0 0 1 0 1 0 1 1 1 0  

A

Теперь, двигаясь направо (1), опять направо (1) и налево (0), получим D:

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D

Дальше действуем аналогично (шаги показаны ниже, результат на каждом шаге выделен жирным шрифтом):

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B B

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B B C

0 1 1 0 0 1 0 1 0 1 1 1 0  

A D A B B C A

И действительно:

> (decode sample-message sample-tree)  

(A D A B B C A)