Программирование бинарных деревьев на языке СС++
СОДЕРЖАНИЕ
Введение
Язык
Си, созданный Денисом Ритчи в
начале 70-х годов в Bell Laboratory американской
корпорации AT&T, является одним из
универсальных языков программирования.
Язык Си считается языком системного программирования,
хотя он удобен и для написания прикладных
программ. Среди преимуществ языка Си
следует отметить переносимость программ
на компьютеры различной архитектуры
и из одной операционной системы в другую,
лаконичность записи алгоритмов, логическую
стройность программ, а также возможность
получить программный код, сравнимый по
скорости выполнения с программами, написанными
на языке ассемблера. Последнее связано
с тем, что хотя Си является языком высокого
уровня, имеющим полный набор конструкций
структурного программирования, он также
обладает набором низкоуровневых средств,
обеспечивающих доступ к аппаратным средствам
компьютера. С 1989 года язык Си регламентируется
стандартом Американского института национальных
стандартов ANSI С. В настоящее время, кроме
стандарта ANSI C разработан международный
стандарт ISO C (International Standard Organization C).
1 Постановка задачи
1.1 Общая характеристика задачи
Работа со структурами
данных: программирование В дерева на языке С/С++
Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования.
Для каждого поезда указывается:
• номер поезда;
• станция назначения;
время отправления.
Данные в информационной системе организованы в виде бинарного дерева.
Составить программу, которая:
• обеспечивает первоначальный ввод данных в информационную систему и формирование двоичного дерева;
• производит вывод всего дерева;
• вводит номер поезда и выводит все данные об этом поезде;
• вводит название станции назначения и выводит данные о всех поездах, следующих до этой станции.
Программа
должна обеспечивать диалог с помощью
меню и контроль ошибок при вводе.
1.2 Двоичные деревья
Основные понятия
Структуры данных типа “дерево” исключительно широко используются в программной индустрии. В отличие от списковых структур деревья относятся к нелинейным структурам. Любое дерево состоит из элементов – узлов или вершин, которые по определенным правилам связаны друг с другом рёбрами. В списковых структурах за текущей вершиной (если она не последняя) всегда следует только одна вершина, тогда как в древовидных структурах таких вершин может быть несколько. Математически дерево рассматривается как частный случай графа, в котором отсутствуют замкнутые пути (циклы).
Дерево является типичным примером рекурсивно определённой структуры данных, поскольку оно определяется в терминах самого себя.
Рекурсивное определение дерева с базовым типом Т – это:
- либо пустое дерево (не содержащее ни одного узла)
- либо некоторая вершина типа Т с конечным числом связанных с ней отдельных деревьев с базовым типом Т, называемых поддеревьями
Отсюда видно, что в любом непустом дереве есть одна особая вершина – корень дерева, которая как бы определяет “начало” всего дерева. С другой стороны, существуют и вершины другого типа, не имеющие связанных с ними поддеревьев. Такие вершины называют терминальными или листьями.
Классификацию деревьев можно провести по разным признакам.
- По числу
возможных потомков у вершин различают
двоичные (бинарные) или недвоичные
(сильноветвящиеся) деревья.
Двоичное дерево: каждая вершина может иметь не более двух потомков.
Недвоичное дерево: вершины могут иметь любое число потомков.
- Если в дереве важен порядок следования потомков, то такие деревья называют упорядоченными. Для них вводится понятие левый и правый потомок (для двоичных деревьев) или более левый/правый (для недвоичных деревьев). В этом смысле два следующих простейших упорядоченных дерева с одинаковыми элементами считаются разными:
При использовании деревьев часто встречаются такие понятия как путь между начальной и конечной вершиной (последовательность проходимых ребер или вершин), высота дерева (наиболее длинный путь от корневой вершины к терминальным).
При рассмотрении дерева как структуры данных необходимо четко понимать следующие два момента:
- Все вершины дерева, рассматриваемые как переменные языка программирования, должны быть одного и того же типа, более того – записями с некоторым информационным наполнением и необходимым количеством связующих полей
- В силу естественной логической разветвленности деревьев (в этом весь их смысл!) и отсутствия единого правила выстраивания вершин в порядке друг за другом, их логическая организация не совпадает с физическим размещением вершин дерева в памяти.
Дерево
как абстрактная структура
- добавление новой вершины
- удаление некоторой вершины
- обход всех вершин дерева
- поиск заданной вершины
Двоичные деревья
Двоичные деревья (ДД) используются наиболее часто и поэтому представляют наибольший практический интерес. Каждая вершина ДД должна иметь два связующих поля для адресации двух своих возможных потомков.
ДД
можно реализовать двумя
- на основе массива записей с использованием индексных указателей
- на базе механизма динамического распределения памяти с сохранением в каждой вершине адресов ее потомков (если они есть)
Второй
способ является значительно более
удобным и поэтому используется
наиболее часто. В этом случае каждая
вершина описывается как
struct
TREE {
int Info;
TREE *Right;
TREE *Left;
};
Для
обработки дерева достаточно знать
адрес корневой вершины. Для хранения
этого адреса надо ввести ссылочную
переменную:
TREE *Root;
Тогда
пустое дерево просто определяется установкой
переменной Root в нулевое значение:
Root = NULL;
Реализацию основных операций с ДД удобно начать с процедур обхода. Поскольку дерево является нелинейной структурой, то НЕ существует единственной схемы обхода дерева. Классически выделяют три основных схемы:
- обход в прямом направлении
- симметричный обход
- обход в обратном направлении
Для объяснения каждого из этих правил удобно воспользоваться простейшим ДД из трех вершин. Обход всего дерева следует проводить за счет последовательного выделения в дереве подобных простейших поддеревьев и применением к каждому из них соответствующего правила обхода. Выделение начинается с корневой вершины.
Сами
правила обхода носят рекурсивный
характер и формулируются следующим
образом:
- Обход в прямом направлении:
- обработать корневую вершину текущего поддерева
- перейти к обработке левого поддерева таким же образом
- обработать правое поддерево таким же образом
- Симметричный обход:
- рекурсивно обработать левое поддерево текущего поддерева
- обработать вершину текущего поддерева
- рекурсивно обработать правое поддерево
- Обход в обратном направлении:
- рекурсивно обработать левое поддерево текущего поддерева
- рекурсивно обработать правое поддерево
- затем – вершину текущего поддерева
В качестве примера по шагам рассмотрим обход следующего ДД с числовыми компонентами (10 вершин):
Обход в прямом порядке:
- Выделяем поддерево 0-1-2
- обрабатываем его корень – вершину 0
- переходим к левому потомку и выделяем поддерево 1-3-4
- обрабатываем его корень – вершину 1
- выделяем левое поддерево 3-*-* (здесь * обозначает пустую ссылку)
- обрабатываем его корень – вершину 3
- т.к. левого потомка нет, обрабатываем правое поддерево
- т.к. правого поддерева нет, возвращаемся к поддереву 1-3-4
- выделяем поддерево 4-6-7
- обрабатываем его корень – вершину 4
- выделяем левое поддерево 6-*-*
- обрабатываем его корень – вершину 6
- т.к. левого потомка нет, обрабатываем правое поддерево
- т.к. правого потомка нет, то возвращаемся к поддереву 4-6-7
- выделяем правое поддерево 7-*-*
- обрабатываем его корень – вершину 7
- т.к. левого поддерева нет, обрабатываем правое поддерево
- т.к. правого поддерева нет, то возвращаемся к поддереву 4-6-7
- т.к. поддерево 4-6-7 обработано, то возвращаемся к поддереву 1-3-4
- т.к. поддерево 1-3-4 обработано, возвращаемся к поддереву 0-1-2
- выделяем правое поддерево 2-*-5
- обрабатываем его корень – вершину 2
- т.к. левого потомка нет, обрабатываем правого потомка
- выделяем поддерево 5–8–9
- обрабатываем его корень – вершину 5
- выделяем левое поддерево 8-*-*
- обрабатываем его корень – вершину 8
- т.к. левого поддерева нет, обрабатываем правое поддерево
- т.к. правого поддерева нет, то возвращаемся к поддереву 5-8-9
- выделяем правое поддерево 9-*-*
- обрабатываем его корень – вершину 9
- т.к. левого поддерева нет, обрабатываем правое поддерево
- т.к. правого поддерева нет, то возвращаемся к поддереву 5-8-9
- т.к. поддерево 5-8-9 обработано, то возвращаемся к поддереву 2-*-5
- т.к. поддерево 2-*-5 обработано, то возвращаемся к поддереву 0-1-2
- т.к. поддерево 0-1-2 полностью обработано, то обход закончен
В итоге получаем следующий порядок обхода вершин: 0-1-3-4-6-7-2-5-8-9
Идеально сбалансированные деревья
В заключение данной темы рассмотрим один частный случай ДД – так называемое идеально сбалансированное дерево (ИСД). Как будет отмечено в дальнейшем, эффективное использование деревьев на практике часто требует управления ростом дерева для устранения крайних случаев, когда дерево вырождается в линейный список и тем самым теряет всю свою привлекательность (с вычислительной точки зрения, разумеется).
В этом смысле ИСД полностью оправдывает свое название, поскольку вершины в нем распределяются наиболее равномерно и тем самым ИСД имеет минимально возможную высоту. Более точно, ДД называется идеально сбалансированным, если для каждой вершины число вершин в левом и правом ее поддеревьях отличаются не более чем на единицу. Обратим внимание, что данное условие должно выполняться для всех вершин дерева!
ИСД легко строится, если заранее известно количество вершин N в этом дереве. В этом случае ИСД можно построить с помощью следующего рекурсивного алгоритма:
- взять первую по порядку вершину в качестве корневой
- найти количество
вершин в левых и правых поддеревьях:
NL = N div 2; NR = N – NL – 1; - построить левое поддерево с NL вершинами точно таким же образом (пока не получим NL = 0)
- построить правое поддерево с NR вершинами точно таким же образом (пока не получим NR = 0)
Естественно, что реализация рекурсивного алгоритма наиболее просто выполняется в виде рекурсивной подпрограммы. При этом между этой процедурой и процедурами обхода есть одно принципиальное различие: процедуры обхода лишь используют существующую структуру дерева, не изменяя ее, и поэтому их формальные параметры являются лишь входными, тогда как процедура построения ИСД должна СОЗДАВАТЬ вершины и каждый раз возвращать в вызвавшую ее подпрограмму адрес очередной созданной вершины. Поэтому формальный параметр ссылочного типа должен быть объявлен как параметр-переменная. Кроме того, второй формальный параметр-значение принимает число вершин в текущем строящемся поддереве.
void AddNodes
(Node **Сurrent, int aN);
{
Node *Tmp;
int NL, NR;
if (aN==0) /*вершин для размещения нет*/
Current = NULL; /*формируем пустую ссылку*/
else
{
NL = aN div 2; /*сколько вершин будет слева?*/
NR = aN – NL – 1; /*сколько вершин будет справа?*/
Tmp = new Node; /*создаем корень поддерева*/
AddNodes (&Tmp->Left, NL); /*уходим на создание
левого поддерева*/
AddNodes (&Tmp->Right, NR); /*уходим на создание
правого поддерева*/
Current = Tmp; /*возвращаем адрес созданного
корня*/
}
}
Запуск процесса построения как обычно выполняется из главной программы с помощью вызова AddNodes(&Root, N). В этом вызове фактический параметр N обязательно должен иметь конкретное значение, например – заданное пользователем количество вершин в строящемся ИСД. Однако, первый фактический параметр Root, являясь выходным, получит свое значение лишь после отработки всех рекурсивных вызовов, при возврате в главную программу.
Для
понимания работы приведенной процедуры
целесообразно вручную расписать шаги
ее работы для простейшего дерева из трех
вершин. Пусть элементами дерева являются
символы A, B, C. В результате работы мы должны
получить:
Root = A, A->Left = B, A->Right = C,
B->Left = NULL, B->Right = NULL,
C->Left = NULL, C->Right = NULL.
Двоичные деревья представляют эффективный способ поиска. Двоичное дерево представляет собой структурированную коллекцию узлов. Коллекция может быть пустой и в этом случае мы имеем пустое двоичное дерево. Если коллекция непустая, то она подразделяется на три раздельных семейства узлов: корневой узел n (или просто корень), двоичное дерево, называемое левым поддеревом для n, и двоичное дерево, называемое правым поддеревом для n. На рис. 1а узел, обозначенный буквой А, является корневым, узел В называется левым потомком А и является корнем левого поддерева А, узел С называется правым потомком А и является корнем правого поддерева А.
Рис. 1 Двоичное дерево с показанными внешними узлами (а) и без них (б)
Двоичное дерево на рис. 1а состоит из четырех внутренних узлов (обозначенных на рис. кружками) и пяти внешних (конечных) узлов (обозначены квадратами). Размер двоичного дерева определяется числом содержащихся в нем внутренних узлов. Внешние узлы соответствуют пустым двоичным деревьям. Например, левый потомок узла В — непустой (содержит узел D), тогда как правый потомок узла В — пустое дерево. В некоторых случаях внешние узлы обозначаются каким-либо образом, в других — на них совсем не ссылаются и они считаются пустыми двоичными деревьями (на рис. 1 внешние узлы не показаны).
При реализации двоичных деревьев, основанной на точечном представлении, узлы являются объектами класса TreeNode.
template<class T> class TreeNode {
protected:
TreeNode *_lchild;
TreeNode *_rchild;
Т val;
public:
TreeNode(T);
virtual ~TreeNode(void);
friend class SearchTree<T>; // возможные пополнения
friend class BraidedSearchTree<T>; // структуры
};
Элементы данных _lchild и _rchild обозначают связи текущего узла с левым и правым потомками соответственно, а элемент данных val содержит сам элемент.
Конструктор класса формирует двоичное дерево единичного размера — единственный внутренний узел имеет два пустых потомка, каждое из которых представлено нулем NULL:
template<class T> TreeNode<T>::TreeNode(T v) :
val(v), _lchild(NULL), _rchild (NULL)
{
}
Деструктор ~TreeNode рекурсивно удаляет оба потомка текущего узла (если они существуют) перед уничтожением самого текущего узла:
template<class T> TreeNode<T>::~TreeNode(void)
{
if (_lchild) delete _lchild;
if (_rchild) delete _rchild;
}
Двоичные
деревья поиска
Основное назначение двоичных деревьев заключается в повышении эффективности поиска. При поиске выполняются такие операции, как нахождение заданного элемента из набора различных элементов, определение наибольшего или наименьшего элемента в наборе, фиксация факта, что набор содержит заданный элемент. Для эффективного поиска внутри двоичного дерева его элементы должны быть организованы соответствующим образом. Например, двоичное дерево будет называться двоичным деревом поиска, если его элементы расположены так, что для каждого элемента n все элементы в левом поддереве n будут меньше, чем n, а все элементы в правом поддереве — будут больше, чем n. На рис. 2 изображены три двоичных дерева поиска, каждое из которых содержит один и тот же набор целочисленных элементов.
Рис. 2 Три двоичных дерева поиска с одним и тем же набором элементов
В общем случае существует огромное число двоичных деревьев поиска (различной формы) для любого заданного набора элементов.
Предполагается, что элементы располагаются в линейном порядке и, следовательно, любые два элемента можно сравнить между собой. Примерами линейного порядка могут служить ряды целых или вещественных чисел в порядке возрастания, а также слов или строк символов, расположенных в лексикографическом (алфавитном, или словарном) порядке. Поиск осуществляется путем обращения к функции сравнения для сопоставления любых двух элементов относительно их линейного порядка. В нашей версии деревьев поиска действие функции сравнения ограничено только явно определенными объектами деревьев поиска.
Также очень полезны функции для обращения к элементам дерева поиска и воздействия на них. Такие функции обращения могут быть полезны для вывода на печать, редактирования и доступа к элементу или воздействия на него каким-либо иным образом. Функции обращения не принадлежат деревьям поиска, к элементам одного и того же дерева поиска могут быть применены различные функции обращения.
Конструкторы и деструкторы
Конструктор SearchTree инициализирует элементы данных cmp для функции сравнения и root для пустого дерева поиска:
template<class T> SearchTree<T>::SearchTree (int (*с) (Т, Т) ) :
cmp(с), root (NULL)
{
}
Дерево поиска пусто только, если в элементе данных root содержится нуль (NULL) вместо разрешенного указателя:
template<class T> int SearchTree<T>::isEmpty (void)
{
return (root == NULL);
}
Деструктор удаляет все дерево путем обращения к деструктору корня:
template<class T> SearchTree<T>::~SearchTree (void)
{
if (root) delete root;
}
Поиск
Чтобы
найти заданный элемент val, мы начинаем
с корня и затем следуем
вдоль ломаной линии
Этот алгоритм поиска реализуется в компонентной функции find, которая возвращает обнаруженный ею указатель на элемент или NULL, если такой элемент не существует в дереве поиска.
template<class T> T SearchTree::find (T val)
{
TreeNode *n = root;
while (n) {
int result = (*cmp) (val, n->val);
if (result < 0)
n = n->_lchild;
else if (result > 0)
n = n->_rchild;
else
return n->val;
}
return NULL;
}
Этот алгоритм поиска можно сравнить с турниром, в котором участвуют некоторые кандидаты. В начале, когда мы начинаем с корня, в состав кандидатов входят все элементы в дереве поиска. В общем случае для каждого узла n в состав кандидатов входят все потомки n. На каждом этапе производится сравнение val с n->val. Если val меньше, чем n->val, то состав кандидатов сужается до элементов, находящихся в левом поддереве, а элементы в правом поддереве n, как и сам элемент n->val, исключаются из соревнования. Аналогичным образом, если val больше, чем n->val, то состав кандидатов сужается до правого поддерева n. Процесс продолжается до тех пор, пока не будет обнаружен элемент val или не останется ни одного кандидата, что означает, что элемент val не существует в дереве поиска.
Для нахождения наименьшего элемента мы начинаем с корня и прослеживаем связи с левым потомком до тех пор, пока не достигнем узла n, левый потомок которого пуст — это означает, что в узле n содержится наименьший элемент. Этот процесс также можно уподобить турниру. Для каждого узла n состав кандидатов определяется потомками узла n. На каждом шаге из состава кандидатов удаляются те элементы, которые больше или равны n->val и левый потомок n будет теперь выступать в качестве нового n. Процесс продолжается до тех пор, пока не будет достигнут некоторый узел n с пустым левым потомком и, полагая, что не осталось кандидатов меньше, чем n->val, и будет возвращено значение n->val.
Компонентная функция findMin возвращает наименьший элемент в данном дереве поиска, в ней происходит обращение к компонентной функции _findMin, которая реализует описанный ранее алгоритм поиска, начиная с узла n :
template<class T> T SearchTree<T>::findMin (void)
{
TreeNode<T> *n = _findMin (root);
return (n ? n->val : NULL);
}
template<class T>
TreeNode<T> *SearchTree<T>::_findMin (TreeNode<T> *n)
{
if (n == NULL)
return NULL;
while (n->_lchild)
n = n->_lchild;
return n;
}
Наибольший элемент в дереве поиска может быть найден аналогично, только отслеживаются связи с правым потомком вместо левого.
Удаление элементов
Удаление элемента из двоичного дерева поиска гораздо сложнее, чем включение, поскольку может быть значительно изменена форма дерева. Удаение узла, у которого есть не более чем один непустой потомок, является равнительно простой задачей — устанавливается ссылка от предка узла на потомок. Однако ситуация становится гораздо сложнее, если у подлежащего удалению узла есть два непустых потомка: предок узла может быть связан с одним из потомков, а что делать с другим? Решение может заключаться не в удалении узла из дерева, а скорее в замене элемента, содержащегося в нем, на последователя этого элемента, а затем в удалении узла, содержащего этот последователь.
Рис. 4 Три ситуации, возникающие при удалении элемента из двоичного дерева поиска
Чтобы удалить элемент из дерева поиска, вначале мы отслеживаем путь поиска элемента, начиная с корня и вниз до узла n, содержащего элемент. В этот момент могут возникнуть три ситуации, показанные на рис. 4:
- Узел n имеет пустой левый потомок. В этом случае ссылка на n (записанная в предке n, если он есть) заменяется на ссылку на правого потомка n.
- У узла n есть непустой левый потомок, но правый потомок пустой. В этом случае ссылка вниз на n заменяется ссылкой на левый потомок узла n.
- Узел n имеет два непустых потомка. Найдем последователя для n (назовем его m), скопируем данные, хранящиеся в m, в узел n и затем рекурсивно удалим узел m из дерева поиска.
