Рисование иерархического дерева: отображение дерева

Question

Я пытаюсь разработать представление иерархического дерева, в котором вес каждого узла равен фактическому количеству дочерних узлов. Листовой узел имеет вес 1.

Я хочу расположить эти элементы так, чтобы их можно было просматривать, углубляясь в дерево, показывая корневые категории (без родительского элемента) в начале. Нажатие на узел заставляет представление перерисовывать себя, чтобы показать только потомков этого узла.

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

В качестве примера приведу программу для Mac Os X под названием GrandPerspective , которая показывает размеры папок вашего HD :

_{(источник: arstechnica.com )}

Я хочу расположить узлы таким образом! (размер, конечно, пропорционален размеру папки)

Есть предложения?

Спасибо

Answer 1

Это квадратная древовидная карта. Вы можете прочитать статью , объясняющую эту технику.

Answer 2

Структура данных, используемая в примере файловой системы, который вы показываете, скорее всего, KD tree . Я не совсем уверен, насколько хорошо проблема, которую вы хотите решить, сопоставляется с примером файловой системы, но именно так я бы сам решил проблему с файловой системой:

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

1. Для файлов размер - это размер файла
2. Для каталогов размер - это полный размер всех файлов, которые он содержит (включая все его подпапки, их подпапки и т. Д.).

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

Базовые случаи будут:

1. В списке только один файл. Затем вы заполняете прямоугольник цветом типа файла.
2. В списке есть один каталог. Для этого случая вы запускаете алгоритм рекурсивно для содержимого в каталоге внутри прямоугольника.

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

РЕДАКТИРОВАТЬ: проблема расщепления называется раздел и представляет собой особый случай рюкзака. Это покрыто этим потоком здесь, на SO.