Алгоритм рендеринга горизонтального бинарного дерева в текстовой / ASCII-форме

Question

Это довольно обычное двоичное дерево, за исключением того факта, что один из узлов может быть пустым.

Я хотел бы найти способ вывести его горизонтально (то есть кореньузел находится слева и расширяется вправо).

У меня был некоторый опыт расширения деревьев по вертикали (корневой узел вверху, расширение вниз), но я не уверен, с чего начать, в этомcase.

Предпочтительно, он будет следовать следующим правилам:

• Если у узла есть только один дочерний элемент, он может быть пропущен как избыточный («конечный узел», безchildren, всегда отображается)
• Все узлы одинаковой глубины должны быть выровнены по вертикали;все узлы должны находиться справа от всех менее глубоких узлов и слева от всех более глубоких узлов.
• Узлы имеют строковое представление, которое включает их глубину.
• Каждый «конечный узел» имеетсобственная уникальная линия;то есть количество строк - это число конечных узлов в дереве, и когда конечный узел находится в строке, после этой конечного узла в этой строке может не быть ничего другого.
• Как следствиепоследнее правило, корневой узел может быть лучше в верхнем левом или нижнем левом углу;предпочтительным является верхний левый.

Например, это допустимое дерево с шестью конечными узлами (узел представлен именем и его глубиной): РЕДАКТИРОВАТЬ: см. нижнюю часть вопросадля более простого рендеринга

[a0]-----------[b3]------[c5]------[d8]
    \              \         \----------[e9]
     \              \----[f5]
      \-[g1]--------[h4]------[i6]
            \           \--------------------[j10]
             \-[k3]

, который представляет вертикальное явное двоичное дерево:

0              a
              / \
1            g   *
            / \   \
2          *   *   *
          /     \   \
3        k       *   b
                /   / \
4              h   *   *
              / \   \   \
5            *   *   f   c
            /     \     / \
6          *       i   *   *
          /           /     \
7        *           *       *
        /           /         \
8      *           *           d
      /           /
9    *           e
    /
10 j

(ветви сложены для компактности; * представляет избыточный, одно-дочерние узлы; обратите внимание, что * являются фактическими узлами, каждый из которых содержит по одному дочернему узлу, только с именами, опущенными здесь для удобства представления)

(также, чтобы уточнить, я хотелдля генерации первого, горизонтального дерева, а не этого вертикального дерева)

Я говорю не зависимо от языка, потому что я просто ищу алгоритм;Я говорю ruby, потому что в конечном итоге мне все равно придется реализовать его в ruby.

Предположим, что каждая Node структура данных хранит только свой идентификатор, левый узел и правый узел.

Мастер Tree класс отслеживает все узлы и имеет адекватные алгоритмы для поиска:

• n-й предок узла
• n-ный потомок узла
• Всепотомки конечного узла узла и их количество
• Генерация узла
• Самый низкий общий предок двух заданных узлов

I ужезнать :

• Количество конечных узлов

У кого-нибудь есть идеи, с чего можно начать?Должен ли я пойти на рекурсивный подход?Повторяющийся?Какой-то Psuedo-код тоже был бы довольно крутым, и его очень ценят =)

---

progress

По предложению walkytalky, я решил посмотреть, как он будет выглядетьнравится отображать каждый «релевантный» или значимый узел в сетку, где столбцы являются глубиной, а строки - идентифицируемыми по их конечным узлам.Вот что происходит (пропуская столбец 7, потому что в глубине 7 нет значимых узлов):

depth: 0  1  2  3  4  5  6  8  9  10
       a        b     c     d
                               e
                      f
          g        h     i
                                  j
                k

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

Теперь, зная эти факты:

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

Мы можем видеть, что для любой действительной сетки существует один однозначный способ , так сказать, «соединить точки»;здесь представлено одно недвусмысленное дерево.

Теперь «соединение точек» больше не является вопросом бинарной древовидной структуры ... это просто вопрос декорирования.Нам просто нужно построить алгоритм для правильного размещения правильных - и \, куда они могут пойти, возможно, следуя только простым сеткам / лексикографическим правилам вместо двоичной древовидной структурыправила.

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

Может кто-нибудь предложитьспособ формулирования этих правил?Или, может быть, совершенно другой метод?

---

edit

Я задумал намного, гораздо более простой финальный рендеринг:

--d0----d1----d3----d4----d5----d6----d8----d9----d10-- => guide line (not rendered)

 [a0 ]-------[b3 ]-------[c5 ]-------[d8 ]
   |           |           \---------------[e9 ]
   |           \---------[f5 ]
   \---[g1 ]-------[h4 ]-------[i6 ]
         |           \---------------------------[j10]
         \---[k3 ]

--d0----d1----d3----d4----d5----d6----d8----d9----d10-- => guide line (not rendered)

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

