Имеет ли смысл реализовывать итераторы для контейнеров, у которых нет очевидного конца - например, деревья?

Question

Я пишу шаблон бинарного дерева поиска по двум причинам - изучая C ++ и изучая наиболее распространенные алгоритмы и структуры данных.
Итак, вот вопрос - до тех пор, пока я хочу реализовать итераторы, мне кажется, что нет строгого определения того, где заканчивается дерево. Каковы ваши предложения? Как мне это сделать?

Answer 1

Для деревьев существуют стандарты обхода дерева, то есть перечисления узлов: обход по предварительному заказу, обход по порядку и обход по порядку. Вместо того, чтобы описывать все это здесь, я перенаправлю вас на http://en.wikipedia.org/wiki/Tree_traversal. Концепции в основном применяются к бинарным деревьям, но вы можете распространить идею на произвольные деревья, добавив больше случаев: фактически, обработайте узел затем рекурсивный, рекурсивный, затем обрабатывает узел, обрабатывает всех потомков, затем рекурсивный в каждый ... и т. д. Я не знаю никакой канонической классификации этого подхода.

Answer 2

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

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

1. Где начинается итерация коллекции (root? Leaves?)
2. Как итерация переходит к следующему элементу (инфикс? Постфикс? Суффикс? Ширина?)
3. Когда заканчивается итерация (выходит? Root? Final node?)

Что бы вы ни выбрали, вы должны четко понимать, как вы называете (и документируете) свой итератор, чтобы было понятно, как он будет посещать и испускать узлы.

Возможно, вам придется написать несколько итераторов для разных типов путешествий, которые вы намереваетесь поддерживать. Здесь есть несколько хороших статей, которые обсуждают модели обхода дерева .

Answer 3

Если под «строгим» вы подразумеваете: одно всеобъемлющее определение, вы правы, его нет.

Но «конец» для деревьев очень хорошо определен, хотя и зависит от выбранного вами метода обхода.

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

Наиболее распространенные методы обхода дерева .

Answer 4

Ваше определение итератора немного неверно. Итераторы не переходят от start к finish и front до back . Вместо этого они проходят через всех членов этой структуры.

Если вы попросите выполнить итерацию по упорядоченной структуре, то есть массиву, связанному списку и т. Д., Вы (как правило) вернете своих членов по порядку.

Для неупорядоченных элементов, например набора, вы получите их в любом порядке, который итератор набора хочет вам предоставить, но вы получите их все по одному, точно так же, как вы это сделаете с массивом-итератором.

Что касается деревьев, другие люди уже упоминали: у них есть четко определенные понятия общего порядка, вам просто нужно выбрать одно:)

Answer 5

Я думаю, что в итераторе более абстрактно. Я не вижу в шаблоне итератора ничего, что действительно говорит о начале или конце! Так почему же ограничиваться этим видением. Мы можем представить себе итератор, который касается только следующего элемента, вот и все. Я имею в виду, что я сталкивался (особенно в массовой обработке) с ситуациями, когда с самого начала мы не знаем расширение коллекции, мы не знаем, закончится ли она когда-нибудь или у нас нет всех элементы загружаются в память, и нам все равно. Мы заботимся только о получении следующего элемента. В одной из этих реализаций следующий узел создается сразу после вызова метода следующего элемента. Мы можем открыть свои умы и думать о бесконечных коллекциях (в конце концов, коллекция - это тип математического набора), таких как коллекции всех чисел, коллекция всех случайных чисел. Вам не обязательно иметь все элементы в памяти (это очевидно для бесконечных коллекций). Конечно, это не практические примеры, но мое сообщение таково, что пользователю Итератора не нужно полагаться на фактическую структуру или расширение коллекции. ПРОСТО ДАЙ МНЕ СЛЕДУЮЩЕЕ (ЕСЛИ ТЫ ЕСТЬ).

Answer 6

Имеет смысл , особенно в подобных случаях, потому что дает пользователям вашего класса возможность легко обходить все элементы различными способами, в зависимости от ситуации. Без них пользователи должны сами писать сложными, обычно рекурсивными способами. По сравнению, например, с векторы, в которых итераторы набирают больше, чем используют для (i = 0; i

Answer 7

Это зависит от того, что вы хотите сделать с деревом - может быть, было бы неплохо иметь, например, итераторы Breadth-First-Search или Depth-First-Search (или оба).

Если у вас есть какой-то особый способ прочесать дерево, то в действительности у вас есть начало и конец. Это не так очевидно, как линейные отношения в списках и наборах, но оно есть, если вы хотите наложить на него некоторый порядок.