7 / 14
Алгоритм кодирования бинарного дерева с минимальной избыточностью
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 3
39
Решив задачу декодирования индекса в структуру дерева, перейдем к об-
ратной задаче: по заданной структуре бинарного дерева с
N
узлами необходимо
получить число
I
от 0 до
1,
N
C
−
кодирующее такую структуру. Хотя кодирова-
ние деревьев и не требовалось для исходной задачи оптимизации графических
интерфейсов, его следует рассмотреть для полноты проработки вопроса и для
возможности применения этого метода при решении других проблем.
Рассмотрим бинарное дерево с
N
узлами, в левом поддереве которого нахо-
дится
L
N
узлов, а в правом —
–1.
R
L
N N N
= −
Принятый метод перечисления
деревьев (от полностью левоориентированного к полностью правоориентиро-
ванному с перебором комбинаций левого поддерева при фиксированном пра-
вом) предполагает, что начальный индекс дерева с
R
N
узлами левого поддерева
равен
1
0
1
0
.
R
N
N k k
k
I
C C
−
− −
=
=
Дерево, имеющее индекс
0
,
I
показано на рис. 4,
а
.
Рис. 4.
Дерево с индексом
1
0
1
0
R
N
N k k
k
I
C C
−
− −
=
=
(
а
), с индексом
1
– 1
0
R
N
N k k
k
I
C C
−
−
=
=
+
L
N R
C I
+
(
б
), правая часть которого приняла требуемый вид, требуемое дерево (
в
)
с индексом
R
I
правого поддерева и
L
I
левого поддерева
После этого для каждой из
R
I
зафиксированных комбинаций правого под-
дерева последовательно перечисляются по
L
N
C
комбинаций левого поддерева
(рис. 4,
б
). Таким образом, правое поддерево принимает требуемый вид, а левое
поддерево полностью ориентировано по левую сторону. Индекс этого дерева
равен
1
– 1
0
.
R
L
N
N k k
N R
k
I
C C C I
−
−
=
=
+
Для получения исходного дерева необходимо перечислить еще
L
I
комби-
наций левого поддерева (рис. 4,
в
). Таким образом, окончательно имеем форму-
лу кодирования дерева:
1
– 1
0
.
R
L
N
N k k
N R L
k
I
C C C I I
−
−
=
=
+
+
Значения индексов
R
I
и
L
I
рекурсивно определяются этим же алгорит-
мом, либо равны нулю для пустых поддеревьев.