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


Таблица рекурсивных алгоритмов прохождения бинарного дерева (классификация по порядку прохождения ).

Таблица 1    
ПрямойСимметричныйКонцевой
1. Корень поддерева 1. Левое поддерево 1. Левое поддерево
2. Левое поддерево 2. Корень поддерева 2. Правое поддерево
3. Правое поддерево 3. Правое поддерево 3. Корень поддерева

Прямой порядок прохождения означает обход в направлении сверху-вниз, когда после посещения очередного разветвления продолжается прохождение вглубь дерева, пока не пройдены все потомки достигнутого узла. По этой причине прямой порядок прохождения часто называют нисходящим, или прохождением в глубину. Прямой порядок есть наиболее естественный способ перечисления узлов дерева в форме вложенных скобок или уступчатого списка. Если исключить все скобки и запятые, то последовательность узлов в форме вложенных скобок будет соответствовать прямому порядку прохождения дерева. Уступы в ступенчатом списке, представляющем любую иерархическую структуру, также располагаются в прямом порядке. В генеалогических терминах прямой порядок прохождения дерева отражает династический порядок престолонаследования, когда титул передается старшему потомку. При симметричном порядке дерево проходится слева-направо, порождая лексиграфически упорядоченную последовательность ключей узлов. По этой причине симметричный порядок прохождения часто называют лексиграфическим. В частности, такой способ прохождения бинарного дерева знаков зодиака располагает их названия в лексиграфическом порядке:

aquarius < aries < canser < capricorn < gemini < leo < ... < virgo

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

Рис. 1.  Траектория обхода бинарного дерева.

На этом рисунке стрелками обозначена траектория обхода бинарного дерева. Последовательности обработки узлов для бинарного дерева рассматриваемого примера при различных порядках прохождения сведены в таблицу на том же рисунке. По сложившейся традиции процедуры прохождения бинарного дерева в прямом, симметричном и концевом порядке принято называть PREORDER, INORDER и POSTORDER, соответственно, учитывая их применение для прохождения семантических деревьев, которые строятся для грамматического разбора арифметических выражений. Прохождение семантического дерева грамматического разбора в прямом, симметричном и концевом порядке представляет арифметическое выражение соответственно в префиксной, инфиксной и постфиксной форме. Независимо от конкретного приложения наиболее естественными являются рекурсивные варианты процедур прохождения бинарных деревьев, поскольку они как деревья относятся к классу объектов с рекурсивно определенной структурой. Как известно, процедура называется рекурсивной, если она явно или неявно, вызывает сама себя, порождая соответствующее число независимых последовательных активаций. При этом выполнение каждой предшествующей активации ожидает завершение последующей активации в той точке процедуры откуда она "самовызвана". Таким образом выполняется всегда только последняя активация, причем в контексте своих предшественников, которые находятся в состоянии ожидания завершения своих потомков.
Рекурсивные процедуры прохождения бинарных деревьев в различном порядке имеют сходную прямо-рекурсивную структуру, которая предусматривает явное обращение каждой из них к себе самой для левого и правого потомка текущего узла, а также обеспечивает нерекурсивную обработку текущего узла. Например, псевдокод процедуры INORDER для прохождения бинарного дерева в симметричном порядке содержит следующие операторы:

 IF THIS <> NULL THEN 
{ 
  INORDER (LEFT); /*рекурсия для левого потомка*/ 
  VISIT (THIS);   /*нерекурсивная обработка     */ 
  INORDER (RIGHT) /*рекурсия для правого потомка*/ 
  { 
  RETURN; 

Где THIS используется для ссылки на текущий узел дерева, LEFT и RIGHT - для идентификации левого и правого потомков текущего узла, а VISIT (THIS) обозначает процедуру функциональной обработки текущего узла.
При начальном обращении к процедуре INORDER ее аргумент должен идентифицировать корень бинарного дерева (root). Последующие рекурсивные вызовы порождают активации процедуры INORDER для различных потомков корня с целью прохождения бинарного дерева в требуемом симметричном порядке.
Важное преимущество рекурсивных алгоритмов по сравнению с традиционными итерационными - простота и выразительность вычислительной схемы. Чисто алгоритмически рекурсия всегда может быть использована вместо итерации для организации повторяющихся действий. С другой стороны рекурсия не всегда заменяется итерацией. Поэтому пока рекурсия доступна и эффективна, рекурсивные управляющие структуры более предпочтительны, чем их итерационные аналоги, особенно для обработки данных, структура которых определена рекурсивно.
Практическая эффективность использования рекурсии вместо итерации обусловлена возможностями программной реализации. При программной реализации эффективность рекурсии ограничена ресурсными сообщениями, которые связаны с необходимостью хранения во внутреннем стеке программы последовательности активаций вместе с необходимыми им значениями локальных переменных и аргументов рекурсивной процедуры. Поскольку размер внутреннего стека ограничен, то глубина рекурсии не может быть произвольной. Таким образом, если ожидается обработка значительных информационных массивов, когда ресурсные требования рекурсивной процедуры могут превысить размер программного стека то следует отдать предпочтение нерекурсивной версии алгоритма, как более эффективной и безопасной. Аналогичный выбор рекомендуется сделать, когда трудоемкость понимания рекурсивного и итерационного вариантов примерно равны.
Для сравнения, ниже приводится итерационный вариант процедуры INORDER прохождения бинарного дерева в симметричном порядке, где применяется собственный внешний стек вместо внутреннего стека в адресном пространстве программы рекурсивной процедуры. Псевдокод итерационной процедуры прохождения бинарного дерева в симметричном порядке образует следующие операторы:

 S <= (ROOT,1) 
  WHILE S <> 0 
  { 
  (THIS,i) <= S; 
  CASE i = 1 : S <= (THIS,2); VISIT (THIS) 
  CASE i = 2 : S <= (THIS,3); 
        IF LEFT <> NULL THEN S <= (LEFT,1); 
  CASE i = 3 : IF RIGHT <> NULL THEN S <= (RIGHT,1); 
  } 
  RETURN; 

В этом алгоритме дополнительно к обозначениям рекурсивного варианта вводится собственный стек S для хранения пар, состоящих из ссылки на текущий узел дерева THIS и целочисленной переменной i. Ее значение указывает, какую из 3-х операций прохождения нужно применить к текущему узлу, когда пара достигнет вершины стека и будет извлечена для обработки. Итерационные варианты 2-х других процедур прохождения бинарного дерева конструируются по сходной схеме. Необходимый объем памяти для внешнего стека в них может динамически распределяться из кучи или принадлежать сегменту данных из адресного пространства программы итерационной процедуры. В любом случае внешний стек итерационной процедуры менее чувствителен к ограничениям операционной среды, чем внутренний стек ее рекурсивного варианта. С другой стороны сравнительная оценка сложности обоих аналогов процедуры INORDER однозначно в пользу рекурсивного алгоритма.