Предлагаю нарисовать дерево так же.Это можно сделать с помощью какого-либо движущегося «курсора рисования».
Вы можете сохранить атрибут width для каждого узла, который рассчитывается следующим образом:
-
widthОтпуск равен 1 width внутреннего узла - это сумма всех дочерних элементов width s
Затем вы выводите корень "в первой строке"посередине, что означает, что вы просто берете половину корня width.
Затем вы генерируете сетку по изображению, так что каждая линия сетки соответствует одной линии соответственно.один шаг слева направо, и каждое пересечение линий сетки может содержать узел, и у каждого узла есть достаточно места.
Затем вы перебираете дочерние элементы и, перебирая, вы накапливаете дочерние width s и рисуете.дети "на следующей линии".Чтобы нарисовать currentChild, вы перемещаете курсор рисования currentWidth/2 вправо, рисуете currentChild и перемещаете курсор рисования на оставшиеся currentWidth/2 вправо.
Чтобы получить узлы вхороший порядок, вы могли бы рассмотреть поиск в ширину.
Я надеюсь, что мое объяснение ясно, но я думаю, что будет лучше, если я нарисую небольшую картинку.
Это наше дерево(x - узлы, все остальные ребра)
+-------x--+-------+
| | |
+-x-+ +-+x+-+ +-x-+
| | | | | | | | |
x x x x x x x x x
Итак, вы вычисляете лист width s:
+-------x--+-------+
| | |
+-x-+ +-+x+-+ +-x-+
| | | | | | | | |
1 1 1 1 1 1 1 1 1
Затем снизу вверх width sв виде сумм детских width с:
+-------9--+-------+
| | |
+-2-+ +-+4+-+ +-3-+
| | | | | | | | |
1 1 1 1 1 1 1 1 1
Итак, вы начинаете с корня (width 9) и идете на 4,5 шага к ригту в первой строке.
Затем вы перемещаете «курсор для рисования» на вторую строку, «столбец 0» (идите влево).
Первый дочерний элемент имеет width 2, поэтому мы идем 2/2=1 линий сетки вправои нарисуйте узел и переместите курсор рисования оставшиеся 1 линии сетки вправо, чтобы закончить узел.Итак, следующий узел имеет width 4, что означает, что мы идем вправо 4/2 = 2 линии сетки, рисуем, делаем оставшиеся 2 шага и т. Д.
И так далее со следующимлиния.В конце (или в промежуточных шагах) соедините узлы.
Эта процедура гарантирует, что не будет перекрывающихся узлов (если линии сетки находятся достаточно далеко друг от друга), но это может привести к довольно большим диаграммам деревакоторый мог бы использовать пространство более эффективно.
Чтобы обнаружить неиспользуемое пространство, можно просто отсканировать линии после описанного выше процесса и посмотреть, есть ли неиспользуемые пересечения линий сетки, а затем, возможно, перестроить некоторые узлы, чтобы заполнитьпространство.