Как расставить узлы произвольного дерева? [закрыт]

Есть произвольное дерево, узлы-братья удалены друг от друга на динамически задаваемое значение (в данном случаи 20), так же как и узлы-соседи (в данном случаи 40). В тот момент, когда самая левая ветвь формируется, вызывается метод расстоновка_узлов в который передается самый верхний-левый и самый верхний-правый и разница на которую увеличился промежуток между ними (в данном случаи 20). Вот что происходит в методе расстоновка_узлов -

в цикле проходим от верхний-левой до верхней-правой и считаем промежутки (в данном случаи это шесть пустых клеточек, которые как говорил ранее по 20, то есть сумма 120); делю сумму полученную на предыдущем шаге на кол-во узлов плюс один (120 / 3 = 40); проверяю на сколько текущий узел (я начинаю с лева на право и по этому текущий узел это тот у которого два ребенка) удален от левого узла-брата (в данном случаи это 80). теперь я вычитаю из 80 - 40 = 40, это значение расстояние на которое я смещу текущую ноду чтобы оказаться в нужном месте. если это значение (40) больше чем то на которое увеличилось расстояние между двумя крайними нодами, то это значение становится меньшим. То есть рассчитал что 40, но оно больше позволенного и по этому значение меняется на 20. перемещаю ноду.

Повторяю шесть предыдущих шагов для следующей ноды - 1. получаю 60 2. 60 / 2 = 30 3. 40 4. 30 5. 10 6. ...

Видите как я усреднил? Сначала выяснил что сдвинуть нужно на сорок, но так как на сорок сдвинуть я не могу (нарушится правило для нижних детей, они будут ближе чем на сорок), я сдвигаю на максиму возможное, это двадцать. А потом я сдвигаю уже на десять. Для примера, если бы у первой обрабатываемой ноды не было детей, то картина была бы следующей -
На тот случай, если у меня сначала идет узел который можно сдвинуть на "сколько-то" (без детей), а после тот который уже нельзя сдвинуть на "сколько-то", то второй я снова сдвигаю на максимум, но при этом выполняю алгоритм с самого начала (точнее с самой последней удачной точки), но на время подменяю самый верхний-правый текущим.
Я бы показал код, но я не хочу чтобы Вы смотрели его недочеты, а лишь хочу чтобы Вы поняли смысл.
Вот. Но дальше я столкнулся с следующей проблемой, да и возможно это только одна из ... Входные данные те же, но все ломается. Алгоритма, как я хотел, не получилось, да и придумать я не могу. Ниже конечный результат -
Что есть у нод indent - значение на которое текущая нода удалена от предыдущей ||->|| leftOffset - это значение на которое я смещаю влево. В самом начале оно ноль rightOffset = это то значение на которое смещаю вправо. И тоже по дефолту ноль.
Вот. Сами ноды, как обычные ноды, ссыдка на парента, в котором они хранятся в индексированном массиве. Есть методы для получения ноды по индексу и получение самого индекса.

Ответ

