Алгоритм для Рендеринга Горизонтального Дерева Двоичного выхода в форме текста/ASCII

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

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

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

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

редактировать: хорошо, я не мог устоять перед попыткой написать какой-нибудь непроверенный псевдокод, надеюсь, он сработает:

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

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

Если вы начнете с ширины метки для каждого уровня (не включая [] символов), то она будет равна самой большой метке для этой ширины (в этом примере ширина обычно равна 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]

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

• Дерево представлено в виде объектов из классов, которые наследуются от узла
• Сначала вычислите количество листьев и создайте массив из этого количества строк
• Затем для каждого уровня:
  • выяснить, в каких строках мы собираемся записать
  • для этих строк, вычислить максимум того, что уже есть в этих строках
  • записать все узлы в столбец 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;
            }
        }
    }
}

РЕДАКТИРОВАТЬ : ваше примерное дерево отображается точно так же, как и ваше:

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