Форум Flasher.ru - Алгоритмы Как построить дерево?

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - [Алгоритмы] Как построить дерево? (http://www.flasher.ru/forum/showthread.php?t=210623)

Как построить дерево?

До этого никогда не работал с деревьями и четыре дня пытался сделать по найденным алгоритмам, но все они не отвечали тем требованиям, которые я к ним предъявлял. Но сегодня я нашел изображение, которое меня полностью устроило, но как построить подобное, я даже в уме не представляю.
По этому, если кто-то делал подобное, то объясните на словах , как рассчитать подобное дерево.
И если Вы знаете и хотите мне помочь, то у меня ещё одна к Вам просьба - помните что я до этого с деревьями не работал и что нуждаюсь в подробном объяснении.

И ещё вопрос по теме - у деревьев бывает ширина и высота и если да, то что это?

Про рекурсию и обходы дерева тоже не знаете?

Цитата:

Про рекурсию и обходы дерева тоже не знаете?

Смотря о чем Вы. Обойти рекурсивно дерево для меня не проблема. Но я слышал о деревьях ( не знаю как они называются ) где есть ссылки право, лева, низ, верх.. Вот у меня не такое дерево, а просто ноды которые на нативный Sprite похожи.
Так вот количество детей считать - могу! Получалось пирамидками детей выстраивать при помощи рекурсии, но как уже сказал ранее, меня получившееся представление не устроило и я пошел дальше.
Так что можно с натяжкой сказать, что минимум манипуляций в рекурсии я умею.

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

Вот... Жду помощи.

Ничего не понял из вопроса.
Что Вы имеете в виду, говоря "рассчитать дерево"?
Что такое "алгоритмы" в данном контексте? Что они делают?
Что именно представляют из себя "те требования, которые я к ним предъявлял"?

Дерево оно и есть дерево. Каждый узел имеет ссылку на parent — родительский узел, и массив ссылок на children — узлы детей, для которых он в свою очередь parent.
Вариантом может быть дополнительная классификация узла как "лист", то есть не имеющий детей, конечный узел. То есть можно создать класс Leaf, имеющий ссылку только на parent, и расширяющий его класс Node, имеющий так же массив ссылок на детей и методы для работы с ними (добавление/удаление, сортировка, подсчет количества, поиск по свойствам).

Добавлено через 1 минуту

Цитата:

я не могу подобрать алгоритм, который бы выстраивал ноды в такой последовательности.

В смысле "сортировал по алфавиту" что ли?

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

Цитата:

Что Вы имеете в виду, говоря "рассчитать дерево"?

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

Цитата:

Что такое "алгоритмы" в данном контексте? Что они делают?

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

Цитата:

Что именно представляют из себя "те требования, которые я к ним предъявлял"?

Только сейчас дошло, что у меня наверное просто не получалось. Ведь как отображение не крути,
а ведь все равно только так, как в данном примере и можно отобразить.

Еще, только сейчас понял, что я неправильно работаю с деревьями, вообще не умею.
Чтобы найти расположение чилда, нужно знать длину его чилдов ( если они есть ) и следовательно его и его чилдов. По этому я подошел неправильно и сделал деспатч изменения длины вверх по дереву:) Но это все равно мне не помогло.
Да и нарисовать с конца тоже не могу, не могу даже представить как узнать координаты зная только.. Я даже не знаю, что нужно знать. А когда смотрю ещё и на картинку, особенно на увеличенную, то вообще не понимаю, почу в один раз нода без детей в центре между двумя с детьми, а в другой раз, если нет боковой с детьми, прижимается дефолтное расстояние..

Добавлено через 14 минут
olexandr, как я написал в той теме, я отказался от этой библиотеки из-за устаревшего демо и невозможности посмотреть исходники, так как библиотека написана на haxe, на который я сейчас смотрю, как когда-то, да и сейчас, на php с его -> вместо точки. Неделю я не могу понять как так нарисовать, зато вдоволь с рекурсией наигрался.

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

