Задать вопрос
@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


Если нужны какие-то свойства, то скажите.
  • Вопрос задан
  • 550 просмотров
Комментировать
Подписаться 1 Оценить Комментировать
Решения вопроса 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 — отрицательное число с запредельно большим модулем
Ответ написан
21 комментарий
21 комментарий
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Вакансии с Хабр Карьеры
С developer (алгоритмист)
СберТех • Москва
от 350 000 ₽
Бэкенд программист
Grade Factor • Москва
от 80 000 ₽
Senior Java Developer, Database Engine
CedrusData
от 350 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Нужен директолог с опытом работы
19 апр. 2024, в 10:02
6000 руб./за проект
Помощь с парсингом XML файла яндекс товаров
19 апр. 2024, в 09:46
500 руб./за проект
Обработать массив фотографий
19 апр. 2024, в 08:46
5000 руб./за проект
Ещё заказы