Я думаю что это то что я искал, большое спасибо!
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Визуализация небинарного дерева |
| Автор: SavotinArtem 4.5.2006, 12:43 |
| Здравствуйте! Есть вопрос: Меня интересует алгоритм визуализации небинарного дерева на 2х мерной плоскости. Кто-нибудь может написать просто название алгоритма или предложить идеи. Я хочу получить что то типо как: http://www.yworks.com/products/yfiles/doc/api/y/layout/tree/doc-files/y.layout.tree.TreeLayouter.gif Я уже реализовал такой алгоритм но он очень сложный и при большом количестве элементов долго пересчитывается. Вот пример моего алгоритма(возможно я придумываю велосипед, но в гугле ничего не нашел по этому пришлось придумывать свое): Т.е. к примеру у меня есть небинарное дерево: Я обозначаю root дерева как 0, далее иду по дереву и обозначаю элементы как -1 0 1, -2 -1 0 1 и.т.д т.е. в конце концов я работая с двухмерным массивом: 0 -1 0 1 -2 -1 1 0 0 -1 0 1 вычисляю пересечения и двигаю ветви влево или вправо рекурсивно и т.д. Но это слишком сложный алгоритм и занимает много вычислительного времени, по этому я ищу более простой алгоритм, желательно в один два обхода. Спасибо! |
| Автор: nostromo 4.5.2006, 15:05 |
| Кажется, можно предложить алгоритм в два рекурсивных обхода. Сначала для каждого узла считаем "ширину" соответствующего поддерева (как самму ширин дочерних поддеревьев. Ширину бездетного узла полагаем равной 1), а вторым обходом собственно размещаем относительно заданной точки. |
| Автор: belonesox 4.5.2006, 15:07 |
| Возможно не стоит изобретать велосипед, а стоит посмотреть исходники http://www.graphviz.org/ (http://lib.custis.ru/index.php/Graphviz)? Т.е. планаризация ориентированных и неориентированных графов. |
| Автор: SavotinArtem 4.5.2006, 15:24 |
| Это Супер! Я думаю что это то что я искал, большое спасибо! |