9.3.1. Представление свободных, ориентированных и упорядоченных деревьев

Всякое свободное дерево можно ориентировать, назначив один из узлов корнем. Всякое ордерево можно произвольно упорядочить. Всякое упорядоченное дерево можно представить бинарным деревом, проведя правую связь к старшему брату, а левую — к младшему сыну.

Пример

На рис. 9.10 приведены диаграммы упорядоченного и соответствующего ему би­нарного деревьев.

Рис. 9.10. Упорядоченное и бинарное деревья

Таким образом, достаточно рассмотреть представление в ЭВМ бинарных де­ревьев.

ЗАМЕЧАНИЕ-

Из данного представления следует, что множество бинарных деревьев взаимнооднозначно соответствует множеству упорядоченных лесов упорядоченных деревьев.