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

Рис.1 "Пример бинарного дерева"

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

Если А - корень бинарного дерева и В - корень его левого или правого поддерева, то говорят, что А-отец В, а В-левый или правый сын А. Узел, не имеющий сыновей (такие как узлы D, G, Н и F), называется листом.

Узел nl - предок узла n2 (а n2-потомок nl), если nl-либо отец n2, либо отец некоторого предка n2.

Узел n2-левый потомок узла n1, если n2 является либо левым сыном n1, либо потомком левого сына n1. Похожим образом может быть определен правый потомок.

Два узла являются братьями, если они сыновья одного и того же отца. Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правые и левые поддеревья, то дерево называется строго бинарным деревом. Строго бинарное дерево с n листами всегда содержит 2n-1 узлов. Пример строго бинарного дерева приведен на рисунке ниже.

Рис.2 "Строго бинарное дерево"

Уровень узла в бинарном дереве может быть определен следующим образом. Корень дерева имеет уровень 0, и уровень любого другого узла дерева имеет уровень на 1 больше уровня своего отца. Например, в бинарном дереве на первом рисунке узел Е - узел уровня 2, а узел Н-уровня 3. Глубина бинарного дерева - это максимальный уровень листа дерева, что равно длине самого длинного пути от корня к листу дерева. Стало быть, глубина дерева на первом рисунке равна 3.

Полное бинарное дерево уровня n - это дерево, в котором каждый узел уровня n является листом и каждый узел уровня меньше n имеет непустые левое и правое поддеревья. На рисунке приведен пример полного бинарного дерева.

Рис.3 "Полное бинарное дерево"

Почти полное бинарное дерево - это бинарное дерево, для которого существует неотрицательное целое k такое, что:

1. Каждый лист в дереве имеет уровень k или k+1.

2. Если узел дерева имеет правого потомка уровня k+1, тогда все его левые потомки, являющиеся листами, также имеют уровень k+1.

Есть еще одна разновидность бинарных деревьев, которая называется дерево поиска. Это двоичное дерево организовано так, что для каждой вершины справедливо утверждение, что все ключи левого поддерева меньше ключа , а все ключи правого поддерева больше его, то такое дерево будем называть деревом поиска. В таком дереве легко обнаружить заданный элемент, для этого достаточно, начав с корня, двигаться к левому или правому поддереву на основании лишь одного сравнения с ключом текущей вершины. Дерево поиска для заданной последовательности целых чисел 23, 17, 26, 32, 18, 6, 2, 5, 8, 29, 146 имеет вид:

Размещено на http://www.allbest.ru/

Рис.4 "Бинарное дерево писка"

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

Существует 3 способа обхода бинарного дерева.

в прямом порядке

в симметричном порядке

в обратном порядке

В прямом порядке:

Попасть в корень

Пройти в прямом порядке левое поддерево

Пройти в прямом порядке правое поддерево

В симметричном порядке:

Пройти в симметричном порядке левое поддерево

Попасть в корень

Пройти в симметричном порядке правое поддерево

В обратном порядке:

Пройти в обратном порядке левое поддерево

Пройти в обратном порядке правое поддерево

Попасть в корень

Рис.5"Пример обхода бинарного дерева разными способами"

Прямой порядок: ABDGCEHIF

Симметричный порядок: DGBAHEICF

Обратный порядок: GDBHIEFCA

Применение

бинарное дерево программа поиск

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

Раздел 2. Алгоритмическая часть