4 / 14
В.П. Корвяков
36
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. Приборостроение. 2017. № 3
Поскольку число возможных структур бинарных деревьев с
N
узлами равно
числу Каталана
,
N
C
любое число от 0 до
1
N
C
−
можно сопоставить с конкрет-
ной структурой дерева. Задача кодирования и декодирования заключается в
нахождении алгоритма однозначного взаимного преобразования индекса дере-
ва в структуру бинарного дерева.
Для решения этой задачи примем, что индексу 0 соответствует бинарное
дерево с
N
узлами, полностью ориентированное по левую сторону, а индексу
1
N
C
−
— по правую. Установим, что каждый узел определяется следующей
структурой:
NODE
{
NODE LLINK;
NODE RLINK;
}
где
LLINK
— корневой узел левого поддерева или
EMPTY
, если левое поддерево
отсутствует;
RLINK
— корневой узел правого поддерева или
EMPTY
, если пра-
вое поддерево отсутствует.
Природа древовидных структур подсказывает возможность применения
рекурсивного алгоритма. На каждом вызове функции
NODE
=
decode
( , )
I N
по
заданному индексу структуры
I
и числу узлов
N
необходимо следующее.
1.
Если
N
= 0, то вернуть
EMPTY
, иначе перейти к п. 2.
2. Инициализировать структуру возвращаемого узла
NODE ROOT
{
LLINK
=
=
EMPTY
,
RLINK = EMPTY
}.
3.
Если
N
равно 1, то вернуть
ROOT
, иначе перейти к п. 3.
4.
Вычислить число узлов левого поддерева
.
L
N
5. Определить число узлов правого поддерева
,
R
N
которое всегда равно
1.
L
N N
− −
6.
Рассчитать индекс структуры левого поддерева
L
I
такой, что
0
1.
L
L N
I C
≤ ≤ −
7.
Вычислить индекс структуры правого поддерева
R
I
такой, что
0
1.
R
R N
I C
≤ ≤ −
8.
Вызвать функцию
decode
( ,
)
L L
I N
и присвоить результат ее выполнения
левому поддереву данного узла:
ROOT.LLINK
=
decode
( ,
).
L L
I N
9.
Вызвать функцию
decode
( ,
)
R R
I N
и присвоить результат ее выполнения
левому поддереву данного узла:
ROOT.RLINK
=
decode
( ,
).
R R
I N
10.
Вернуть структуру
ROOT
.
Отдельную задачу представляет вычисление числа
.
L
N
К ее решению можно
подойти исходя из следующих соображений. Поскольку нулевому индексу соот-
ветствует дерево, полностью ориентированное по левую сторону, для
0
I
=
имеем
1,
L
N N
= −
0.
R
N
=
Число комбинаций левого поддерева равно
1
.
N
C
−
Таким об-
разом, первые
1
N
C
−
индексов перечисляют различные комбинации левого подде-
рева, состоящего из
1
N
−
узлов, при пустом правом поддереве (рис. 3,
а
).