 |
Реализация двоичного дерева
|
|
|
|
В отличие от списков двоичные деревья представляют собой более сложные структуры данных.
Дерево - непустое конечное множество элементов, один из которых называется корнем, а остальные делятся на несколько непересекающихся подмножеств, каждое из которых также является деревом. Одним из разновидностей деревьев являются бинарные деревья. Бинарное дерево имеет один корень и два непересекающихся подмножества, каждое из которых само является бинарным деревом. Эти подмножества называются левым и правым поддеревьями исходного дерева. На рис. 11 приведены графические изображения бинарных деревьев. Если один или более узлов дерева имеют более двух ссылок, то такое дерево не является бинарным.
Бинарные деревья с успехом могут быть использованы, например, при сравнении и организации хранения очередной порции входной информации с информацией, введенной ранее, и при этом в каждой точке сравнения может быть принято одно из двух возможных решений. Так как информация вводится в произвольном порядке, то нет возможности предварительно упорядочить ее и применить бинарный поиск. При использовании линейного поиска время пропорционально квадрату количества анализируемых слов. Каким же образом, не затрачивая большое количество времени, организовать эффективное хранение и обработку входной информации. Один из способов постоянно поддерживать упорядоченность имеющейся информации - это перестановка ее при каждом новом вводе информации, что требует существенных временных затрат. Построение бинарного дерева осуществляется на основе лексикографического упорядочивания входной информации.
Лексикографическое упорядочивание информации в бинарном дереве заключается в следующем. Считывается первая информация и помещается в узел, который становится корнем бинарного дерева с пустыми левым и правым поддеревьями. Затем каждая вводимая порция информации сравнивается с информацией, содержащейся в корне. Если значения совпадают, то, например, наращиваем число повторов и переходим к новому вводу информации. Если же введенная информация меньше значения в корне, то процесс повторяется для левого поддерева, если больше - для правого. Так продолжается до тех пор, пока не встретится дубликат или пока не будет достигнуто пустое поддерево. В этом случае число помещается в новый узел данного места дерева.
|
|
|
Приводимый далее пример шаблонного класса B_tree демонстрирует простое дерево поиска. Как и для программы очереди, код программы организован в виде двух файлов, где файл Bt.h является непосредственно шаблонным классом дерева, а Bt.cpp демонстрирует работу функций шаблонного класса. Вначале приведен текст файла Bt.h.
#include <iostream>
#include <cassert>
using namespace std;
///////////////////////////////////////////////////////////////
// реализация шаблона класса B_tree
// Тип Т должен поддерживать следующие операции:
// operator=();
// operator<<();
// operator==();
// operator!=();
// operator<();
//
///////////////////////////////////////////////////////////////
template <class T>
Class B_tree
{
private:
Struct T_node
{ friend class B_tree;
T val; // данные узла
T_node *left; // указатель на левый узел
T_node *right; // указатель на правый узел
int count; // число повторов val при вводе
T_node(); // конструктор
T_node(const T node_val): val(node_val) { } // конструктор
~T_node(){} // деструктор
// печать данных в виде дерева "на боку" с корнем слева
// "Обратный" рекурсивный обход (т.е. справа налево)
// Листья показаны как "@".
void print (const int level = 0) const
{ // Инициализация указателем this (а не корнем)
// это позволяет пройти по любому поддереву
const T_node *tn = this;
if(tn) tn->right->print(level+1); // сдвиг вправо до листа
|
|
|
for (int n=0; n<level;++n)
cout << " ";
if(tn)
cout << tn->val << '(' << tn->count << ')' << endl;
else
cout << "@" << endl;
if(tn) tn->left->print(level+1); // сдвиг на левый узел
}
};
private:
T_node *root;
T_node *zero_node;
// Запретить копирование и присваивание
B_tree(const B_tree &);
B_tree & operator=(const B_tree &);
// Создать корневой узел и проинициализировать его
void new_root(const T root_val)
{ root = new T_node(root_val);
root->left = 0;
root->right = 0;
root->count = 1;
}
// Find_node(T find_value) возвращает ссылку на
// указатель для упрощения реализации remove(T).
T_node * & find_node(T find_value)
{ T_node *tn = root;
while ((tn!= 0) && (tn->val!= find_value))
{ if(find_value < tn->val)
tn = tn->left; // движение налево
else
tn = tn->right; // движение направо
}
if (!tn) return zero_node;
else return tn;
}
// Присоединяет новое значение ins_val к соответствующему листу,
// если значения нет в дереве, и увеличивает count для каждого
// пройденного узла
T_node * insert_node(const T ins_val, T_node * tn = 0)
{ if(!root)
{ new_root(ins_val);
return root;
}
if(!tn) tn = root;
if((tn) && (tn->val!= ins_val))
{ if(ins_val < tn->val)
{ if(tn->left) // просмотр левого поддерева
insert_node(ins_val,tn->left);
else
{ attach_node(tn,tn->left,ins_val); // вставка узла
return tn->left;
}
}
else
{ if(tn->right) // просмотр правого поддерева
insert_node(ins_val,tn->right);
else
{ attach_node(tn,tn->right,ins_val); // вставка узла
return tn->right;
}
}
}
else
if(tn->val==ins_val) add_count(tn,1);
assert(tn); // Оценивает выражение и, когда результат ЛОЖЕН, печатает
// диагностическое сообщение и прерывает программу
return 0;
}
// Создание нового листа и его инициализация
void attach_node(T_node * new_parent,
T_node * & new_node, T insert_value)
{ new_node = new T_node(insert_value);
new_node->left = 0;
new_node->right = 0;
new_node->count = 1;
}
// Увеличение числа повторов содержимого узла
void add_count(T_node * tn, int incr)
{ tn->count += incr; }
// Удаление всех узлов дерева в обходе с отложенной
// выборкой. Используется в ~B_tree().
void cleanup (T_node *tn)
{ if(!tn) return;
if(tn->left)
{ cleanup(tn->left);
tn->left = 0;
}
if(tn->right!= 0)
{ cleanup(tn->right);
tn->right = 0;
}
delete tn;
}
// рекурсивно печатает значения в поддереве с корнем tn
// (обход дерева с предварительной выборкой)
void print_pre(const T_node * tn) const
{ if(!tn) return;
cout << tn->val << " ";
if(tn->left)
print_pre(tn->left);
if(tn->right)
print_pre(tn->right);
}
// рекурсивно печатает значения в поддереве с корнем tn
// (обход дерева)
void print_in(const T_node * tn) const
{ if(!tn) return;
if(tn->left)
print_in(tn->left);
cout << tn->val << " ";
|
|
|
if(tn->right)
print_in(tn->right);
}
// рекурсивно печатает значения в поддереве с корнем tn
// (обход дерева с отложенной выборкой)
void print_post(const T_node * tn) const
{ if(!tn) return;
if(tn->left)
print_post(tn->left);
if(tn->right)
print_post(tn->right);
cout << tn->val << " ";
}
public:
B_tree(): zero_node(0) {root = 0;}
B_tree(const T root_val): zero_node(0)
{ new_root(root_val); }
~B_tree()
{ cleanup(root); }
// Добавляет к дереву через функцию insert_node() значение, если его
// там еще нет. Возвращает true, если элемент добавлен, иначе false
bool add(const T insert_value)
{ T_node *ret = insert_node(insert_value);
if(ret) return true;
else return false;
}
// Find(T) возвращает true, если find_value найдено
// в дереве, иначе false
bool find(T find_value)
{ Tree_node *tn = find_node(find_value);
if(tn) return true;
else return false;
}
// Print() производит обратную порядковую выборку
// и печатает дерево "на боку"
void print() const
{ cout << "\n=---------------------------\n"<< endl;
// Это вызов Binary_tree::Tree_node::print(),
// а не рекурсивный вызов Binary_tree::print().
root->print();
}
// последовательная печать дерева при обходе
// с предварительной, порядковой и отложенной выборкой.
// Вызываются рекурсивные private-функции, принимающие
// параметр Tree_node *
void print_pre_order() const
{ print_pre(root);
cout << endl;
}
void print_in_order() const
{ print_in(root);
cout << endl;
}
void print_post_order() const
{ print_post(root);
cout << endl;
}
};
Далее приведено содержимое файла Bt.cpp.
#include "bin_tree.h"
B_tree<int> my_bt(7); // создание корня бинарного дерева
// Заполнение дерева целыми значениями
void populate()
{ my_bt.add(5);
my_bt.add(5);
my_bt.add(9);
my_bt.add(6);
my_bt.add(5);
my_bt.add(9);
my_bt.add(4);
my_bt.add(11);
my_bt.add(8);
my_bt.add(19);
my_bt.add(2);
my_bt.add(10);
my_bt.add(19);
}
int main()
{ populate();
my_bt.print ();
cout << endl;
cout << "Pre-order: ";
my_bt.print_pre_order ();
cout << "Post-order: ";
my_bt.print_post_order ();
cout << "In-order: ";
my_bt.print_in_order ();
return 0;
}
Результат работы программы:
B_tree содержит вложенный закрытый класс T_node (структуру) для представления внутреннего описания элемента (узла) бинарного дерева. Структура его скрыта от пользователя. Поле val содержит значение, хранимое в узле, left и right – указатели на левый и правый потомки данного узла.
В классе B_tree два открытых конструктора. Конструктор по умолчанию создает пустое бинарное дерево B_tree, а конструктор В_tree(const T) дерево с одним узлом. Деструктор ~B_tree() удаляет каждый T_node, производя обход бинарного дерева с отложенной выборкой. Отложенная выборка гарантирует, что никакой узел не будет удален, пока не удалены его потомки.
|
|
|
Для объектов класса B_tree с целью упрощения не определены (а только объявлены закрытыми) конструктор копирования и операция присваивания. Это позволяет компилятору сообщить об ошибке при попытке выполнить эти операции. Если эти операции потребуется использовать, то их необходимо сделать открытыми и определить.
Функция find_node() возвращает ссылку на указатель T_node. Для того чтобы функция могла сослаться на нулевой указатель, вводится поле zero_node.
Рекурсивные функции print_pre_order(), print_in_order() и print_post_order() печатают элементы дерева в линейной последовательности в соответствии со стандартными схемами обхода двоичного дерева. Функция print_pre_order() печатает значение узла до того, как будет напечатан любой из его потомков. Функция print_post_order(), наоборот, печатает значение узла только после того, как будут напечатаны все его потомки. И, наконец, функция print_in_order() выводит на печать элементы бинарного дерева в порядке возрастания.
Литература
1. Дейтел Х., Дейтел П.. Как прграммировать на С++: Пер. с англ. – М.: ЗАО «Издательство БИНОМ», 2001.
2. Шилд Г. Программирование на Borland C++ для профессионалов. –Мн.: ООО «Попурри», 1998.
3. Скляров В.А. Язык С++ и объектно-ориентированное программирование. Мн.: Выш. шк., 1997.
4. Ирэ П. Объектно-ориентированное программирование с использованием С++. Пер. с англ. – Киев: НИПФ «ДиаСофт Лтд», 1995.
5. Мейерс С. Наиболее эффективное использование С++. 35 новых рекомендаций по улучшению ваших программ и проектов. Пер. с англ. – М: ДМК Пресс, 2000.
Вопросы по курсу ООП
1. Как обратиться к глобальной переменной, если в функции определена локальная переменная с таким же именем?
2. Чему будут равны значения y и s после выполнения следующего кода
int y = 8;
int &s = y;
s++;
ответ s=9 y=9
3. Что происходит если new не смог выделить требуемую память?
ответ bad_alloc
4.Определить, не компилируя, что напечатает программа
class Lock{
public:
Lock(){ cout << "A"; }
Lock(Lock& B){ cout << "B"; }
~Lock(){ cout << "C"; }
};
int main(int argc, char* argv[])
{
try{
Lock guard;
throw 0; // вариант посложнее throw guard (ответ АВСЕС)
cout << "D";
}
catch(Lock&){
cout << "E";
}
catch(...){
cout << "X";
}
cout << endl;
return 0;
}
ответ ACX
Вопросы без ответов
- как удалить массив объектов
- что такое полиморфизм
- что такое абстрактный базовый класс
- как определить чисто виртуальную функцию
|
|
|
- зачем нужен виртуальный деструктор
- как реализован виртуальный деструктор в C++
- чем отличаются const char* ptr и char const *ptr
- в каких случаях вызывается конструктор копирования
- в чем потенциальная опасность конструктора копирования по умолчанию
Содержание
Введение. 3
Объектно-ориентированное программирование. 3
Абстрактные типы данных. 3
Базовые принципы объектно-ориентированного программирования. 4
Основные достоинства языка С++. 6
Особенности языка С++. 6
Ключевые слова. 7
Константы и переменные. 7
Операции. 7
Типы данных. 7
Передача аргументов функции по умолчанию.. 7
Простейший ввод и вывод. 8
Объект cout 8
Манипуляторы hex и oct 8
Другие манипуляторы.. 9
Объект cin. 11
Операторы для динамического выделения и освобождения памяти (new и delete) 11
Базовые конструкции объектно-ориентированных программ. 14
Объекты.. 14
Понятие класса. 16
Конструктор копирования. 28
Конструктор explicit 29
Указатели на компоненты класса. 32
Встроенные функции (спецификатор inline) 32
Организация внешнего доступа к локальным компонентам класса (спецификатор friend) 33
Вложенные классы.. 38
Static-члены (данные) класса. 41
Указатель this. 43
Компоненты-функции static и const 46
Proxi-классы.. 49
Ссылки. 50
Параметры ссылки. 53
Независимые ссылки. 54
Практические приемы ограничения числа объектов класса. 54
Наследование (производные классы) 56
Конструкторы и деструкторы при наследовании. 60
Виртуальные функции. 64
Абстрактные классы.. 75
Виртуальные деструкторы.. 81
Множественное наследование. 83
Виртуальное наследование. 86
Перегрузка функций. 90
Перегрузка операторов. 91
Перегрузка бинарного оператора. 92
Перегрузка унарного оператора. 96
Дружественная функция operator 98
Особенности перегрузки операции присваивания. 99
Перегрузка оператора [] 101
Перегрузка оператора () 104
Перегрузка оператора ->. 105
Перегрузка операторов new и delete. 106
Преобразование типа. 111
Явные преобразования типов. 111
dynamic_cast Operator. 112
Преобразования типов, определенных в программе. 115
Шаблоны.. 117
Параметризированные классы.. 117
Передача в шаблон класса дополнительных параметров. 120
Шаблоны функций. 120
Совместное использование шаблонов и наследования. 122
Шаблоны класса и friend. 124
Некоторые примеры использования шаблона класса. 124
Реализация smart-указателя. 124
Классы поддерживающие транзакции. 126
Задание значений параметров класса по умолчанию.. 129
Свойства в С++. 131
Пространства имен. 135
Ключевое слово using как директива. 136
Ключевое слово using как объявление. 137
Псевдоним пространства имен. 138
Организация ввода-вывода. 139
Состояние потока. 142
Строковые потоки. 144
Организация работы с файлами. 145
Организация файла последовательного доступа. 148
Создание файла произвольного доступа. 151
Основные функции классов ios, istream, ostream.. 154
Исключения в С++. 156
Основы обработки исключительных ситуаций. 157
Перенаправление исключительных ситуаций. 166
Исключительная ситуация, генерируемая оператором new.. 167
Генерация исключений в конструкторах. 169
Задание собственной функции завершения. 171
Спецификации исключительных ситуаций. 171
Задание собственного неожиданного обработчика. 172
Иерархия исключений стандартной библиотеки. 173
Стандартная библиотека шаблонов (STL) 174
Общее понятие о контейнере. 174
Общее понятие об итераторе. 178
Категории итераторов. 183
Основные итераторы.. 183
Вспомогательные итераторы.. 193
Операции с итераторами. 196
Контейнерные классы.. 197
Контейнеры последовательностей. 197
Контейнер последовательностей vector 197
Контейнер последовательностей list 199
Контейнер последовательностей deque. 203
Ассоциативные контейнеры.. 205
Ассоциативный контейнер multiset 205
Ассоциативный контейнер set 203
Ассоциативный контейнер multimap. 204
Ассоциативный контейнер map. 206
Адаптеры контейнеров. 206
Адаптеры stack. 206
Адаптеры queue. 207
Адаптеры priority_queue. 208
Пассивные и активные итераторы.. 209
Алгоритмы.. 212
Алгоритмы сортировки sort, partial_sort, sort_heap. 212
Алгоритмы поиска find, find_if, find_end, binary_search. 213
Алгоритмы fill, fill_n, generate и generate_n. 214
Алгоритмы equal, mismatch и lexicographical_compare. 215
Математические алгоритмы.. 217
Алгоритмы работы с множествами. 218
Алгоритмы swap, iter_swap и swap_ranges. 219
Алгоритмы copy, copy_backward, merge, unique и reverse. 220
Примеры реализации контейнерных классов. 220
Связанные списки. 220
Реализация односвязного списка. 220
Реализация двусвязного списка. 221
Реализация двоичного дерева. 226
Литература. 235
Св. план 2003, резерв
Учебное издание
Луцик Юрий Александрович,
ОБЪЕКТНО-ОРИЕНТИРОВАННОЕ ПРОГРАММИРОВАНИЕ.
ЯЗЫК С++
Учебное пособие
по курсу «Объектно-ориентированное программирование»
для студентов специальности «Вычислительные машины,
системы и сети» всех форм обучения
Редактор Т.А. Лейко
Корректор Е.Н. Батурчик
Компьютерная верстка
Подписано в печать..2003. Формат 60х84 1/16. Бумага офсетная.
Гарнитура Times New Roman. Печать ризографическая. Усл. печ. л..
Уч.- изд. л. 12,0. Тираж 200 экз. Заказ.
Издатель и полиграфическое исполнение:
Учреждение образования
«Белорусский государственный университет информатики и радиоэлектроники»
Лицензия ЛП № 156 от 05.02. 2001.
Лицензия ЛВ № 509 от 03.08. 2001.
220013, Минск, П.Бровки, 6.
|
|
|
