HV или О том, как неплохо отрисовывать бинарные деревья

[jced]

А что если рассмотреть вариант увеличения угла между ребрами, длина которых увеличивается? Для того, чтобы немного уменьшить вертикальный размер. Или это ухудшает читаемость?

[Zhe_Ver]

Если вы всё-таки угол имеете в виду, то тогда получится уже не HV-представление. HV-представление имеет только 2 угла: 0 и Pi/2.

[Peter_Voronov]

А вот если немного менять угол каждого следующего потомка. Допустим от 20 до 80 градусов, и этот диапазон делить между требуемым количеством колен. Не ради сужения размера графика, а именно ради информативности. Тогда в любой точке будет понятно, какого порядка потомок и примерно сколько шагов до корня.

[Zhe_Ver]

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

[Saffron]

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

[third112]

тем более интернет сразу ничего не выдал…

М.б. не так искали? Гугл на запрос «визуализация дерева» кидает много ссылок. Можно еще в Википедии посмотреть: там большой список источников и софта для визуализации графов, что-то может быть полезным для бинарных деревьев. Из сравнительно старых источников:

Н. Вирт, Алгоритмы+структуры данных=программы, М., Мир, 1985, С. 267 — Изображение древовидной структуры. Там исходный код программы для распечатки бинарного дерева на алфавитно-цифровом (не графическом) принтере.

В.Н.Касьянов, В.А.Евстигнеев, Графы в программировании: обработка, визуализация и применение, СПб, БХВ-Петербург, 2003, С.357. — Рисование деревьев.

Вопрос по статье: а как предлагается нумеровать/метить вершины (узлы)? (ИМХО без меток рисунок будет не очень информативным).

[Zhe_Ver]

Не совсем понял вопрос про нумерацию… Вроде же алгоритм однозначно говорит как выводить, нет?

Может и выдаёт, но на слова HW-tree не отзывался.

[third112]

Я о том где и как рисовать метки (цифры и/или буквы)? На вершинах? рядом? А если рядом с вершиной, то нужно чтобы соседние метки не пересекались.

[Deosis]

Судя по изображению, вы просто повернули изображение дерева набок. (представьте египетскую пирамиду в таком положении)
Для многих привычно видеть корень вверху в центре, как раз на месте правого ребенка в HV дереве.
Ещё стандартное представление дерева легко расширяется на тернарные и В-деревья. Как их можно нарисовать в вашем представлении?

[Zhe_Ver]

1. Нет, не просто набок. Присмотритесь. По крайней мере, так может быть получилось только из-за какой-то случайной симметрии.
2. О представлении B-деревьях вообще стоит говорить отдельно. Я могу написать статью, в которой будут кое-какие идеи о представлениях, если это имеет смысл.