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

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

Рис. 63. Дерево общего вида

 

Число поддеревьев данного корня (узла) называется степенью этого узла. Максимальная степень всех узлов дерева называется степенью дерева, обозначим d. Узел с нулевой степенью называется терминальным узлом или листом. Уровень узла – выраженная в числе ребер длина пути, ведущего из узла в корень дерева плюс единица. Считается, что корень дерева находится на уровне 1. Если некоторый узел А располагается на уровне i, то находящийся непосредственно ниже его на уровне i+1 узел В называется непосредственным потомком узла А, а узел А называется непосредственным предком узла В. Максимальный уровень всех узлов дерева называется высотой или глубиной дерева, обозначим h. Высота пустого дерева равна нулю, высота дерева, состоящего из одного корня, равна 1. Дерево, содержащее максимальное число узлов, называется полным. Количество узлов в полном дереве степени d высотой h вычисляется по формуле (i – номер уровня)

 

Основные свойства деревьев общего вида:

¨ корень не имеет предков;

¨ каждый узел, за исключением корня, имеет только одного предка;

¨ каждый узел связан с корнем единственным путем, т.е. в деревьях отсутствуют замкнутые контуры (циклы).

Если в определении дерева имеет значение относительный порядок поддеревьев Т1,…,Тm, дерево является упорядоченным. Поэтому два упорядоченных дерева на рис. 64 – это разные, отличные друг от друга объекты.

 

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

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