Бинарное дерево

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

В рекурсивном определении бинарное дерево состоит из корня и двух бинарных поддеревьев – левого и правого, причем любое из них сожжет быть пустым, то есть .

Несмотря на иерархическую структуру бинарные деревья не являются подмножеством упорядоченных корневых деревьев.

Пример

a a a

b b b

различные бинарные деревья эквивалентное упорядоченное

Приведенные примеры двух бинарных деревьев различны по структуре. Корень первого из них имеет только левое поддерево. Корень второго из них имеет только правое поддерево.

В общем случае различие между корневым деревом и бинарным состоит в том, что каждая вершин корневого дерева может иметь произвольное число поддеревьев, в то время как вершина бинарного дерева может иметь 0, 1 или 2 поддерева. Кроме того, у бинарных деревьев существуют различия между правым и левым поддеревьями.

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

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

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

Пример

Преобразуем 4-х уровневое корневое дерево в бинарное

1 1

2 3 4 2 3 4

5 8 9

5 6 7 8 9 6 7

Организация данных с помощью бинарных деревьев позволяет сократить время обработки данных.