Методы программирования. Громов Ю.Ю - 46 стр.

UptoLike

Составители:

Рубрика:

Рис. 21. Преобразованный лес из двух деревьев

Повернув затем некоторые части графа примерно на 45

по часовой

стрелке вокруг соответствующих узлов, получим искомое представление

бинарного дерева, изображённое на рис. 22.

Рис. 22. Бинарное дерево, представляющее лес из двух деревьев

Выполняя обратные действия в обратном порядке, можно из бинар-

ного дерева получить соответствующий ему лес.

Описанные преобразования называются естественным соответст-

вием между лесами и бинарными деревьями.

Иногда для удобства граф бинарного дерева изображают так, как на

рис. 21, т.е. не выполняя поворотов по часовой стрелке. Прошитое би-

нарное дерево, соответствующее рассматриваемому лесу, представлено

на рис. 23. Здесь штриховые линии обозначают правые, а пунктирные –

левые связи-нити. Заметим, что правые связи-нити идут от самого право-

го сына к отцу семьи.