Килиманджаро
Фотограф Divyan Khoda.
Фотограф Divyan Khoda.
Просто фотографии без политики и рейтингов. Просто я люблю свой вид из окна. Когда я просыпаюсь и пью утренний кофе я смотрю в окно и вижу вековые сосны. Да они покрыты зимним песком смешанным с реагентом и солью, но они выживают и каждый год становятся все красивее. Но ни кто не знает, через какую боль проходят наши подмосковные деревья. Их пытаются разрушить все, но они перерабатывают боль и возрождаются с новой силой. И мой утренний кофе становится просто допингом от мысли, что деревья намного сильнее наших жизней!
В прошлой части мы ознакомились с базовыми понятиями деревьев и обошли одно дерево рекурсией. В данной статье мы еще раз рассмотрим понятие рекурсии и посмотрим как небольшие во время итерации могут повлиять на результат. В данной части мы сфокусируемся на итерации, а в следующе мы уже будем использовать эти подходы для решения задач.
Обход деревьев часто ощущается как лабиринт
Давайте рассмотрим уже знакомое дерево:
В прошло части мы уже итерировались по дереву рекурсивно. В нем мы сначала печатали значение узла (Node) затем посещаем левое поддерево (Left) и лишь потом правое поддерево (Right). Такой подход называется прямым или еще префиксным - NLR.
Распечатка значения и последующее движение влево вниз и уже затем вправо.
Теперь сделаем одно минимальное изменение - сначала мы пойдем в левое поддерево (Left) затем распечатаем значение узла (Node) и потом пойдем в правое поддерево (Right) - этот обход называют Инфиксным (от лат. in внутри fixus закрепленный) или центрированным - LNR. Понятие инфиксный прошло из математики. Если очень упрощать значит что N находится между L и R.
разница лишь в 1 линии но процес "обхода" меняется.
И так вроде рекурсия выполнила ровно такой же обход, но теперь процесс распечатки значения узла мы стали делать после того как уходим "влево". Теперь если задуматься то первая печать произойдет лишь когда мы дойдем до нижнего левого узла. Давайте изобразим как будет выглядеть "обход" а порядок печати значений узлов:
Думаю уже понятно что данный подход подразумевает печать значения узла (Node) после посещения левого (Left) поддерева и правого (Right) поддерева - LRN
Печатаем лишь после обхода левого и затем правого поддеревьев.
Порядок распечатки изображен ниже:
Изза минимальных изменений (меняя лишь порядок одной строчки) мы получили разные обходы дерева. Это позволит нам решать разные задачи в будущем.
В следующей статье мы рассмотрим какие задачи мы можем решать используя описанные подходы. Одна из главных целей цикла статей - помочь преодолеть страх задач про деревья во время собеседований. Думаю стоит повторить еще раз - как только вам прилетела задача на деревья во время собеса начинайте с того что напишите функцию обхода. Большинство алгоритмических задач решается именно через рекурсию (но не только через неё).
Кому интересна промышленная разработка и Java приглашаю в мою группу. Спасибо за внимание.