Большинство алгоритмов работы с деревьями основаны на обходах. Возможны следующие основные обходы бинарных деревьев:
Прямой (левый) обход:
попасть в корень,
обойти левое поддерево,
обойти правое поддерево.
Обратный обход (симметричный или внутренний порядок):
обойти левое поддерево,
попасть в корень,
обойти правое поддерево.
Концевой (правый) обход:
обойти левое поддерево,
обойти правое поддерево,
попасть в корень.
Данное описание обходов фактически дает алгоритм обхода с рекурсией. Другими словами, Вы пишете функцию, которая для решения задачи в какой-то момент вызывает сама себя. При таком вызове в стеке создается новый набор локальных переменных, так что, по сути, можно считать, что вызывается другая функция. Единственное о чем следует побеспокоиться при использовании рекурсии, − чтобы вызовы функций самой себя не привели бы к переполнению стека (стек ≈ 64Кбайт). Однако, при большом количестве узлов, скажем, порядка 106, обеспечение этого требования становится проблематичным. Поэтому, приведем алгоритм симметричного обхода без рекурсии.
Алгоритм. Нумерация узлов двоичного дерева в соответствии с обходом по внутреннему порядку.
Вход. Двоичное дерево, представленное массивами ЛЕВЫЙ_СЫН и ПРАВЫЙ_БРАТ.
Выход. Массив, называемый НОМЕР, такой, что НОМЕР(i) — номер узла i во внутреннем порядке.
Метод. Кроме массивов ЛЕВЫЙ_СЫН, ПРАВЫЙ_БРАТ и НОМЕР, алгоритм использует переменную СЧЕТ, значение которой — номер очередного узла в соответствии с внутренним порядком. Начальным значением переменной СЧЕТ является 1. Параметр УЗЕЛ вначале равен корню. При прохождении дерева в стеке запоминаются все узлы, которые еще не были занумерованы и которые лежат на пути из корня в узел, рассматриваемый в данный момент. При переходе из узла v к его левому сыну узел v запоминается в стеке. После нахождения левого поддерева для v узел v нумеруется и выталкивается из стека. Затем нумеруется правое поддерево для v. При переходе из v к его правому сыну, узел v не помещается в стек, поскольку после нумерации правого поддерева мы не хотим возвращаться в v. Более того, мы хотим вернуться к тому предку узла v, который еще не занумерован (т.е. к ближайшему предку w узла v, такому, что v лежит в левом поддереве для w).
Пример. На рисунке ниже изображено двоичное дерево, узлы которого пронумерованы в соответствии с прохождением его по внутреннему порядку:
Если все узлы занумерованы в порядке посещения, то рассмотренные нумерации обладают рядом интересных свойств.
Номера узлов двоичного дерева, соответствующие внутреннему порядку, обладают тем свойством, что номера узлов в левом поддереве от узла v меньше, чем в v, а в правом поддереве больше v. Таким образом, чтобы найти узел с номером w, надо сравнить w с корнем r. Если w = r, то искомый узел найден. Если w < r, то надо повторить этот процесс для левого поддерева; если w > r, то повторить процесс для правого поддерева. В конце концов, узел с номером w будет найден или придем к ситуации, когда этого узла нет в дереве.