9.3.3. Обходы бинарных деревьев

Большинство алгоритмов работы с деревьями основаны на обходах. Возможны следующие основные обходы бинарных деревьев:

Прямой (левый) обход: попасть в корень,

обойти левое поддерево,

обойти правое поддерево.

Обратный (симметричный) обход: обойти левое поддерево,

попасть в корень,

обойти правое поддерево.

Концевой (правый) обход: обойти левое поддерево,

обойти правое поддерево,

попасть в корень.

Кроме трех основных, возможны еще три соответствующих обхода, отличающих­ся порядком рассмотрения левых и правых поддеревьев. Этим исчерпываются обходы, если в представлении фиксированы только связи «отец-сын».

ЗАМЕЧАНИЕ

Если кроме связей «отец-сын» в представлении есть другие связи, то возможны и другие (более эффективные) обходы. «Деревья», в которых пустые поля l и r в структуре N используются для хранения дополнительных связей, называются прошитыми деревьями.

Пример

Концевой обход дерева выражения а+ b с дает обратную польскую запись этого выражения: abc.

ОТСТУПЛЕНИЕ

Польская запись выражений (прямая или обратная) применяется в некоторых языках программирования непосредственно и используется в качестве внутреннего представле­ния программ во многих трансляторах и интерпретаторах. Причина заключается в том, что такая форма записи допускает очень эффективную интерпретацию (вычисление зна­чения) выражений. Например, значение выражения в обратной польской записи может быть вычислено при однократном просмотре выражения слева направо с использованием одного стека. В таких языках, как Forth и PostScript, обратная польская запись исполь­зуется как основная.