Алгоритм визуализации дерева

Question

Есть ли какой-нибудь алгоритм для визуализации древовидной структуры данных?Я попробовал поискать в Google, но не смог найти.Я почти уверен, что должен быть какой-то алгоритм для этой не такой простой задачи.Или у кого-нибудь есть идеи?

Answer 1

Предположение: вы хотите, чтобы каждый узел отображался так, чтобы он находился по центру над его дочерними узлами.

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

Это приводит к:

width = 1 + sum(widths of children's nodes)

Итак, сделайте обход в глубину по дереву, чтобы вычислить ширину каждого узла. Для отображения выполните обход в ширину, чтобы нарисовать уровень дерева по уровню.

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

Answer 2

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

Здесь есть несколько альтернатив.

Здесь - хороший список статей и другой информации по теме.

Answer 3

Вы можете использовать язык DOT, например, с Graphviz.

Answer 4

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

print(node, spaces):
    if node has left child:
        print(left_child, spaces + '    ')
    print spaces + node + '\n'
    if node has right child:
        print(right_child, spaces + '    ')

Этот алгоритм будет печатать один узел дерева на строку.Каждый уровень дерева будет отступать вправо на несколько пробелов.Этот алгоритм будет печатать элементы в порядке возрастания, но в порядке убывания можно сначала обработать нужного потомка.