Обходы дерева как рекурсивной структуры данных

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

1. Прямой обход:

— обработать узел;

— посетить в прямом порядке каждого сына.

2. Обратный обход:

— посетить в обратном порядке каждого сына;

— обработать узел.

3. Внутренний, или симметричный обход:

— посетить во внутреннем порядке левого сына:

— обработать узел.

— посетить во внутреннем порядке правого сына (остальных сыновей).

Минимальная обработка узла может состоять в присвоении соответствующему в нём полю номера в порядке посещения (разметка) или в выдаче номеров на экран, если они уже имеются, или в формировании последовательности из номеров посещённых узлов. Очевидно, что не существует иных способов отличить один порядок обхода узлов от другого.

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