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

Question

[vasIvas]

Имеется дерево где ноды имеют неограниченное количество детей.
Нужно расставить их на плоскости так, чтобы между братьями был минимальный размер A,
а между соседями минимум B.
Стоит упомянуть что ширина ноды не фиксированная, но это я думаю не столь важно.

Если кто-то знает, как это решить, объясните на словах.

Нода выглядит так -

getLeftNode():Node
getRightNode():Node
insertNode(node:Node):void
getNodeAt(index:uint):Node

parent:Node

next:Node
prev:Node
// сюда я пишу значение на которое брат должен быть отложен от брата
indent:Number 

// сюда записываю общую ширину детей вместе с indent
tierWidth:Number

width:Number
height:Number

// служит для записи координат
position:Point

Если нужны какие-то свойства, то скажите.

Answer 1

[Mercury13]

Придумал.
Для каждого узла делаем координату deltaX — смещение по X относительно отца.
И динамический массив из пар (x1, x2) — границы деревьев на всех уровнях.

алг рекурсия(узел: Узел)
  длина_мас = 0

  // Прогоним алгоритм для сыновей, рассчитаем длину массива
  для всех сыновей (узел) → сын
    рекурсия(сын)  // ыгы, в основе банальный обход в глубину
    длина_мас = макс(длина_мас, сын.границы.длина)
  длина_мас = длина_мас + 1

  разложить сыновей на плоскости, руководствуясь их массивами границ
     и вашим чувством прекрасного;  соответственно присвоить ИХ deltaX
     (оставлю это как домашнее задание)

  // Рассчитаем границы дли нашего узла
  границы.установить_размер(длина_мас)  
  границы.заполнить(левая=+M, правая=—M)
  полширины = узел.ширина / 2
  границы[0] = (левая = −полширины, правая = узел.ширина − полширины)
  для всех сыновей (узел) → сын
    для i = [0 .. сын.границы.длина)      
      узел.границы[i+1].левая = мин(
           узел.границы[i+1].левая, сын.границы[i].левая + сын.deltaX)
         // если сыновья идут слева направо, этого хватает!
      узел.границы[i+1].правая = сын.границы[i].правая + сын.deltaX
    сын.границы.установить_размер(0)    // массив больше не нужен

// Если же нужны точные координаты каждого узла…

алг уточнитьКоординаты(узел: Узел; Y: целое)
  узел.коорд.Y = Y
  Yсына = Y + высота_яруса
  для всех сыновей (узел) → сын
    сын.коорд.X = узел.коорд.X + сын.deltaX
    уточнитьКоординаты(сын, Yсына)

+M — запредельно большое число
−M — отрицательное число с запредельно большим модулем

Comments

[Mercury13]

> Если мин\макс установить миллиард, то расчеты будут производится из расчета такого огромного поля-массива?
Просто чтобы было заведомо больше всех разумных координат.

> И ещё, это один рекурсивный метод? Если нет, то разбейте пожалуйста на логические блоки.
Один рекурсивный метод. Всё равно разбил.

> это координаты самого левого и самого правого ребенка узла?
Это координаты самого левого и самого правого узла в поддереве относительно текущего узла.

> Ведь у родителя с тремя детьми шириной по 10 и пробелами 10, длина будет не 50, а может быть в разы больше из-за того что у одного из детей будут ещё дети которые соприкасаются на нижних уровнях.
Потому и не пара (left, right), а массив — чтобы учитывать все ярусы и в «дыры» одного сына можно было пристроить «баобаб» другого.

[Mercury13]

> это координаты самого левого и самого правого ребенка узла?
Это координаты самого левого и самого правого узла в поддереве НА i-м ЯРУСЕ относительно текущего узла.

[Mercury13]

Я подкорректировал алгоритм, чтобы ширина узла могла быть произвольной.

[Mercury13]

Чтобы не убирало, используйте тэг code.

.........|
.....0-0-0
..........|
.......0-0

...........0
............|
......0-0----0
.........|........ |
.......0-0....0-0

[Mercury13]

Что значит «не увеличивают»? Это габариты i-го яруса. Например.

    0       0..1
  0--0-0   -2..3
 0-0 0     -3..1

[Mercury13]

У каждого узла свой массив габаритов, который можно уничтожать, когда вычислены габариты отца.

[vasIvas]

Я вот о чем -


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

[Mercury13]

Эта часть и остаётся вам как домашнее задание. Система справится, т.к. она хранит габариты всех поддеревьев на всех ярусах.

[Mercury13]

P.S. Например, у того самого дерева

    0       0..1
  0--0-0   -2..3
 0-0 0     -3..1

у первого узла 1-го яруса координаты 0..1 и −1..2, у 2-го 0..1 и 0..1, у 3-го только 0..1.

[Mercury13]

Ошибка тут у меня… Координаты 0..1, −2..4 и −3..2.

[Mercury13]

Алгоритм, который я оставил как задание, прост. Расставить поддеревья друг относительно друга так, чтобы в нулевом ярусе зазор был A, в остальных B, а затем спозиционировать всё это чудо относительно папы.

[vasIvas]

Mercury13: первый вопрос - массив границы это один массив, который хранит только узлы-границы? А то у Вас сначала "границы" упоминаются в самостоятельном контексте, а следом в контексте ребенка.

[Mercury13]

Массив «границы» есть у каждого узла. Длина массива — это высота поддерева. Элемент — два числа: левая и правая граница соотв. яруса поддерева. Относительно элемента-владельца, разумеется.

[Mercury13]

Попробую нарисовать, только ночью.

[vasIvas]

Mercury13: был бы очень благодарен. А то сегодня сел делать и сразу ступор. Вы вчера сказали что это единый метод, но расчет на основе границ происходит до того, как они рассчитываются.

[vasIvas]

Mercury13: даже можно на листочке и сфоткать телефоном. Разницы нет, главное чтобы все было по шагам. Прям как для детсадовца. Я впервые с таким столкнулся. Было конечно трудно но по шагам преодолевал. А сейчас просто ступор. Сейчас нашел на reference.wolfram.com/language/tutorial/TreeDrawin... статью, сижу читаю, хотя тоже больше вопросов чем ответов.

[Mercury13]

Ну, вот картинка.
Минимальной единицей считаем клеточку, но ничего не мешает этой самой минимальной единицей сделать и пиксель.

[Mercury13]

…минимальной единицей ПОЗИЦИОНИРОВАНИЯ ПО X, разумеется. По Y наш простенький алгоритм клеточный и только клеточный.

[Mercury13]

Я не написал deltaX, но он таков:
— какой угодно, например, 3
— −2, 1, 3
— −1, 1, 0

[vasIvas]

Mercury13: по сути векторы.. да? Я в самом начале тоже с векторами пробовал, но у меня не получилось. Но я делал не так как Вы. Как объяснили Вы я сегодня так и не смог додуматься.

Мне хочется задать Вам просто миллион вопросов, но сегодня у меня уже голова не соображает :( А завтра я проштудирую темы на вольфрам и обязательно вернусь сюда и уже все по пунктам расспрошу. И буду надеяться, что Вы уделите мне немножечко своего свободного времени. Спасибо.

[Mercury13]

Динамические массивы. std::vector — это тоже динамический массив.