В общем, нужно расставлять узлы уже по факту, а не извращаться с двиганием в каких-то рамках. Есть обе константы, "братья" и "соседи", причем "соседи" определяет, насколько должны отстоять друг от друга соседние поддеревья на уровнях ниже первого, а "братья" - на первом. Тогда задачу нужно решать снизу вверх: для каждого поддерева вначале выстраиваем каждое из собственных поддеревьев, после чего выстраиваем текущее подерево, вычисляя для каждого следующего поддерева минимальное смещение относительно нуля, при котором на каждом уровне это поддерево не будет мешать уже установленным поддеревьям. В итоге каждое подерево будет иметь параметр "занятый диапазон" на каждом уровне, где у него есть хоть один лист, по нему и будет идти сравнение при размещении текущего поддерева на верхнем уровне.
Т.е. алгоритм выглядит так:
BuiltTree buildTree(Tree tree) { BuiltTree[] siblings; foreach (subTree in tree.subTrees) siblings.push(buildTree(subTree)); BuiltTree result=new BuiltTree(); // пустое foreach (sibling in siblings) { int minRightPos=0; for (i=0;iright заполняется следующим образом: Если добавляемое поддерево на i-m уровне не имеет заполненного right, то на i+1-m уровне right не изменяется, если же имеет, то right становится равным присланному offset плюс имеющийся right. left заполняется схожим образом, но заполняется, только если на данном уровне ещё не заполнен - так как новые поддеревья добавляюстя справа, первое поддерево с заданной глубиной установит left этому поддереву. При выполнении positionRoot() весь массив right и left уменьшается на position, после чего в начало массивов добавляется 0.
Попытаюсь описать разворачивание алгоритма. Для описания дерева буду использовать списки Лиспа, числа - листы, списки - поддеревья. Пример: ((1) (2 3 4 5)) соответствует такому дереву:
root | *-----* | +-+^+-+ 1 2 3 4 5
Исходное дерево: (((1) 2) (((3))) ((4 5 6) ((7 8 9) (10)))). Поддеревья из одного листа не рассматриваю, ибо незачем. Поддерево ((1) 2) имеет значение: left=[0,-10,-10]; right=[0,10,-10] и следующий вид:
* +^+ * 2 | 1
Звездочки обозначают вершины поддеревьев, так как в списках нет элемента "корень" . Поддерево (((3))) имеет тривиальный вид и значение массивов left=[0,0,0,0]; right=[0,0,0,0]. Поддерево ((7 8 9) (10)) имеет значение массивов left=[0,-30,-50]; right=[0,30,30] и выглядит так:
* +--^--+ * * +-+-+ | 7 8 9 10
Из-за того, что поддерево (7 8 9) получило right[1] как 20, а смещение "соседи" 40, второе поддерево было помещено по смещению 60 (0+40+20), а positionRoot был вызван со смещением 30 (=60/2), в итоге левое поддерево провалилось в минус относительно общего кроня на -50. Сборка поддерева 4-10 будет выглядеть так:
* +---^----+ * * +-+-+ +--^--+ 4 5 6 * * +-+-+ | 7 8 9 10
Ограничителем положения правого поддерева здесь выступает второй слой, где у (4 5 6) right[1]=20, а left[1] у поддерева -30, итого общее смещение будет 90. На нижнем уровне у левого поддерева нет элементов, поэтому его пропускаем. В итоге positionRoot будет вызван с положением 55, и общий массив выглядит как left=[0,-55,-75,5]; right=[0,55,85,85]. После чего сборка из трех поддеревьев будет выстроена так: первое ставится по смещению 0, второе (((3))) по смещению 50, и большое третье по смещению 50+40+(-75) = 165, и голова будет смещена на 87.5. Итого получится такая картина:
* +----+---^-------+ * * * +^+ | +---^----+ * 2 * * * | | +-+-+ +--^--+ 1 * 4 5 6 * * | +-+-+ | 3 7 8 9 10
Из-за округлений в третьем ряду между звездочкой и 4 четыре пробела вместо трех (я считал один символ = 10 точек, но я считал элементы не имеющими ширины, таким образом, вместо 20 и 40 в вопросе нужно ставить константы 40 и 60).
Надеюсь, понятно объяснил.
Апдейт: Технически можно после распределения поддеревьев таким образом искать те поддеревья, которые можно подвинуть внутри отображения, не мешая остальным, и если проблема именно тут, то её на самом деле нет, так как после расстановки всех поддеревьев получен наиболее компактный вариант размещения всего дерева в ширину, и если какие-то поддеревья можно двигать, т.е. у них появляется диапазон разрешенных позиций, вы можете использовать имеющийся у вас алгоритм. А то, что дерево в итоге очень громоздкое по ширине, это не является проблемой как таковой.