2008, oбходы деревьев и Microsoft Denmark
В далеком 2008 году произошло мое первое интервью с крупной софтверной компанией, которое я (неудивительно) бездарно провалил еще на стадии телефонного интервью, т.к. интервьюировался до того только в Казахстане, да и вообще, имел довольно слабое представление о том, как интервьюируют серьезные компании, и к чему следует быть готовым.
И вот, когда меня попросили открыть систему для совместного редактирования кода и писать там решение задачи в процессе интервью, это для меня стало _очень_ большим сюрпризом. Тем не менее, это был, пожалуй, самый полезный фейл в моей жизни, после которого я сделал ряд важных выводов.
Тем не менее, возвращаясь к тому событию, хотелось бы рассмотреть задачу, которую я зафейлил, а также сходные задачи и их решения.
Задача довольно стандартная, реализовать обход дерева в порядке postorder без использования рекурсии. Postorder это один из трех стандартных вариантов обхода дерева, два других это preorder и inorder. В данном посте я рассмотрю решения для всех трех обходов без помощи рекурсии.
Wiki дает следующие русские термины для этих обходов:
preorder - предупорядоченный обход; postorder - поступорядоченный обход; inorder - симметричный обход.
Для решения всех трех обходов без рекурсии необходимо будет использовать стек, который, в определенном смысле, заменит стек выполнения, на котором основана работа рекурсивной программы.
1) Preorder - порядок обхода такой: нода, левое поддерево, правое поддерево.
В рамках данной задачи preorder - это самый простой случай, когда мы инициализируем стек корнем дерева, и затем в цикле будем брать элемент из стека, выводить его значение, и после добавлять в стек его правого, а затем левого потомка (для того, чтобы на следующей итерации мы бы вытащили левого потомка, и пошли по левому поддереву, а затем по правому).
Иллюстрировать тут, ИМХО, нечего, достаточно просто посмотреть на имплементацию.
https://gist.github.com/codekrolik/446b67b970d9c038d649
А вот здесь пост на leetcode на эту тему.
2) Postorder - порядок обхода такой: левое поддерево, правое поддерево, нода.
Реализовать такой обход сложнее, т.к. необходимо различать для нод с потомками, в какой момент доставаемую из стека ноду надо передобавить в стек с ее потомками, а в какой момент ее следует процессить в порядке обхода (в нашем случае - вывести ее значение на экран).
Логика для этого будет следующая: если мы достаем из стека ноду и предыдущая "обойденная" нода не является ее ребенком, то мы передобавляем ноду и ее детей в стек в следующем порядке: нода, правый ребенок, левый ребенок.
Если же предыдущая нода - ее ребенок, то мы процессим ее и уходим на следующую итерацию (к ее родителю, либо правому сиблингу). Даный прием гарантирует порядок процессинга, при котором сама нода будет отпроцессена лишь после того, как ее левый и правый дети будут отпроцессены.
Моя имплементация алгоритма:
https://gist.github.com/codekrolik/916286dac0524caee4f6
Это специальный пост из моего блога, где показано на примере, как работает стек в этом алгоритме.
А здесь пост на leetcode по этой теме.
3) Inorder - порядок обхода такой: левое поддерево, нода, правое поддерево.
С моей точки зрения, это самый хитрый обход в контексте реализации без рекурсии.
Решение можно представить следующим образом: для начала пройдем от корня по всем левым потомкам, добавляя их в стек. Когда мы дошли таким образом до листа дерева, необходимо вывести его, затем его родителя, и перейти на правое поддерево родителя, если таковое имеется.
Реализовать это можно это путем использования стека и дополнительной ноды (переменной). Инициализируем доп.ноду корнем дерева, и начнем действия в цикле по следующему алгоритму:
1) если доп.нода не NULL, добавим доп.ноду в стек, и изменим ее значение на левого ребенка.
2) если доп.нода NULL, вытащим ноду из стека, отпроцессим ее, и изменим значение доп. ноды на правого ребенка ноды из стека.
Таким образом, все ноды будут проходить следующий цикл:
1) запись ноды в доп.ноду;
2) добавление ноды в стек из доп.ноды, и запись левого ребенка в доп.ноду (т.е. левое поддерево будет отпроцессенно раньше, чем сама нода);
3) забирание (pop) ноды из стека, ее процессинг, и запись ее правого ребенка в доп.ноду. (т.е. правое поддерево будет отпроцессено сразу после того, как будет отпроцессена сама нода).
В случае если левый либо правый ребенок ноды отсутствуют, соответственно, левое/правое дерево будет проигнорировано, и цикл начнет получать ноды с предыдущего уровня из стека. Индикатором такой ситуации будет значение NULL в доп.ноде.
Моя имплементация:
https://gist.github.com/codekrolik/6f8fef669154f75b6316
Пост из моего блога с примером работы алгоритма.
А вот здесь тесты для всех реализаций обхода.
https://gist.github.com/codekrolik/ab806962e7e381c41cbf