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

Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент (корень), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями. Каждый элемент бинарного дерева называется узлом [1,3].

Общепринятый способ изображения бинарного дерева представлен на рис. 2.15: дерево состоит из 9 узлов; А — корень; левое поддерево имеет корень В; правое — С.

Узел у, который находится непосредственно под узлом х, называется потоком х; если х находится на уровне i, то у — на уровне i+. Наоборот, узел х называется предком у. Считается, что корень дерева расположен на уровне 1. Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой. Если элемент не имеет потомков, он называется листом. Остальные элементы — внутренние узлы. Число потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева. Число ветвей, которое нужно пройти от корня к узлу х, называется длиной пути к х. Корень имеет длину пути 1; узел на уровне / имеет длину пути /.

 

Рис. 2.15

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

Узел дерева можно описать как структуру с полями.