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

#алгоритм #дерево #графы

                            
             
                
                    
                        
                            Закрыт. Этот вопрос необходимо уточнить или дополнить
подробностями. Ответы на него в данный момент не принимаются.
                            
                        
                    
                
            
                    
                
                        
                            
                        
                    
                        
                            Хотите улучшить этот вопрос? Добавьте больше подробностей
и уточните проблему, отредактировав это сообщение.
                        
                        Закрыт 4 года назад.
                    
                
        

Есть произвольное дерево, узлы-братья удалены друг от друга на динамически задаваемое
значение (в данном случаи 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 = это то значение на которое смещаю вправо. И тоже по дефолту ноль.  

Вот. Сами ноды, как обычные ноды, ссыдка на парента, в котором они хранятся в индексированном
массиве. Есть методы для получения ноды по индексу и получение самого индекса.
    

Ответы

Ответ 1

В общем, нужно расставлять узлы уже по факту, а не извращаться с двиганием в каких-то
рамках. Есть обе константы, "братья" и "соседи", причем "соседи" определяет, насколько
должны отстоять друг от друга соседние поддеревья на уровнях ниже первого, а "братья"
- на первом. Тогда задачу нужно решать снизу вверх: для каждого поддерева вначале выстраиваем
каждое из собственных поддеревьев, после чего выстраиваем текущее подерево, вычисляя
для каждого следующего поддерева минимальное смещение относительно нуля, при котором
на каждом уровне это поддерево не будет мешать уже установленным поддеревьям. В итоге
каждое подерево будет иметь параметр "занятый диапазон" на каждом уровне, где у него
есть хоть один лист, по нему и будет идти сравнение при размещении текущего поддерева
на верхнем уровне.

Т.е. алгоритм выглядит так:

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