--- title: "2008, oбходы деревьев и Microsoft Denmark" description: "В далеком 2008 году произошло мое первое интервью с крупной софтверной компанией, которое я (неудиви..." author: "codekrolik" published: "2014-07-24T21:51:17+00:00" modified: "2014-07-24T22:59:06+00:00" locale: "ru" canonical_url: "https://yvision.kz/post/2008-obhody-derevev-i-microsoft-denmark-422553" markdown_url: "https://yvision.kz/post/2008-obhody-derevev-i-microsoft-denmark-422553/markdown" site_name: "Yvision.kz" --- # 2008, oбходы деревьев и Microsoft Denmark > В далеком 2008 году произошло мое первое интервью с крупной софтверной компанией, которое я (неудиви... В далеком 2008 году произошло мое первое интервью с крупной софтверной компанией, которое я (неудивительно) бездарно провалил еще на стадии телефонного интервью, т.к. интервьюировался до того только в Казахстане, да и вообще, имел довольно слабое представление о том, как интервьюируют серьезные компании, и к чему следует быть готовым. И вот, когда меня попросили открыть систему для совместного редактирования кода и писать там решение задачи в процессе интервью, это для меня стало _очень_ большим сюрпризом. Тем не менее, это был, пожалуй, самый полезный фейл в моей жизни, после которого я сделал ряд важных выводов. Тем не менее, возвращаясь к тому событию, хотелось бы рассмотреть задачу, которую я зафейлил, а также сходные задачи и их решения. Задача довольно стандартная, реализовать обход дерева в порядке postorder без использования рекурсии. Postorder это один из трех стандартных вариантов обхода дерева, два других это preorder и inorder. В данном посте я рассмотрю решения для всех трех обходов без помощи рекурсии. > [Wiki](http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_(%D1%81%D1%82%D1%80%D1%83%D0%BA%D1%82%D1%83%D1%80%D0%B0_%D0%B4%D0%B0%D0%BD%D0%BD%D1%8B%D1%85)#.D0.9C.D0.B5.D1.82.D0.BE.D0.B4.D1.8B_.D0.BE.D0.B1.D1.85.D0.BE.D0.B4.D0.B0) дает следующие русские термины для этих обходов: **preorder** - предупорядоченный обход; **postorder** - поступорядоченный обход; **inorder** - симметричный обход. Для решения всех трех обходов без рекурсии необходимо будет использовать стек, который, в определенном смысле, заменит стек выполнения, на котором основана работа рекурсивной программы. 1) Preorder - порядок обхода такой: нода, левое поддерево, правое поддерево. В рамках данной задачи preorder - это самый простой случай, когда мы инициализируем стек корнем дерева, и затем в цикле будем брать элемент из стека, выводить его значение, и после добавлять в стек его правого, а затем левого потомка (для того, чтобы на следующей итерации мы бы вытащили левого потомка, и пошли по левому поддереву, а затем по правому). Иллюстрировать тут, ИМХО, нечего, достаточно просто посмотреть на имплементацию. [https://gist.github.com/codekrolik/446b67b970d9c038d649](https://gist.github.com/codekrolik/446b67b970d9c038d649) А вот здесь [пост на leetcode](http://www.programcreek.com/2012/12/leetcode-solution-for-binary-tree-preorder-traversal-in-java/) на эту тему.   2) Postorder - порядок обхода такой: левое поддерево, правое поддерево, нода. Реализовать такой обход сложнее, т.к. необходимо различать для нод с потомками, в какой момент доставаемую из стека ноду надо передобавить в стек с ее потомками, а в какой момент ее следует процессить в порядке обхода (в нашем случае - вывести ее значение на экран). Логика для этого будет следующая: если мы достаем из стека ноду и предыдущая "обойденная" нода не является ее ребенком, то мы передобавляем ноду и ее детей в стек в следующем порядке: нода, правый ребенок, левый ребенок. Если же предыдущая нода - ее ребенок, то мы процессим ее и уходим на следующую итерацию (к ее родителю, либо правому сиблингу). Даный прием гарантирует порядок процессинга, при котором сама нода будет отпроцессена лишь после того, как ее левый и правый дети будут отпроцессены. Моя имплементация алгоритма: [https://gist.github.com/codekrolik/916286dac0524caee4f6](https://gist.github.com/codekrolik/916286dac0524caee4f6) Это [специальный пост](http://codekrolik.yvision.kz/post/422689) из моего блога, где показано на примере, как работает стек в этом алгоритме. А здесь [пост на leetcode](http://www.programcreek.com/2012/12/leetcode-solution-of-iterative-binary-tree-postorder-traversal-in-java/) по этой теме.   3) Inorder - порядок обхода такой: левое поддерево, нода, правое поддерево. С моей точки зрения, это самый хитрый обход в контексте реализации без рекурсии. Решение можно представить следующим образом: для начала пройдем от корня по всем левым потомкам, добавляя их в стек. Когда мы дошли таким образом до листа дерева, необходимо вывести его, затем его родителя, и перейти на правое поддерево родителя, если таковое имеется. Реализовать это можно это путем использования стека и дополнительной ноды (переменной). Инициализируем доп.ноду корнем дерева, и начнем действия в цикле по следующему алгоритму: 1) если доп.нода не NULL, добавим доп.ноду в стек, и изменим ее значение на левого ребенка. 2) если доп.нода NULL, вытащим ноду из стека, отпроцессим ее, и изменим значение доп. ноды на правого ребенка ноды из стека. Таким образом, все ноды будут проходить следующий цикл: 1) запись ноды в доп.ноду; 2) добавление ноды в стек из доп.ноды, и запись левого ребенка в доп.ноду (т.е. левое поддерево будет отпроцессенно раньше, чем сама нода); 3) забирание (pop) ноды из стека, ее процессинг, и запись ее правого ребенка в доп.ноду. (т.е. правое поддерево будет отпроцессено сразу после того, как будет отпроцессена сама нода). В случае если левый либо правый ребенок ноды отсутствуют, соответственно, левое/правое дерево будет проигнорировано, и цикл начнет получать ноды с предыдущего уровня из стека. Индикатором такой ситуации будет значение NULL в доп.ноде. Моя имплементация: [https://gist.github.com/codekrolik/6f8fef669154f75b6316](https://gist.github.com/codekrolik/6f8fef669154f75b6316) [Пост из моего блога](http://codekrolik.yvision.kz/post/422694) с примером работы алгоритма. [Пост на leetcode](http://www.programcreek.com/2012/12/leetcode-solution-of-binary-tree-inorder-traversal-in-java/). А вот здесь тесты для всех реализаций обхода. [https://gist.github.com/codekrolik/ab806962e7e381c41cbf](https://gist.github.com/codekrolik/ab806962e7e381c41cbf) --- Source: [https://yvision.kz/post/2008-obhody-derevev-i-microsoft-denmark-422553](https://yvision.kz/post/2008-obhody-derevev-i-microsoft-denmark-422553)