Структуры и алгоритмы обработки данных


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


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

pic4_1.gif (3023 bytes)

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

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

pic4_2.gif (4860 bytes)

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

pic4_3.gif (3861 bytes)

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




Начало  Назад  Вперед



Книжный магазин