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

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

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

Пример

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

Рис. 9.9. Два различных бинарных дерева

ЗАМЕЧАНИЕ Понятие двоичного допускает обобщение, т-ичным деревом называется конечное множество узлов, которое либо пусто, либо состоит из корня и т непересекающихся т- ичных деревьев, имеющих номера 1,...,т. Большая часть утверждений и алгоритмов для двоичных деревьев может быть сравнительно легко распространена и на т -ичные деревья (с соответствующими модификациями). Поэтому, хотя на практике т -ичные деревья и используются достаточно часто, здесь мы ограничиваемся только двоичными деревьями.

Представление деревьев в компьютере

Обсуждению представлений деревьев можно предпослать в точности те же рассуждения, что были предпосланы обсуждению представлений графов (см. 7.4). Кроме того, следует подчеркнуть, что задача представления деревьев в программе встречается гораздо чаще, чем задача представления графов общего вида, а потому методы ее решения оказывают еще большее влияние на практику программирования.