Коды Закса

Коды Закса (Zaks' schemes) — относятся к классу линейных кодов деревьев. Пусть дано бинарное или $k$-ичное дерево $T$ с $n$ вершинами такое, что каждая внутренняя вершина дерева помечена числом 1, а каждая висячая — числом 0. Рассматриваются следующие способы кодирования дерева $T$:

1) $x$-кодом Закса дерева $T$ называется последовательность пометок его вершин, перечисленных в инфиксном порядке;

2) $z$-кодом Закса дерева $T$ называется последовательность номеров единиц в $x$-коде дерева $T$, перечисленных в порядке их возрастания;

3) $y$-кодом Закса дерева $T$ называется последовательность номеров нулей в $x$-коде дерева $T$, перечисленных в порядке их возрастания.

См. также

• Коды Ли,
• Коды, свободные от повторений,
• Коды с дублированием номеров вершин,
• Коды с использованием ограничителей,
• Линейный код,
• Уровневые коды корневых деревьев,
• Ротационный код.

Литература

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.