Answer 1

Если имеются N конечные узлы, то должно быть N-1 внутренних узлов с 2 дочерними узлами. (Может быть любое количество внутренних узлов с 1 дочерним элементом, которые мы должны будем посчитать, чтобы получить глубины, но в противном случае проигнорируем.) Таким образом, создание дерева эквивалентно расположению этих узлов в сетке, где:

• количество строк в сетке N
• I думаю, количество столбцов находится между 1+floor(log2(N)) и 2*N-1, в зависимости от степени перекрытия; это, вероятно, не имеет большого значения для наших целей, хотя
• каждая конечная точка появляется в отдельной строке
• все узлы с одинаковой глубиной отображаются в одном столбце
• все внутренние узлы отображаются в той же строке, что и их крайняя правая нижняя точка

Итак, давайте посмотрим:

• Пройдите по дереву сначала вглубь, справа налево.
• Для каждой конечной точки запишите ее глубину и метку.
• Для каждого 2-дочернего внутреннего элемента запишите его глубину, метку и индексы как самой правой, так и самой левой дочерних конечных точек.
• Сортировка всей партии по глубине - это дает вам порядок столбцов с количеством различных глубин, дающих фактическое количество столбцов. (Думаю, что все остальные упорядочения должны исходить автоматически с прогулки, но здесь дело обстоит не так, потому что любая ветвь может быть любой глубины.)
• Поместите все узлы в сетку.
• Пометить пустые ячейки справа от каждого не конечного узла как горизонтальные ветви.

• Пометить пустые ячейки вниз от каждого внутреннего узла до строки над его левым потомком как вертикальные ветви, а ячейку на уровне левого потомка - как соединение.

• Печать с соответствующим декором ASCII.

Обновление:

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

Я вроде думал, что печать достаточно тривиальна, чтобы затушевать, но:

• Перейдите вниз по каждому столбцу и определите ширину столбца как size of fixed elements + max label length + floor(log10(depth) + 1). (Например, фиксированные элементы могут быть [ и ]-. Мы можем заменить ]\n в качестве суффикса для конечных точек.)
• Для каждого ряда
  • для каждого столбца
    • если ячейка содержит узел или конечную точку
      • печать фиксированного префикса
      • печать этикетки
      • глубина печати
      • пробелы для печати (максимальная длина этикетки - текущая длина этикетки)
      • напечатать соответствующий суффикс
      • если узел является конечной точкой, перейти к следующей строке
    • если ячейка пуста, вывести пробелы на ширину столбца
    • если ячейка содержит вертикаль, вывести номер выбранного префикса с пробелами, чертой и заполнить пробелами
    • если в ячейке содержится соединение, выведите несколько префиксов, количество пробелов, обратную косую черту и заполните дефисами
    • если ячейка содержит горизонталь, вывести полную ширину столбца дефисов

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

В какой-то момент я могу попытаться вставить это в код, но, вероятно, этого не произойдет сегодня - чем заняться!

Answer 2

Если вы начнете с ширины метки для каждого уровня (не включая [] символов), равной наибольшей метке для этой ширины (в этом примере ширина в основном равна 2, за исключением j10, который равен 3, и уровням 2и 7, которые равны 0).

Каждый уровень с ненулевой максимальной шириной метки должен быть равномерно распределен по одному символу - между уровнями, чтобы вы могли рассчитать начальный уровень y местоположений.

Дайте каждому узлу свой номер строки.

Затем настройте расположение уровней на основе максимального количества линий между дочерними элементами для уровня.

Добавлено 2 к уровню 1для a0 до g1
Добавлено от 1 до уровня 2 для от g1 до k3
Добавлено от 1 до уровня 4 для от b3 до []

Использование \ и ` символов для диагоналей.

[a0]---------[b3]-------[c5]------[d8]
    \            \          `----------[e9]
     \            `-----[f5]
      `[g1]--------[h4]------[i6]
           \           `--------------------[j10]
            `[k3]

Answer 3

Ниже приведен полностью функциональный код C #, который делает именно то, что вы хотите.Как это происходит:

• Дерево представлено в виде объектов из классов, которые наследуются от Node
• Сначала вычислите количество листьев и создайте массив из такого количества строк
• Затем для каждого уровня:
  • выясните, на каких строках мы будем писать
  • для этих строк, вычислим максимум того, что уже на этих строках
  • записать все узлы в столбец max (номер предыдущего шага, конец предыдущего уровня) +1;добавьте -, чтобы добраться до этого столбца.
  • записать диагональные линии от всех двоичных узлов до линии их правого потомка (в моей программе первый потомок левый, второй правый, у тебя это другой путьвокруг)
  • продвинуться на один уровень

