Алгоритм кодирования бинарного дерева с минимальной избыточностью

6 / 14

В.П. Корвяков
38 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 3
При перечислении комбинаций дерева (с заданными L N и )
R N правое под-
дерево фиксируется, и последовательно рассматриваются L N C комбинаций ле-
вого поддерева. Далее осуществляется переход к следующей комбинации право-
го поддерева и процедура повторяется. Следовательно,
ˆ
;
L
R
N
I
I
C
 
=  
 
ˆ .
L L R N I I I C= −
Скобки    обозначают неполное частное, т. е. округление до ближайшего
целого в меньшую сторону. Таким образом, алгоритм функции decode можно
описать следующим псевдокодом:
NODE decode(I, N) {
if (N == 0) return EMPTY; // Дерево с 0 узлами – пустое
NODE ROOT { LLINK = EMPTY; RLINK = EMPTY };
if (N == 1) return ROOT; // Один узел без поддеревьев
NL = N – 1;
NR = 0;
SUM = 0;
OLDSUM = 0;
K = 0;
CL = 1;
CR = 1;
while (SUM <= I) {
NL = N – K – 1;
NR = K;
CL = catalan(NL);
CR = catalan(NR);
OLDSUM = SUM;
SUM = SUM + CL*CR;
K++;
}
I = I – OLDSUM;
IR = floor(I/CL);
IL = I – IR*CL;
ROOT.LLINK = decode(IL, NL);
ROOT.RLINK = decode(IR, NR);
return ROOT;
}
В приведенном псевдокоде функция floor(X) выполняет округление величи-
ны X до ближайшего целого в меньшую сторону, а функция catalan(N) — вы-
числение N-го числа Каталана.