Archives

Archives / 2012 / October
  • Обход бинарного дерева с помощью итератора

    Tags: вопросы на собеседовании, структуры данных, алгоритмы

    Исходники для статьи

    Недавно мне пришлось проходить собеседование в Microsoft. По моим впечатлениям, я проявил себя довольно неплохо, но взяли другого разработчика, который по каким-то причинам подошёл лучше меня. Интервьюировали меня в несколько этапов. Задания и вопросы, в отличии от большинства вопросов в наших компаниях, были интереснее и разумнее, что-ли. Поэтому мне захотелось опубликовать серию статей с разбором заданий. Сегодня я рассмотрю задание, с частью которого я не справился, но хорошенько подумав на досуге нашёл хорошее решение.

    Задание, собственно, было такое. Напишите класс-итератор для обхода бинарного дерева. Первую половину – обход дерева breadth-first traversal – я решил довольно быстро, а вот со второй – inorder depth-first traversal возникли проблемы. Выполнить какое-либо действие (например, распечатать значение поля данных узла) для всех узлов с помощью рекурсии не представляет проблем, а вот с итератором у меня что-то не заладилось.

    Теория

    Для начал немного теории. Бинарное дерево – древовидная структура данных, в которой каждый узел имеет не более двух потомков (детей). Как правило, первый называется родительским узлом, а дети называются левым и правым наследниками.

    Далее по тексту я буду использовать следующее бинарное дерево.

    binary-tree-1

    Read more...