Обход бинарного дерева

Обход бинарного дерева предполагает посещение всех вершин бинарного дерева, при этом каждая из вершин посещается только один раз.

Существуют три вида таких обходов, каждый из которых определяется рекурсивно :

• прямой порядок ( англ. preorder ) следующей последовательности:
  1. посетить корень
  2. посетить левое поддерево
  3. посетить правое поддерево

  То есть, в таком порядке обхода каждая вершина посещается до того, как будут посещены ее дети.

• обратный порядок ( англ. postorder ) следующей последовательности:
  1. посетить левое поддерево
  2. посетить правое поддерево
  3. посетить корень

  То есть, в таком порядке каждая вершина посещается лишь после того, как будут посещены ее дети.

• центрированный (центральный) порядок ( англ. inorder ) следующей последовательности:
  1. посетить левое поддерево
  2. посетить корень
  3. посетить правое поддерево

  В таком порядке каждая вершина посещается между посещением левой и правой ребенка. Такой порядок особенно часто применяется в бинарных деревьях поиска, так как дает возможность обхода вершин в порядке увеличения их порядковых номеров.

Пример

Для этого бинарного дерева, Прямой порядок: 2, 7, 2, 6, 5, 11, 5, 9, 4 Обратный порядок: 2, 5, 11, 6, 7, 4, 9, 5, 2 Центрированный (центральный) порядок: 2, 7, 5, 6, 11, 2, 5, 4, 9