Литература Сущность рекурсии

Алгоритм обхода в прямом порядке:

• 
  Попасть в корень,
  
• 
  Пройти все поддеревья слева на право в прямом порядке.
  

Данный алгоритм рекурсивен, так как прохождение дерева содержит прохождение поддеревьев, а они в свою очередь проходятся по тому же алгоритму.
В частности для дерева на рис. 3 и 4 прямой обход дает последовательность узлов: A, B, C, D, E, F, G.
Получающаяся последовательность соответствует последовательному слева направо перечислению узлов при представлении дерева с помощью вложенных скобок и в десятичной системе Дьюи, а также проходу сверху вниз при представлении в виде уступчатого списка.
При реализации этого алгоритма на языке программирования попадание в корень соответствует выполнение процедурой или функцией некоторых действий, а прохождение поддеревьев – рекурсивным вызовам самой себя. В частности для бинарного дерева (где из каждого узла исходит не более двух поддеревьев) соответствующая процедура будет выглядеть так:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

// Preorder Traversal – английское название для прямого порядка procedure PreorderTraversal({Аргументы}); begin //Прохождение корня DoSomething({Аргументы}); //Прохождение левого поддерева if {Существует левое поддерево} then PreorderTransversal({Аргументы 2}); //Прохождение правого поддерева if {Существует правое поддерево} then PreorderTransversal({Аргументы 3}); end;

То есть сначала процедура производит все действия, а только затем происходят все рекурсивные вызовы.
Алгоритм обхода в обратном порядке:

• 
  Пройти левое поддерево,
  
• 
  Попасть в корень,
  
• 
  Пройти следующее за левым поддерево.
  
• 
  Попасть в корень,
  
• 
  и т.д пока не будет пройдено крайнее правое поддерево.
  

То есть проходятся все поддеревья слева на право, а возвращение в корень располагается между этими прохождениями. Для дерева на рис. 3 и 4 это дает последовательность узлов: B, A, D, C, E, G, F.
В соответствующей рекурсивной процедуре действия будут располагаться в промежутках между рекурсивными вызовами. В частности для бинарного дерева:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

// Inorder Traversal – английское название для обратного порядка procedure InorderTraversal({Аргументы}); begin //Прохождение левого поддерева if {Существует левое поддерево} then InorderTraversal({Аргументы 2}); //Прохождение корня DoSomething({Аргументы}); //Прохождение правого поддерева if {Существует правое поддерево} then InorderTraversal({Аргументы 3}); end;