Как посчитать координаты для дерева?

Question

[Bogdan]

Есть некая диаграмма для элементов которой нужно посчитать координаты так что бы не было наложений и дерево выглядело нормально. Координаты корневого элемента задаются в ручную. Соответственно при перемещении рута или удалении какого-то элемента, все элементы могут быть пересчитаны.
Дерево должно выглядеть примерно так:


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

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

Answer 1

[Станислав Макаров]

На вашей картинке некий нелистовой узел располагается посередине того интервала (по оси X), который занимают его дочерние узлы.

Поэтому решите задачу определения того, сколько места должны занимать дочерние узлы, включая все их дочерние узлы и т.д. Эту задачу можно решить алгоритмом ПВГ-обхода дерева, управляя стеком вершин вручную или же пользуясь рекурсивными вызовами процедуры обхода.

Comments

[longclaps]

ПВГ лучше подойдёт или пользуясь рекурсией

Смишно.

[Станислав Макаров]

longclaps что смешного, простите?

[Станислав Макаров]

longclaps если вы намекаете на то, что по факту это одно и то же, то не нужно, т.к. вопрошающий врядли это поймёт.

[longclaps]

Станислав Макаров, и это повод дурить ему голову? )

[Станислав Макаров]

longclaps А вы как представляете он будет решать эту задачу?
Я думаю либо он пойдёт и таки прочитает про DFS, и может быть поймёт (или прочитает в хорошем источнике), что в качестве стека для depth-first обхода можно применять как вручную управляемый стек, так и стек вызовов, либо он не пойдёт ничего читать, и попытается определить задачу как задачу рекурсивную (например, "будем считать место, занимаемое узлом, как сумму мест, занимаемых дочерними узлами с учётом отступов, если дочерние узлы есть, а если - как константу n") и вполне себе решит её, написав обычные рекурсивные вызовы и даже возможно не поняв, что это тоже ПВГ.

Я попытался дать альтернативных способа реализации (!). Согласитесь, использовать стек самостоятельно или делать рекусивные вызовы - довольно разные подходы.

[Станислав Макаров]

longclaps Впрочем, вы правы что ответ не даёт однозначного понимая теоретической стороны вопроса. Я думаю стоит его поправить, спасибо.

[longclaps]

Станислав Макаров, по мне - так вы намусорили. Для вычисления ширины дерева естественно использовать поиск в ширину (неожиданно, правда?).

[Bogdan]

В общем-то с обходом дерева я знаком, и ранее уже пытался решить это с использование чего-то похожего на dfs, но в итоге приходил к одному, дерево было не ровным, разъезжалось в некоторых местах и элементы пересекались. Я отходил от уровня с максимальной шириной к руту