Отображение дерева в старом стиле

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

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

Вот мой класс Node:

 class Node
{
    public Node(string text, params Node[] children)
    {
        this.Text = text;
        this.Children = children ?? new Node[] {};
    }
    public string Text { get; private set; }
    public IList<Node> Children { get; private set; }
}

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

Мое задание вам – реализовать следующий метод:

 sealed class Dumper
{
    static public string Dump(Node root) { /* ... */ }
    /* ... */ 
}

таким образом, чтобы метод Dump выдавал строку следующего вида:

a

├─b

│ ├─c

│ │ └─d

│ └─e

│   └─f

└─g

  ├─h

  │ └─i

  └─j

если ему на вход передать следующее дерево:

 var root = new Node("a", 
    new Node("b",
        new Node("c", 
            new Node("d")),
        new Node("e",
            new Node("f"))),
    new Node("g",     
        new Node("h",
            new Node("i")),
        new Node("j")));

Обратите внимание, что я использую юникодные символы для рисований линий и рамок (“box drawing” symbols) │ ├ ─ └. Я пользовался ими для разработки подобных интерфейсов пользователя еще в те дни, когда писал под Commodore 64. Ох уж эти безмятежные дни моей юности.

Свое решение я разместил здесь, но давайте НЕ ПОДГЛЯДЫВАТЬ! Вначале напишите свое решение, и потом давайте сравним его с моим.

Когда я рассказывал о раскраске графа / решения головоломки Sudoku в июле, я анализировал дизайнерские решения, которые принимал в процессе решения задачи. Какие ваши критерии при решении этой задачи? Например, собираетесь ли вы автоматически использовать рекурсивное решение, поскольку задачи с деревьями наиболее просто решаются при помощи рекурсии? Или вы воспользуетесь итеративным решением? Вы предпочтете, очевидно, корректное решение хитроумному или наоборот? Будет ли вам не хватать указателя на родительский узел? И так далее. Мне будет интересно, какие дизайнерские решения вы примите.

Ну, поехали!

Оригинал статьи

Comments

• Anonymous
  October 10, 2010
  Я на хабре опубликовал эту задачу и там запостили оч-чень элегантное решение: habrahabr.ru/.../104241

• Anonymous
  October 11, 2010
  Вот процедура которая использует два экземпляра StringBuilder для меньшего расхода памяти на строки indent. static public string Dump(Node root) { var result = new StringBuilder(); var indent = new StringBuilder(); Action<Node> dumpNode = null; dumpNode = node => { result.AppendLine(node.Text); var lastIndex = node.Children.Count - 1; for (var i = 0; i < lastIndex; i++) { result.Append(indent); result.Append("├─"); indent.Append("│ "); dumpNode(node.Children[i]); indent.Length = indent.Length - 2; } if (lastIndex >= 0) { result.Append(indent); result.Append("└─"); indent.Append("  "); dumpNode(node.Children[lastIndex]); indent.Length = indent.Length - 2; } }; dumpNode(root); return result.ToString(); }