Бинарные деревья

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

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

Пример

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

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

 

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