748
правок
Изменения
→Укладка дерева
== Укладка дерева ==
Существуют несколько способов укладки дерева на плоскости.
[[Файл:Layer-graph.jpg|250px|left|thumb|Рисунок 1. Пример поуровневой укладки дерева.]]
=== Поуровневая укладка ===
Простой способ построения нисходящего плоского изображения дерева заключается в использовании его поуровневого расположения (''layered drawing''), при котором вершины глубины <tex>a</tex> имеют координату <tex>y = – a</tex>, а координаты по горизонтальной оси распределяются так, чтобы никакие левые поддеревья не пересекались с правыми (см. рисунок 1). Возможна реализация за линейное время, позволяющая получить оптимальное по ширине [[Укладка графа на плоскости|плоское дерево]] в области размера <tex>O(N^2)</tex> (где <tex>N</tex> — число вершин дерева).
[[Файл:Circle_layered_tree.jpg|250px|right|thumb|Рисунок 2. Граф из рисунка 1, но уложенный радиально.]]
=== Радиальная поуровневая укладка ===
Радиальная поуровневая укладка(''radial drawing'') дерева отличается тем, что его уровни имеют вид концентрических окружностей (см. рисунок 2).
