Коды Закса

Материал из WikiGrapp
Перейти к навигации Перейти к поиску

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

Zaks' schemes.png

1) [math]\displaystyle{ x }[/math]-кодом Закса дерева [math]\displaystyle{ T }[/math] называется последовательность пометок его вершин, перечисленных в инфиксном порядке;

2) [math]\displaystyle{ z }[/math]-кодом Закса дерева [math]\displaystyle{ T }[/math] называется последовательность номеров единиц в [math]\displaystyle{ x }[/math]-коде дерева [math]\displaystyle{ T }[/math], перечисленных в порядке их возрастания;

3) [math]\displaystyle{ y }[/math]-кодом Закса дерева [math]\displaystyle{ T }[/math] называется последовательность номеров нулей в [math]\displaystyle{ x }[/math]-коде дерева [math]\displaystyle{ T }[/math], перечисленных в порядке их возрастания.


См. также

Литература

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