[Алгоритмы] Как построить дерево?

[OlmerDale]

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

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

[GBee]

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

[OlmerDale]

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

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

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

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

[Wolsh]

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

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

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

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

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

[GBee]

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

[OlmerDale]

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

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

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

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

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

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

[olexandr]

http://www.flasher.ru/forum/showthread.php?t=210591

[OlmerDale]

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

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

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

[GBee]

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

tree2.swf   (1.9 Кб)

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;
		}
 
 
	}
 
}

package 
{
	/**
	 * ...
	 * @author gbee
	 */
	public class TreeNode 
	{
		public var children:Array = [];
		public var count:int = 0;
		public function TreeNode() 
		{
 
		}
 
	}
 
}

[OlmerDale]

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