Упорядоченные и бинарные деревья

Ордерево Т — это конечное множество узлов, таких что:

1) Имеется один узел r, называемый корнем данного дерева.

2) Остальные узлы (исключая корень) содержатся в k попарно непересекающихся множествах Т_1,...,T_k, каждое из которых является ордеревом (k ³ 0).

Множества T₁,..., Т_k в эквивалентном определении ордерева являются поддере­вьями. Если относительный порядок поддеревьев T₁,...,T_k фиксирован, то ор­дерево называется упорядоченным.

Ориентированные и упорядоченные ориентированные деревья интенсивно ис­пользуются в программировании.

1. Выражения. Для представления выражений языков программирования, как правило, используются ориентированные упорядоченные деревья. Пример представления выражения а + b с показан на рисунке (слева).

2. Структура вложенности каталогов и файлов в современных операционных системах является упорядоченным ориентированным деревом.

3. Различные «уравновешенные скобочные структуры» (например, (a(b)(c(d)(e)))) являются ориентированными упорядоченными деревьями.

Бинарное дерево — это конечное множество узлов, которое либо пусто, либо со­стоит из корня и двух непересекающихся бинарных деревьев — левого и правого.

Бинарное дерево не является упорядоченным ордеревом.

Пример: На рисунке приведены две диаграммы деревьев, которые изоморфны как упорядо­ченные, ориентированные и свободные деревья, но не изоморфны как бинарные деревья.

Пример бинарного (слева) и упорядоченного дерева (справа):