LINUX.ORG.RU

алгоритм рисования дерева


0

0

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

P.S. можно писать не мыло eugenf23@mail.ru

anonymous

Re: алгоритм рисования дерева

Ну, мне в голову пришел такой вариант:
на первом шаге загоняем в список корень дерева и рисуем его.
На 2-м шаге загоняем в список всех "детей" корня, попутно рисуя их.
Затем удаляем первый элемент списка (это корень).
На n-шаге для каждого элемента текущего списка загоняем в конец списка
его "детей", рисуя их. Можно сразу удалять эту вершину. Переходим к следующему элементу списка и делаем то же самое. И так далее, пока на переберем число элементов списка, которое было в начале этой n-ой итерации. Ну и так далее.
Дерево будет расти от корня, отрисовываясь уровень за уровнем.

JekLove ()
Ответ на: Re: алгоритм рисования дерева от JekLove

Re: Re: алгоритм рисования дерева

Т.е. BFS?

Мне кажется что проблема не в обходе дерева, а в отображении 
элементов. Если имеем дерево ( т.е ацикличный граф ) с максимальной
шириной узла k, то можно решить проблему за 2 прохода:

Проход 1: Принимаем координаты вершины за 0,0 и обходим дерево с 
помошью BFS. Во время прохода запоминаем крайние координаты (minX, 
minY, maxX, maxY )

Проход 2: Принимаем  minX,minY за 0,0 , обходим список элементов 
( полученный в результате 1-го прохода ) и отрисовываем элементы 
со сдвигом minX, minY.  При необходимости масштабируем координаты.


Однако данный подход может страдать излишеством в случае более
умной графической библиотеки.

omerm ()

Re: алгоритм рисования дерева

Усложняем задачу :-). Корень дерева находиться в центре экрана и элементы должны рисоваться во все стороны. Дело в том, что у меня есть реализация и для случая рисования вниз и для случая рисования по кругу, но эта реализация моя. У нее куча проблем, хоть она и более сложная чем указанные алгоритмы и потому мне интересны именно алгоритмы "профессиональные".

anonymous ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.