Кодировка дерева

Существуют способы задания деревьев, более экономичные, чем с помощью матриц смежности и инцидентности, которые в компьютере занимают много памяти.

Заметим, что дереву с одним ребром сопоставляется код (01). Если деревьям Т1 и Т2 (рис.2.33, а) сопоставлены коды и соответственно, то дереву С (рис. 2.33, б) сопоставляется код (01), а деревьям D и E (рис. 2.33, в) – коды и .

Не всякая последовательность из п единиц и п нулей служит кодом дерева. Необходимым и достаточным условием для этого служит следующее: в любом начальном отрезке последовательности количество нулей не меньше количества единиц. Если это условие выполняется, дерево может быть построено по коду.