Здравствуйте, Pavel Dvorkin, Вы писали:

PD>Здравствуйте, samius, Вы писали:

S>>Элементы он не создает. Создаются лишь итераторы, которые при необходимости можно расположить в стеке. Размер итератора вот только побольше 4х байт, но абсолютно точно не зависит ни от размера дерева ни от размера элемента дерева, т.е. O(C).

PD>Вот это я все же не понимаю. Ладно, оставим LinQ в покое.
Да это не LINQ вовсе. Из LINQ-а там только Concat, который легко реализуется на yield return, который в свою очередь генерирует код конечного автомата для реализации IEnumerator<T>.

PD>Проитерируй мне это несчастное дерево императивным путем.
Да легко. Вместо yield return будет callback и всего лишь.

        static void Walk<T>(Node<T> root, Action<Node<T>> callback)
        {
            callback(root);

            if (root.Left != null)
                Walk(root.Left, callback);
            if (root.Right != null)
                Walk(root.Right, callback);
        }

Здесь я слил специфичный для Node<T> селектор с обходом в единое целое чтобы полностью избавиться от IEnumerable. Алгоритм остался идентичным, только стал более низкоуровневый.

PD>Я-то, грешный, прошел его рекурсией. Мне не надо извне его уметь следующий элемент получить, я это только внутри него самого делаю. И итератора там нет. Я вообще понятие "следующий" явно не использую. А вот попроси ты меня

PD>root = BuildTree();
PD>tree_iterator te = tree_iterator(root);
PD>for(t = te.begin; t!=t.end; t++)

PD>написать, и все будет хуже. Это не список и не массив, тут позицией или индексом не обойдешься. Тут мне придется внутри этого итератора стек хранить, да как бы не что-то еще. Скорее всего придется еще поле Parent добавить, иначе как к нему возвращаться ?
В случае C# (достаточно 2.0) это все на раз-два реализуется с помощью yield return. Стэк перетекает в цепочку связанных перечислителей, Parent не нужен. Можно было бы и на C# 1.0, но пришлось бы вместо yield return реализовывать IEnumerator вручную.

S>>Последовательность как контейнер НЕ создается. Последовательность как способ обхода — создается.

PD>Вот это я и не понимаю. Можно создать последовательность как способ обхода для массива — i++. Для списка p=p.next. Тут никакие дополнительные структуры не требуются.
IEnumerator/IEnumerable — высокоуровневая абстракция над i++ и p=p.next

PD>А в дереве это не получится.
Получится в виде комбинации перечислителей.

PD>Так что твоя последовательность как способ обхода есть по сути дела некая управляющая структура над эти деревом. И как тут может быть O(C) — не понимаю, если в императивном O(log N).
Каждый из перечислителей занимает O(C) места. Но их комбинация будет O(log N). Т.е. ровно как и в императиве. Просто стек перерождается в другую структуру, которая полностью ему соответствует с тем лишь отличием, что будет работать отложенно, а не сразу.

PD>К примеру, я мог бы обойти это дерево как написал и выложить все указатели в массив. После этого пройти итератором будет несложно, но это не решение.
Согласен, это другое решение. Вместо этого можно было воспользоваться callback-ом для поиска минимального элемента без копирования элементов в какой-либо контейнер.

S>>Мы можем по ней пройти через foreach

PD>Вот-вот. each что ? Управляющий элемент для каждого элемента дерева ?
Each — это подузлы. Но управляющая структура все-же создается при прохождении в foreach. См. IEnumerable/IEnumerator.

PD>Это все слова. Да, я понял, что Where тут не контейнер. Отлично. Но начнешь итерировать — будет там ++ где-то внутри какого-то регистра или индекса, и не надо никаких новых байт для этого. Но в дереве же такое невозможно!

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