Я потыркался, вроде и получается, но есть исключения и мне их уже лень думать сегодня. Если хоть как-то
приблизит вас к решению, буду рад. Справа кнопка рефреша. Комменты напишу и баги поправлю потом, если будет нужда. Общая идея - уходим до листиков, рисуем их, потом по усредненному Y рисуем их веточку, веточки дают среднюю Y для ветки их и так далее. Но гд-то явно прогибы есть, голова уже не варит, но задача прикольная.

tree2.swf (1.9 Кб)

Код AS3:

package 

{

        import flash.display.Graphics;

        import flash.display.Sprite;

        import flash.events.MouseEvent;

        import flash.geom.Point;

 

        /**

         * ...

         * @author gbee

         */

        public class TreeTest extends Sprite 

        {

                 private static const VGAP:int = 15;

                private static const HGAP:int = 50;

                private var _levelsOffset:Array;

 

                private var _g:Graphics;

                public function TreeTest() 

                {

                        super();

 

                        var spr:Sprite = new Sprite();

                        spr.graphics.beginFill(0, 0.4);

                        spr.graphics.drawRect(800, 0, 100, 40);

                        spr.addEventListener(MouseEvent.CLICK, refresh);

                        addChild(spr);

                        refresh();

                }

 

                private function refresh(event:MouseEvent = null):void

                {

                        _g = graphics;

                        _g.clear();

                        _g.beginFill(0x008800);

                        _g.lineStyle(1, 0x004400);

                        _levelsOffset = [0, 0, 0, 0, 0, 0, 0, 0, 0];

                        drawTree(generateTree(5, 3), 0);

                }

 

                private function generateTree(maxChilds:int, level:int):TreeNode

                {

                        var childsCount:int = int(Math.random() * maxChilds);

                        var node:TreeNode = new TreeNode();

                        if (level == 0)

                                return node;

                         for (var i:int = 0; i < childsCount; i++)

                                node.children.push(generateTree(maxChilds, level - 1));

                        node.count = childsCount;

                        return node;

                }

 

 

                private function drawTree(node:TreeNode, level:int):Number

                {

                        var levelY:Number = 0; 

                        if (node.count)

                        {

                                var linesY:Array = []; //массив Y для рисования связей.

                                for each(var child:TreeNode in node.children)

                                {

                                        var cY:Number = drawTree(child, level + 1);

                                        levelY += cY;

                                        linesY.push(cY);

                                }

                                _levelsOffset[level + 1] += VGAP;

 

                                levelY = levelY / node.count;

 

                                if(levelY - _levelsOffset[level] >= VGAP)

                                        _levelsOffset[level] = levelY;

                                else

                                {

                                        _levelsOffset[level] += VGAP;

                                        levelY = _levelsOffset[level];

                                }

 

                                //Рисуем связи

                                for each(cY in linesY)

                                {

                                        _g.moveTo(HGAP * level, levelY);

                                        _g.lineTo(HGAP * (level + 1), cY);

                                }

                        }

                        else

                        {

                                levelY = _levelsOffset[level]; 

                                _levelsOffset[level] += VGAP;

                                //Запрещаем рисовать ноды чужих детей выше себя. Но тут надо подумать в примере не запрещено.

                                if(_levelsOffset[level + 1] < _levelsOffset[level])

                                        _levelsOffset[level + 1] = _levelsOffset[level];

                        }

 

                        //Рисуем ноду

                        _g.drawCircle(HGAP * level, levelY, 5);

                        return levelY;

                }

 

 

        }

 

}

Код AS3:

package 

{

        /**

         * ...

         * @author gbee

         */

        public class TreeNode 

        {

                public var children:Array = [];

                public var count:int = 0;

                public function TreeNode() 

                {

 

                }

 

        }

 

}

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