4. Леса
 

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

Лес может быть преобразован в бинарное дерево. Алгоритм преобразования леса в бинарное дерево схож с алгоритмом преобразования m-арного дерева. Сначала каждое дерево леса обрабатывается точно так же, как и отдельное дерево на первом этапе. Затем корни деревьев соединяются горизонтальными линиями и осуществляется поворот по часовой стрелке на 45 градусов относительно корня первого (левого) дерева. Таким образом, корнем леса, представленного бинарным деревом, становится корень первого дерева, второе дерево становится правым поддеревом корня первого, третье дерево — правым поддеревом корня второго дерева и т.д.

Приведем схему преобразования леса, состоящего из двух деревьев а и g, в бинарное дерево.

Рис.Преобразование леса графов в бинарное дерево

Представление m-арного дерева и леса бинарным деревом дает возможность однообразного физического представления деревьев в ЭВМ и облегчает их обработку.