Коды Ли

Коды Ли (Lee scheme) — относятся к классу линейных кодов деревьев. Пусть $T$ — бинарное дерево, каждая внутренняя вершина помечена числом 1, а каждая висячая — числом 0. Рассматриваются следующие вариации кодов Ли:

1) $u$-кодом Ли дерева $T$ называется последовательность пометок вершин, написанных в порядке обхода его в ширину;

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

3) поуровневый позиционный код Ли дерева $T$ высоты $h$ — это последовательность $M=M_1,M_2,\dots ,M_{h-1}$, где $M_i$ — последовательность номеров внутренних вершин уровня $i$, перечисленных в порядке их возрастания.

См. также

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

Литература

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