Алгоритм гарантирует, что каждый уровень начинается только после предыдущего окончания.Это, вероятно, хороший выбор для коротких имен, но для более длинных имен это, вероятно, не следует применять.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SO_ASCII_tree
{
    class Program
    {
        static void Main()
        {
            Node root = …;

            StringBuilder[] lines = Enumerable.Range(0, root.Leaves).Select(i => new StringBuilder()).ToArray();

            Node[] currentLevel = new Node[] { root };
            int level = 0;
            int min = 0;
            int max = 0;
            while (currentLevel.Any())
            {
                NamedNode[] namedNodes = currentLevel.OfType<NamedNode>().ToArray();
                if (namedNodes.Any())
                {
                    min = namedNodes.Select(node => lines[node.Line].Length).Max();
                    min = Math.Max(min, max);
                    if (min != 0)
                        min++;
                    foreach (NamedNode namedNode in namedNodes)
                        WriteAtPosition(lines[namedNode.Line], namedNode.Write(level), min, '-');
                    max = namedNodes.Select(node => lines[node.Line].Length).Max();
                    // change to max = min + 1; for long names
                }

                foreach (Node node in currentLevel)
                    node.SetChildLines();

                Binary[] binaries = namedNodes.OfType<Binary>().ToArray();
                foreach (Binary binary in binaries)
                    GoDown(lines, binary.Line, binary.Right.Line);

                currentLevel = currentLevel.SelectMany(node => node.Children).ToArray();
                level++;
            }

            foreach (StringBuilder line in lines)
                Console.WriteLine(line.ToString());
        }

        static void WriteAtPosition(StringBuilder line, string message, int position, char prepend = ' ')
        {
            if (line.Length > position)
                throw new ArgumentException();
            line.Append(prepend, position - line.Length);
            line.Append(message);
        }

        static void GoDown(StringBuilder[] lines, int from, int to)
        {
            int line = from + 1;
            int position = lines[from].Length;
            for (; line <= to; line++, position++)
                WriteAtPosition(lines[line], "\\", position);
        }
    }

    abstract class Node
    {
        public int Line
        { get; set; }

        public abstract int Leaves
        { get; }

        public abstract IEnumerable<Node> Children
        { get; }

        public virtual void SetChildLines()
        { }
    }

    abstract class NamedNode : Node
    {
        public string Name
        { get; set; }

        public string Write(int level)
        {
            return '[' + Name + level.ToString() + ']';
        }
    }

    class Binary : NamedNode
    {
        public Node Left
        { get; set; }
        public Node Right
        { get; set; }

        int? leaves;
        public override int Leaves
        {
            get
            {
                if (leaves == null)
                    leaves = Left.Leaves + Right.Leaves;
                return leaves.Value;
            }
        }

        public override IEnumerable<Node> Children
        {
            get
            {
                yield return Left;
                yield return Right;
            }
        }

        public override void SetChildLines()
        {
            Left.Line = Line;
            Right.Line = Line + Left.Leaves;
        }
    }

    class Unary : Node
    {
        public Node Child
        { get; set; }

        int? leaves;
        public override int Leaves
        {
            get
            {
                if (leaves == null)
                    leaves = Child.Leaves;
                return leaves.Value;
            }
        }

        public override IEnumerable<Node> Children
        {
            get
            {
                yield return Child;
            }
        }

        public override void SetChildLines()
        {
            Child.Line = Line;
        }
    }

    class Leaf : NamedNode
    {
        public override int Leaves
        {
            get
            {
                return 1;
            }
        }

        public override IEnumerable<Node> Children
        {
            get
            {
                yield break;
            }
        }
    }
}

EDIT : ваше дерево примеров отображается точно так же, как и ваше отображение:

[a0]-----------[b3]------[c5]------[d8]
    \              \         \----------[e9]
     \              \----[f5]
      \-[g1]--------[h4]------[i6]
            \           \--------------------[j10]
             \-[k3]

Answer 4

похоже на интересную проблему;Я был бы рад попробовать, если бы у меня было больше времени.

Я бы, вероятно, выбрал следующий подход:

1. Начать рендеринг "правильно" (или вв вашем случае "верхние") узлы, пока я не дойду до конца.(то есть: рендеринг a, b, c и d)
2. Вернитесь к последнему узлу с дочерним элементом (то есть: c) и сделайте то же самое рекурсивно

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

edit: ок, не устоял при попытке написать какой-то непроверенный псевдокод, надеюсь, он работает:

function print_tree(Node n) {
    print "\n" // begin on a fresh new line
    childs = new Array();
    do {
        if (n.hasLeftChild) {
            childs.push(n.leftChild)
        }
        print "---" + n.id    //this needs a lot of tweaking, but you get the idea
    } while(n = n.rightChild)
    childs.reverse()
    foreach(child in childs) {
        print_tree(child);
    }
}

Answer 5

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