Hv Или Как Хорошо Рисовать Бинарные Деревья

Когда-то я хотел что-то написать, но все было кончено.

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

Хочу сказать большое спасибо Дайняку А.

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

На протяжении всей статьи дерево = бинарное дерево.

Нарисовать небольшие листья деревьев (например, 5-10) действительно несложно.

И для них вы можете использовать естественное представление (это тип LKP) .

И это работает очень хорошо.

HV или Как хорошо рисовать бинарные деревья

Возможно, вы могли бы даже попробовать нарисовать дерево со 100 узлами.

Но если узлов больше — например, 1000 — то можно рисовать деревья.

Но читать их (и понимать) будет совершенно неудобно.

Причем под чтением мы подразумеваем именно изображение дерева на экране, чтобы они просто не слипались до бесконечности, т. е.

в одно большое пятно.

HV или Как хорошо рисовать бинарные деревья

Один из вариантов борьбы с этим, но, наверное, даже не столько борьба, а просто некая структура нормальной визуализации – это ЧАС ориентальный В вертикальный -дерево.

То есть вот что используется для визуализации:

Мы только заходим

.
Хотя это совершенно необязательно с точки зрения реализации.
Нам просто будет удобно.
Хотелось бы как-то удачно победить в пространстве и читабельности.
(Но я не хочу сейчас об этом говорить, может быть, я могу просто сказать, что сверхузкая и длинная полоса дерева совершенно нечитабельна.
)

Итак, концепция представления HV-дерева проста (и рекурсивна): если у нас есть дерево 1 и дерево 2 и мы хотим их объединить (т. е.

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

быть сделано: То есть то, как происходит склейка, совершенно формально: 1. Имеем заданную длину ребра (что, вообще говоря, естественно).

И можем клеить по какому правилу.

Что мы делаем: Перейдем к корню, S=0. Идем от корня ко всем листам и каждый раз идем вправо (от экрана) S=S+1. 2. То же самое со вторым деревом.

3. Внизу закрепляем дерево, которое пошире (у которого S больше).

А направо — все остальное.

Если они равны, нам не важно, как его повесить (хотя, конечно, нам было бы лучше, если бы длинный был внизу, если мы все-таки хотим как-то ограничить рисунок, но если мы не ограничены в изложении , стоит попробовать сделать наоборот - будет удобнее видеть).

Именно так мы определяем такие деревья, а также процесс и построение.

Ну и для примера сравнение презентации в стандартном формате и аппаратной верстке.

Неполное дерево в стандартном формате.
презентация.
Полное дерево в стандартном формате.
представление: Надо сказать, что мы не сможем представить всё дерево с рёбрами одинаковой ширины.
(Точнее, если ребро исходит из узла на n-м уровне ниже (лист — уровень 0, предлист — 1), то длина ребра должна быть n*s, где s — единичное ребро.
(В на моем рисунке это не сразу верно, потому что я передвинул углы ребер.
)
Первое дерево в представлении HV. Это то же дерево, что и на первой картинке.