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

Деревья. Основные понятия и определения. Бинарное дерево

Важным частным случаем графа является дерево.

Существует довольно много равносильных определений деревьев, вот лишь некоторые из них.

Дерево - это связный граф без циклов.

Дерево - это связный граф, в котором при N вершинах всегда ровно N-1 ребро.

Дерево - это граф, между любыми двумя вершинами которого существует ровно один путь.

Аналогичным образом определяется и ориентированное дерево - как орграф, в котором между любыми двумя вершинами существует не более одного пути.

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

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

Эти подмножества называются левым и правым поддеревьями исходного дерева.

Каждый элемент бинарного дерева называется узлом дерева.

На рисунке показан общепринятый способ изображения бинарного дерева. Это дерево состоит из девяти узлов, А-корень дерева. Его левое поддерево имеет корень В, а правое- корень С. Это изображается двумя ветвями, исходящими из А: левым - к В и правым - к С. Отсутствие ветви обозначает пустое поддерево.

Например, левое поддерево бинарного дерева с корнем С и правое поддерево бинарного дерева с корнем Е оба пусты. Бинарные деревья с корнями D, G, Н и I имеют пустые левые и правые поддеревья.

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

Введем понятия степени узла и степени дерева. Степенью узла в дереве называется количество дуг, которое из него выходит. Степень дерева равна максимальной степени узла, входящего в дерево. Исходя из определения степени понятно, что степень узла бинарного дерева не превышает числа два. При этом листьями в дереве являются вершины, имеющие степень ноль.

Рис.4.1. Бинарное дерево

Другим важным признаком структурной классификации бинарных деревьев является строгость бинарного дерева. Строго бинарное дерево состоит только из узлов, имеющих степень два или степень ноль. Нестрого бинарное дерево содержит узлы со степенью равной одному.

Рис.4.3. Строго и не строго бинарные деревья

Рис.4.2. Полное и неполное бинарные деревья