Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
PAGE 3
Лекция 15
4.9.3.4. Бинарные деревья
Бинарное дерево – это динамическая структура данных, состоящая из элементов (узлов), ка ждый из которых наряду с данными содержит также ссылки (не более двух) на различные бинарные поддеревья. На каждый узел, кроме начального, существует ровно одна ссылка. Начальный узел называется корнем дерева.
Узел, не имеющий поддеревьев, называется листом. Узлы поддерева называются потомками его корневого узла, который соответственно является их предком. Высота дерева определяется количеством уровней, на которых располага ются его узлы.
Заметим, что в оперативной памяти ячейки расположены линейно по
возрастанию адресов, а дерево – это метод логической организации данных.
Если в дереве для каждого узла все ключи ле вого поддерева меньше ключа этого узла, а все ключи правого поддерева – больше, то оно называется деревом поиска. В нем одинаковые ключи не допускаются. В дереве поиска можно найти элемент по ключу, двигаясь от корня и переходя на левое или правое поддерево в зависимости от значения ключа в каждом узле. Такой поиск гораздо эффективнее поиска по списку, поскольку время поиска определяется высотой дерева, а она пропорциональна двоичному логарифму ко личества узлов.
Для так называемого сбалансированного дерева, в котором количество узлов справа и слева отличается не более чем на единицу, высота дерева равна двоичному логарифму коли чества узлов. Линейный список можно представить как вырожденное бинарное дерево, в котором каждый узел имеет не более одной ссылки. Для списка среднее время поиска равно половине длины списка.
Дерево является рекурсивной структурой данных, поскольку каждое поддерево также является деревом. Многие действия с такими структурами естественным образом описы ваются с помощью рекурсивных алгоритмов. Например, функцию обхода всех уз лов дерева в общем виде можно описать так:
function way_around ( дерево )
{
way_around ( левое поддерево );
посещение корня;
way_around ( правое поддерево );
}
Приведенная функция позволяет получить на выходе отсортиро ванную последовательность ключей, поскольку сначала посещаются вершины с меньшими ключами, расположенные в левом поддереве. Результат обхода дере ва на рисунке: 1, 6, 7, 8, 9, 10, 20, 25, 28, 30.
Можно обходить дерево и в другом порядке, например, сначала корень, потом поддеревья. Если в функции обхода первое обращение будет к правому поддереву, то результат обхода будет другим: 30, 28, 25, 20, 10, 9, 8, 7, 6, 1.
Таким образом, деревья поиска можно применять для сортировки значений. При обходе дерева узлы не удаляются.
Для бинарных деревьев определены следующие операции:
Для каждого рекурсивного алгоритма на C++ можно создать его нерекурсивный эквивалент. В приведенной ниже программе реализована нерекурсивная функция поис ка по дереву с включением и рекурсивная функция обхода дерева. Первая осуществляет поиск элемента с заданным ключом. Если элемент найден, она возвращает указатель на него, а если нет – включает элемент в соответствующее место дерева и возвращает указатель на него. Для включения элемента необходи мо помнить пройденный по дереву путь на один шаг назад и знать, выполняется ли включение нового элемента в левое или правое поддерево его предка.
Программа формирует дерево из массива целых чисел и выводит его на экран.
#include <iostream.h>
struct Node
{
int d:
Node *left, *right;
};
// Объявления функций
Node *first (const int d);
Node *search_insert (Node *root, const int d);
void print_tree (Node *root, const int level);
// Основная функция
int main ()
{
const int b[] = { 10, 1, 6, 7, 8, 9, 20, 25, 28, 30 };
const int N = sizeof (b) / sizeof (int);
Node *root = first (b[0]);
for (int i = 1; i < N; i++) search_insert (root, b[i]);
print_tree (root, 0);
return 0;
}
/*** Определения функций ***/
// Формирование первого элемента дерева
Node *first (const int d)
{
Node *pv = new Node;
pv->d = d; pv->left = 0; pv->right = 0;
return pv;
}
// Поиск с включением
Node *search_insert (Node *root, const int d)
{
Node *pv = root, *prev;
bool found = false;
while (pv && !found)
{
prev = pv;
if (d == pv->d) found = true;
else if (d < pv->d) pv = pv->left;
else v = pv->right;
}
if (found) return pv; // Искомый узел найден
// Не найден - создать новый узел
Node *pnew = new Node;
pnew->d = d; pnew->left = 0; pnew->right = 0;
if (d < prev->d) prev->left = pnew; // Присоединение к левому поддереву предка
else prev->right = pnew; // Присоединение к правому поддереву предка
return pnew;
}
// Рекурсивный обход дерева
void print_tree (Node *root, const int level)
{
if (pr)
{
print_tree (root ->left, level +1); // Вывод левого поддерева
for (int i = 0; i < level; i++) cout << " "; // Сдвиг позиции соответственно уровню
cout << root ->d << endl; // Вывод корня поддерева
print_tree (root ->right, level +1); // Вывод правого поддерева
}
}
Рассмотрим подробнее функцию обхода дерева print_tree. Вторым параметром в нее переда ется целая переменная, определяющая, на каком уровне находится узел. Корень находится на уровне 0. Дерево печатается по горизонтали так, что корень нахо дится слева. Перед значением узла для имитации структуры дерева выводится количество пробелов, пропорциональное уровню узла. Если заком ментировать цикл печати пробелов, отсортированный по возрастанию массив бу дет выведен в столбик.
Удаление узла дерева представляет собой не такую простую задачу, поскольку удаляемый узел может быть корневым, содержать две, одну или ни одной ссылки на поддеревья. Для узлов, содержащих меньше двух ссылок, удаление тривиаль но. Чтобы сохранить упорядоченность дерева при удалении узла с двумя ссылка ми, его заменяют на узел с самым близким к нему ключом. Это может быть са мый левый узел его правого поддерева или самый правый узел левого поддерева. Например, чтобы удалить из дерева на рисунке узел с ключом 25, его можно заме нить на 20 или 28, узел 10 заменяется на 9 или 20, и т. д. Реализация функции удаления оставлена для самостоятельной работы.
4.9.3.5. О применении массивов
Операции выделения и освобождения динамической памяти являются дорогостоящими, т.к. требуют обращения к операционной системе. Поэтому если максимальный размер данных можно определить до начала их использования и в процессе работы этот размер не меняется (например, при сортировке содержимого файла), более эффективным может оказаться однократное выделение непрерыв ной области памяти. Связи элементов при этом реализуются не указателями, а с помощью вспомогательных переменных или массивов, в которых хранятся номера элементов.
Так можно, например, реализовать стек. Кроме массива элементов, соответ ствующих типу данных стека, достаточно иметь одну переменную целого типа для хранения индекса элемента массива в вершине стека. При помещении в стек индекс увеличивается на единицу, а при выборке – уменьшается. Для работы очереди понадобятся две переменные целого типа – для хранения индексов начала и конца очереди.
Для реализации линейного списка требуется вспомогательный массив целых чи сел и еще одна переменная, например:
10 25 20 6 28 8 1 30 7 9 (массив данных)
1 2 3 4 5 6 7 8 9 -1 (вспомогательный массив)
0 (индекс первого элемента в списке).
При таком представлении списка i-й элемент вспомогательного массива содержит для i-гo элемента мас сива данных индекс следующего за ним элемента списка. Отрицательное число исполь зуется в качестве признака конца списка. Тот же массив после сортировки:
10 25 20 6 28 8 1 30 7 9 (массив данных)
2 4 1 8 7 9 3 -1 5 0 (вспомогательный массив)
6 (индекс первого элемента в списке).
Для создания бинарного дерева можно использовать два вспомогательных мас сива (индексы вершин его левого и правого поддерева). Отрицательное число используется как признак пустой ссылки. Например, рассмотренное в предыдущем пункте дерево можно представить следующим образом:
10 25 20 6 28 8 1 30 7 9 (массив данных)
3 2 -1 6 -1 8 -1 4 -1 -1 (левая ссылка)
1 7 -1 5 -1 9 -1 -1 -1 -1 (правая ссылка)
Связывающие индексы можно хранить не только в отдельных массивах, ни и в структуре каждого элемента. Память под общий массив можно выделить либо на этапе компиляции, если размер можно задать константой, либо во время выполнения программы. Напри мер, для списка:
struct Node
{
Data d; // тип данных Data должен быть определен ранее
int i;
}:
const int N = 1000;
Node listl [N]; // на этапе компиляции
……………………………………………………..
Node *plist2 = new Node [N]; // на этапе выполнения
Заметим, что при работе с подобными структурами необходимо контролировать возможный выход ин дексов за границу массива.
Приведенный здесь способ реализации позволяет использовать преимущества динамических структур (например, сортировать структуры из громоздких эле ментов данных без их физического перемещения в памяти), и при этом не расхо довать время на выделение и освобождение памяти для каждого элемента дан ных.
28
9
7
30
20
8
1
25
6
10