Постановка задачи
Буквально несколько дней назад Eric Lippert на своем блоге Fabulous Adventures In Coding опубликовал очень простую, но занимательную задачку:
Есть дерево, заданное с помощью класса Node, в котором есть Children с теми же самыми Node и какой-то Text (чуть ниже приведу код класса). Необходимо сгенерировать строку такого вида (включая переносы строк):
Использовать нужно юникодовые символы "│ ├ ─ └" (вспомним старые добрые картинки с псевдографикой). Цель, которую поставил себе Эрик — выяснить, какие предпочтения будут сделаны при составлении решения: рекурсивное (так как дерево), более быстрое или более читабельное.
 
Код исходного класса Node:
class Node<br>{<br> public Node(string text, params Node[] children)<br> {<br> this.Text = text;<br> this.Children = children ?? new Node[] {};<br> }<br> public string Text { get; private set; }<br> public IList<Node> Children { get; private set; }<br>}<br><br>* This source code was highlighted with Source Code Highlighter.
Исходные данные:
var root = new Node("a", <br> new Node("b",<br> new Node("c", <br> new Node("d")),<br> new Node("e",<br> new Node("f"))),<br> new Node("g", <br> new Node("h",<br> new Node("i")),<br> new Node("j")));<br><br>* This source code was highlighted with Source Code Highlighter.
Задача заполнить пропущенные строки тут:
sealed class Dumper<br>{<br> static public string Dump(Node root) { /* ... */ }<br> /* ... */ <br>}<br><br>* This source code was highlighted with Source Code Highlighter.
Решения
Так, как я не нашел тега "<spoiler>" у хабрапарсера, и не хочу приводить решения в открытом виде. Чтоб не лишать удовольствия от написания собственного решения, я приведу ссылки на эти свои решения и немного поясню.
Но я бы все-таки посоветовал потратить десяток минут на написание своего решения. Если нет IDE или лень запускать, рекомендую Snippet Compiler (хотя он только для .NET 3.5, для 4.0 я не нашел ничего аналогичного — чтоб с code completition, без создания файлов).
Первый подход
Сначала я для себя поставил задачу пойти наиболее LINQ-way, абсолютно не учитывая скорость выполнения. Вышло довольно интересно — linq-подобный вариант. В коде есть как рекурсивная энумерация всех узлов дерева, так и итеративная. Прошу отметить, что вычисление происходит «лениво», все строки собираются или StringBuilder'ом или с помощью LinkedList и потом собираются Join'ом, что позволяет минимизировать лишнее копирование строк или сдвиг массивов.
Вариант вышел медленным. Очень.
Второй подход
Ленвые вычисления и т.д. конечно красиво, но захотелось написать наиболее оптимальную по скорости реализацию. Отметив, что «уровневый» отступ всегда одинаковый, и его мы можем использовать каждый раз при добавлении нового уровня, решил оформить это вот в такой вариант. Все в одной функции, добавлен только вспомогательный класс-контейнер. То же StringBuilder, но, на этот раз, решил отказаться от каких либо массивов для кусков индентов. И снова таки никакой рекурсии — проход по дереву и построение результата происходит одновременно.
Данный вариант отказался совсем хорошим в плане скорости выполнения. Сразу забегу чуть вперед, скажу что он даже иногда быстрее варианта Эрика на «широких» (т.е. тех, в которых больше children'ов, чем глубина).
Решение Эрика
Ну и решение Эрика. Как ни странно, в нем я нашел много из того, что я сделал в своем «быстром» решении — например, то как он проверяет последний ли элемент в списке «детей» или нет.
Лично мне эта задачка понравилась тем, что пару раз приходилось решать что-то похожее. Да и размять мозги приятно.
Если кто придумает более быстрый вариант — напишите, интересно еще посмотреть на подходы к оптимизации C# кода. И хотя пост похож на то, что пишут в «Спортивном программировании», но, мне кажется, тут слишком простая задача, чтоб сравнивать реализации с другими платформами и языками.
Кроме того, возможно, мой пост поможет кому-то найти интересные подходы, которые можно использовать в других задачах: энумерация дерева с помощью IEnumerable как рекурсивно, так и нет; построение строк с помощью LinkedList и может еще что-то.
Ну а у тех, кому задачка показалась тривиальной, и решения ничем не интересны, прошу прощения за потраченное время.
Upd:
Модифицированный вариант Эрика от lam0x86 в виде только одной функции: Смотреть
Два очень лаконичных варианта от steck активно использующих Linq: Смотреть