Как нарисовать структуру дерева? (Двухрежимный алгоритм рекурсии дерева размещения?)

Question

У меня есть произвольная древовидная структура узлов. Я хочу нарисовать это дерево, чтобы предоставить пользователям визуальное представление. Мне нужно переустановить дерево и для каждого узла добавить графический элемент в список, а затем просто нарисовать список элементов после завершения рекурсии дерева. Рекурсия и рисование элементов, конечно, тривиальны - что немного сложнее, так это расположение графических узлов, чтобы они не перекрывались с другими ветвями.

Я использую Android, но это не важно. Я ищу подход, возможно, алгоритм, который может поддерживать изображение двумерного пространства при его прохождении по дереву, поэтому он просто выделяет наиболее подходящие координаты для каждого как он делает проход.

Любые идеи?

Update

This is the article with the best and most complete algorithm.

Answer 1

Я бы попробовал алгоритм Уокер. Here's an academic paper по алгоритму. Если вы хотите, чтобы код выглядел, просмотрите NodeLinkTreeLayout в Prefuse. Prefuse является открытым исходным кодом, поэтому не должно возникать проблем с адаптацией кода к вашей ситуации, если вы соблюдаете условия лицензии.

Answer 2

Посмотрите на Dot. Вы можете преобразовать свое дерево в представление точки, а затем использовать Graphviz визуализируйте в любом формате, который вам нравится. Например, Doxygen использует его для представления структуры программы.

Answer 3

Graphviz и mfgraph являются мощными, но они предназначены для общих графиков и, вероятно, слишком малы для деревьев.

Попробуйте поиск по дереву + макет + алгоритм или см. Graphic Javascript Tree with Layout. Последний старый, но он использует HTML-холст и javascript, и он объясняет код, поэтому и код, и подход должны быть переносимыми.

Answer 4

Предлагаю рисовать дерево. Вы делаете это, используя какой-то движущийся «рисовочный курсор».

Можно хранить атрибут width для каждого узла, который рассчитывается следующим образом:

• width из отпуска составляет 1
• width из внутреннего узла сумма всех ДЕТСКИЕ width сек

Затем вы нарисуете корень «в первой строке» посередине, а это значит, что вы просто берете корневую часть 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 ых в виде суммы от детей width s:

+-------9--+-------+ 
    |   |  | 
+-2-+  +-+4+-+ +-3-+ 
| |  | | | | | | | 
1 1  1 1 1 1 1 1 1 

Итак, вы начинаете с корня (width 9) и пройдите 4,5 шага к rigt в первой строке.

Затем вы перемещаете «курсор рисования» во вторую строку «столбец 0» (слева направо).

Первый ребенок имеет width 2, поэтому мы идем по 2/2=1 линиям сетки вправо и нарисуем узел и передвигаем курсор рисования на оставшиеся 1 линии сетки вправо, чтобы закончить узел. Итак, следующий узел имеет width 4, что означает, что мы идем справа 4/2 = 2 линии сетки, рисуем, идем оставшиеся 2 шага и т. Д.

И так далее со следующей строкой. В конце (или в промежуточных шагах) соедините узлы.

Эта процедура гарантирует отсутствие перекрывающихся узлов (если линии сетки находятся достаточно далеко друг от друга), но это может привести к созданию довольно больших древовидных диаграмм, которые могли бы использовать пространство более эффективно.

Чтобы обнаружить неиспользуемое пространство, можно просто отсканировать строки после описанного выше процесса и посмотреть, нет ли пересекающихся линий пересечения сетки, а затем, возможно, перестроить некоторые узлы, чтобы заполнить пробел.

Answer 5

В зависимости от характера ваших данных, TreeMap может быть более подходящим, чем представление tinkertoy.