 |
Реализация процедуры и функции работы с бинарным деревом.
|
|
|
|
Дерево– это непустое конечное множество элементов, из которых один называетсякорнем, а остальные делятся на несколько непересекающихся подмножеств, каждое из которых само является деревом.
Рекурсивное определение. Дерево с базовым типом Т – это либо: пустое дерево, либо некоторый узел типа Т с некоторым конечным числом связанных с ним деревьев типа Т, называемых поддеревьями.
Существует несколько способов изображения структуры дерева: вложенные множества (1), вложенные скобки (2), отступы (3), граф (4). Ниже с помощью перечисленных способов изображено одно и то же дерево, элементами которого являются буквы латинского алфавита:
Структура, представленная в виде графа и явно отражающая разветвления, привела к появлению термина «дерево». Каждый элемент дерева называют узлом. Дерево принято изображать растущим вниз, а его верхний узел называют корнем. Все узлы дерева разбивают на уровни. Корень имеет нулевой уровень. Если узел x лежит на уровне i, а y связана с x и лежит на уровне i +1, то говорят, что y – потомок (сын) x, а x – предок (отец) y. Высота дерева равна максимальному уровню этого дерева плюс 1.
Если элемент не имеет потомков, то его называют терминальным узлом, или листом, в противном случае узел называют внутренним. Число непосредственных потомков внутреннего узла называют его степенью. Максимальная степень всех узлов есть степень дерева.
Особенно важную роль играют упорядоченные деревья второй степени. Их называют двоичными(или бинарными)деревьями.
Примеры бинарного дерева:
генеалогическое дерево, где у каждого человека есть потомки в лице отца и матери; схема кубкового спортивного турнира, где каждая игра – это узел, в котором указан её победитель, а потомки – две предыдущие игры соперников; арифметическое выражение с бинарными операциями, где каждому оператору соответствует узел, а операнды – его поддеревья. Ниже приведены два бинарных дерева: дерево (а), элементами которого являются символы латинского алфавита, и дерево (б) выражения (a + b / c)´(d – e ´ f).
|
|
|
(а)(б)
Если каждый узел бинарного дерева, не являющийся листом, имеет непустые правые и левые поддеревья, то дерево называется строго бинарным. Строго бинарное дерево с n листами всегда содержит 2 n -1 узлов. Дерево выражения (б) является строго бинарным. Строго бинарное дерево, все листья которого расположены на одном уровне, называется совершенным. Совершенное дерево высотой h содержит 2 h –1 узлов. На каждом его уровне расположено максимальное количество узлов, равное 2 i, где i – номер уровня.
Реализация бинарного дерева: При реализации дерева с помощью динамических переменных каждый элемент дерева, помимо информационной части, содержит два указателя: на левое и правое поддеревья этого элемента. Переменная ссылочного типа fRoot указывает на корневой узел дерева. Если какой-либо узел дерева не имеет левого или правого поддерева, то соответствующий указатель этого узла содержит значение nil.
Реализация основных операций над бинарным деревом
Операции над бинарным деревом могут быть реализованы с помощью как итерационных, так и рекурсивных процедур. Поскольку дерево по своей природе является рекурсивной структурой, реализация операций обработки дерева в виде рекурсивных процедур является более наглядной и простой, поэтому там, где возможно использование рекурсии, итерационные методы рассматриваться не будут. Особенностью реализации операции над деревом в виде метода класса является отсутствие указателя на корень обрабатываемого дерева в списке параметров метода, т.к. этот указатель является полем класса-дерева и доступен всем его методам изнутри. В то же время для реализации операции с помощью рекурсии необходимо передавать значение указателя на корень текущего поддерева обрабатываемого дерева в тело рекурсивной процедуры. Это может быть выполнено с помощью внутренней рекурсивной подпрограммы для всех процедур-операций, реализуемых рекурсивно. Сам метод при этом остается нерекурсивным и фактически содержит в своем теле лишь вызов внутренней рекурсивной процедуры.
|
|
|
Построение бинарного дерева минимальной высоты с числом узлов n предусматривает, что из входного потока (в данном случае – из текстового файла) считываются значения, размещаемые в узлах строящегося дерева.
procedure tBinaryTree.Build (n: Word; var f: Text);
// Построение дерева минимальной высоты из nузлов из файлаf
function BuildTree(n:Word): pItem; // рекурсивная функция построения
Var
Item: pItem;
NLeft, NRight: Word;
v: tValue;
Begin
if n <> 0
Thenbegin
NLeft:= n div 2; NRight:= n - NLeft-1;
Item:= New(pItem);
Read(f, v);
if Eoln(f) then ReadLn(f);
Item^.Value:= v;
Item^.Left:= BuildTree(NLeft);
Item^.Right:= BuildTree(NRight);
BuildTree:= Item; end
else BuildTree:= nil;
end; // function BuildTree
Begin
fRoot:= BuildTree(n); fSize:=n;
end; // procedure tBinaryTree.Build
1.06.2016. Разработка программного продукта с использованием модуля.
Установка оборудования на рабочем месте.
|
|
|
