Цели работы
Освоение технологии реализации ассоциативных нелинейных коллекций на примере АТД «Двоичное дерево поиска».
Задание
Спроектировать, реализовать и протестировать АТД «BST -дерево» для коллекции, содержащей данные произвольного типа. Тип коллекции задаётся клиентской программой.
Двоичное дерево поиска (Binary Search Tree – BST) представляет упорядоченное, иерархическое, ассоциативное множество элементов, между которыми существуют структурные отношения «предки – потомки».
Интерфейс АТД «BST -дерево» включает следующие операции:
● опрос размера дерева (количества узлов),
● очистка дерева (удаление всех узлов),
● проверка дерева на пустоту,
● поиск данных с заданным ключом,
● включение в дерево нового узла с заданным ключом и данными,
● удаление из дерева узла с заданным ключом,
● обход узлов в дереве по схеме, заданной в варианте задания, и вывод ключей в порядке обхода,
● дополнительная операция, заданная в варианте задания.
Для тестирования коллекции интерфейс АТД «BST – дерево» включает дополнительные операции:
● вывод структуры дерева на экран.
Алгоритмы основных операций АТД (вставки, удаления и поиска) реализуются в рекурсивной форме.
Схема операции обхода: L t → t→ R t .
Дополнительная операция: определение критерия сбалансированности для всех узлов дерева (критерий сбалансированности узла = высота правого поддерева – высота левого поддерева).
Описание АТД «Дерево»
Разработанный абстрактный тип данных представляет собой ассоциативную структуру, в которой каждый экземпляр данных хранится в связке с ключом — уникальным идентификатором этих данных, встречающийся в списке единожды.
Доступ к данным осуществляется по значению ключа.
Данные:
Параметры:
Структура данных:
Бинарное дерево
Операции:
Конструктор
Вход: нет
Предусловия: нет
Процесс: создание пустой коллекции
Выход: нет
Постусловия: создана коллекция с пустой вершиной
Деструктор
Вход: нет
Предусловия: нет
Процесс: удаление коллекции
Выход: нет
Постусловия: коллекция удалена
Получение размера коллекции
Вход: нет
Предусловия: нет
Процесс: обход дерева с подсчетом
Выход: текущий размер коллекции s
Постусловия: нет
Очистка коллекции
Вход: нет
Предусловия: нет
Процесс: удаление всех значений коллекции
Выход: нет
Постусловия: коллекция пуста
Проверка коллекции на пустоту
Вход: нет
Предусловия: нет
Процесс: проверка размера дерева на пустоту
Выход: возврат булевского значения
Постусловия: нет
Вставка значения в коллекцию
Вход: ключ T и значение V
Предусловия: ключ T не встречается в дереве
Процесс: вставка узла с ключом T и значением V в коллекцию
Выход: false, если элемент не был вставлен, true, если элемент был вставлен
Постусловия: в коллекцию добавлено значение V с ключом T
Получение доступа к элементу
Вход: ключ элемента T
Предусловия: нет
Процесс: рекурсивный поиск элемента с ключом T
Выход: получение элемента с ключом T или возврат NULL
Постусловия: нет
Удаление значения
Вход: узел remove_node, булевская переменная-признак успешного удаления
Предусловия: коллекция содержит узел remove_node
Процесс: удаление узла remove_node
Выход:true, если узел был удален, false, если узел не был удален
Постусловия: из коллекции удалён узел remove_node
Вывод коллекции на экран
Вход: служебная переменная сдвига, необходимая для вывода структуры дерева на экран
Предусловия: нет
Процесс: вывод коллекции на экран
Выход: нет
Постусловия: коллекция выведена на экран
Демонстрация порядка обхода L-T-R
Вход: нет
Предусловия: нет
Процесс: обход элементов коллекции в порядке l-t-r
Выход: нет
Постусловия: ключи коллекции выведены на экран в порядке l-t-r
Определение критерия сбалансированности для всех узлов дерева
Вход: узел root
Предусловия: коллекция содержит узел root
Процесс: разность максимальной и минимальный глубины <= 1
Выход: возврат булевово значения – признак сбалансированности
Постусловия: нет
Поиск для заданного ключа предыдущего по значению ключа в дереве
Вход: ключ k
Предусловия: нет
Процесс: поиск предущего по значению ключа в дереве для заданного ключа
Выход: возврат указателя на элемент или NULL
Постусловия: нет
4.Клиентское описание класса BSTree:
BSTNode(T new_key, V new_val): L(0), R(0) //конструктор
~BSTNode() //деструктор
bool IsEmpty() //проверка коллекции на пустоту
size_t size() //Получение размера коллекции
void clear() //очистка коллекции
get(T find_key) //получения значения элемента по ключу
bool insert(BSTNode<T, V>* new_node) //вставка в коллекцию
void print_tree(int indent) // Вывод коллекции на экран
void print_ltr() // Демонстрация порядка обохода L-T-R
bool isBalanced (BSTNode<T, V>*) // Определение критерия сбалансированности для всех узлов дерева
BSTNode<T, V>* find_previous_by_key(T);
remove(BSTNode<T, V>* remove_node, bool &deleted) // Удаление значения из коллекции по ключу
Выводы
В результате проделанной работы был создан абстрактный тип данных — двоичное дерево поиска. Работоспособность класса была проверена с помощью созданной программы-меню, дающей доступ ко всем методам созданного класса.
Приложение А
Исходный код класса
Файл BST.h
#ifndef BST_H
#define BST_H
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
template<typename T = int, typename V = char>
class BSTNode
{
protected:
T key;
V val;
BSTNode<T, V>* r_max();
BSTNode<T, V>* r_parent(BSTNode<T, V>*);
public:
BSTNode(T, V);
~BSTNode();
BSTNode<T, V>* L;
BSTNode<T, V>* R;
V value();
T k();
size_t size();
void clear();
bool is_empty();
void empty_node();
BSTNode<T, V>* get(T);
bool insert(BSTNode<T, V>*);
BSTNode<T, V>* remove(BSTNode<T, V>*, bool&);
BSTNode<T, V>* remove(T, bool&);
BSTNode<T, V>* del(BSTNode<T, V>*);
void print_ltr();
void print_tree(int = 0);
BSTNode<T, V>* find_node(T);
int maxDepth(BSTNode<T, V>*);
int minDepth(BSTNode<T, V>*);
bool isBalanced(BSTNode<T, V>*);
};
//---------------------------------------------------------------------------//
template<typename T, typename V> // Constructor
BSTNode<T, V>::BSTNode(T new_key, V new_val): L(0), R(0)
{
this->key = new_key;
this->val = new_val;
}
template<typename T, typename V> // Destructor
BSTNode<T, V>::~BSTNode()
{
delete this->L;
delete this->R;
}
template<typename T, typename V> // value()
V BSTNode<T, V>::value() {
return this->val;
}
template<typename T, typename V> // k()
T BSTNode<T, V>::k() {
return this->key;
}
template<typename T, typename V> // size()
size_t BSTNode<T, V>::size() {
size_t s = 1;
if (this->L) s += L->size();
if (this->R) s += R->size();
return s;
}
template<typename T, typename V> // print_ltr()
void BSTNode<T, V>::print_ltr() {
cout << "(";
if (this->L) this->L->print_ltr();
cout << this->key << ':' << this->val;
if (this->R) this->R->print_ltr();
cout << ")";
}
template<typename T, typename V> // print_tree()
void BSTNode<T, V>::print_tree(int indent) {
if (this->R) {
this->R->print_tree(indent + 1);
}
if (indent) {
cout << std::setfill('\t') << std::setw(indent + 1) << ' ';
}
if (!this->is_empty()) {
cout << this->key << ':' << this->val << endl << ' ';
}
if (this->L) {
this->L->print_tree(indent + 1);
}
}
template<typename T, typename V> // clear()
void BSTNode<T, V>::clear() {
this->~BSTNode();
this->R = this->L = 0;
this->val = 0;
this->key = 0;
}
template<typename T, typename V> // is_empty()
bool BSTNode<T, V>::is_empty() {
return!this->R &&!this->L &&!this->val;
}
template<typename T, typename V> // get()
BSTNode<T, V>* BSTNode<T, V>::get(T find_key) {
if (this->key == find_key) return this;
else if (find_key < this->key) {
if (this->L) return this->L->get(find_key);
}
else {
if (this->R) return this->R->get(find_key);
}
return 0;
}
template<typename T, typename V> // insert()
bool BSTNode<T, V>::insert(BSTNode<T, V>* new_node) {
if (new_node->key == this->key) return false;
if (new_node->key < this->key) {
if (this->L) this->L->insert(new_node);
else this->L = new_node;
}
else {
if (this->R) this->R->insert(new_node);
else this->R = new_node;
}
return true;
}
template<typename T, typename V> // find_node()
BSTNode<T, V>* BSTNode<T, V>::find_node(T find_key) {
BSTNode<T, V>* elem = this->get(find_key);
if (!elem) return 0;
else return elem;
}
template<typename T, typename V> // r_max()
BSTNode<T, V>* BSTNode<T, V>::r_max() {
if (this->R) return this->R->r_max();
else return this;
}
template<typename T, typename V> // remove()
BSTNode<T, V>* BSTNode<T, V>::remove(T remove_node, bool &deleted) {
BSTNode<T, V>* elem = this->get(remove_node);
if (!elem) {
deleted = false;
return this;
}
return this->remove(elem, deleted);
}
template<typename T, typename V> // remove()
BSTNode<T, V>* BSTNode<T, V>::remove(BSTNode<T, V>* remove_node, bool &deleted) {
if (!remove_node) {
deleted = false;
return this;
}
if (remove_node->key < this->key) {
bool del = false;
if (!this->L) return 0;
this->L = this->L->remove(remove_node, del);
deleted = del;
return this;
}
else if (remove_node->key > this->key) {
bool del = false;
if (!this->R) return 0;
this->R = this->R->remove(remove_node, del);
deleted = del;
return this;
}
deleted = true;
if (!this->L &&!this->R) {
this->empty_node();
return 0;
}
if (!this->L) {
BSTNode<T, V>* right = this->R;
this->empty_node();
return right;
}
if (!this->R) {
BSTNode<T, V>* left = this->L;
this->empty_node();
return left;
}
this->R = this->R->del(remove_node);
return this;
}
template<typename T, typename V> // del()
BSTNode<T, V>* BSTNode<T, V>::del(BSTNode<T, V>* remove_node) {
if (this->L) {
BSTNode<T, V>* old = this->L;
this->L = this->L->del(remove_node);
delete old;
return this;
}
remove_node->key = this->key;
remove_node->val = this->val;
BSTNode<T, V>* right = this->R;
this->empty_node();
return right;
}
template<typename T, typename V> // empty_node()
void BSTNode<T, V>::empty_node() {
this->val = 0;
this->L = this->R = 0;
}
template<typename T, typename V> // r_parent()
BSTNode<T, V>* BSTNode<T, V>::r_parent(BSTNode<T, V>* elem) {
if (this == elem) return 0;
if (elem->key > this->key) {
if (this->R) {
BSTNode<T, V>* rp = this->R->r_parent(elem);
if (rp) return rp;
else return this;
}
else {
return 0;
}
}
else return this->L->r_parent(elem);
}
template<typename T, typename V> // maxDepth()
int BSTNode<T, V>::maxDepth(BSTNode<T, V>* root){
if (!root) {
return 0;
}
return 1 + max(maxDepth(root->L), maxDepth(root->R));
}
template<typename T, typename V> // minDepth()
int BSTNode<T, V>::minDepth(BSTNode<T, V>* root) {
if (!root) {
return 0;
}
return 1 + min(minDepth(root->L), minDepth(root->R));
}
template<typename T, typename V> // isBalanced()
bool BSTNode<T, V>::isBalanced(BSTNode<T, V>* root){
return (maxDepth(root) - minDepth(root) <= 1);
}
#endif // BST_H
Исходный код меню
Файл Menu.cpp
#include "stdafx.h"
#include <iostream>
#include "bst.h"
using namespace std;
// Вариант 7
int main() {
int choice = -1;
BSTNode<int, char>* root = 0, *node = 0;
int new_key;
char new_val;
bool inserted;
bool removed;
while (true) {
cout << endl << setfill('=') << setw(18) << " BST " << setw(15) << ' ' << endl;
cout << "Available actions:" << endl;
cout << "1 - create sample tree," << endl << "2 - print tree (L->t->R)," << endl << "3 - print tree (structure)," << endl;
cout << "4 - insert node (key, value)," << endl << "5 - remove node (key)," << endl << "6 - clear tree," << endl;
cout << "7 - find node by existing key," << endl << "8 - check if tree is empty," << endl;
cout << "9 - check if tree is balanced," << endl;
cout << "0 - exit." << endl << "Choice: ";
cin >> choice;
cout << endl;
new_key = 0;
new_val = 0;
inserted = false;
removed = false;
node = 0;
switch (choice) {
case 1:
if (root) delete root;
root = new BSTNode<int, char>(7, 'b');
root->insert(new BSTNode<int, char>(6, 'e'));
root->insert(new BSTNode<int, char>(10, 'f'));
root->insert(new BSTNode<int, char>(4, 'g'));
root->insert(new BSTNode<int, char>(16, 'j'));
root->insert(new BSTNode<int, char>(8, 'i'));
root->insert(new BSTNode<int, char>(12, 'c'));
root->insert(new BSTNode<int, char>(2, 'd'));
root->insert(new BSTNode<int, char>(18, 'k'));
root->insert(new BSTNode<int, char>(20, 'm'));
cout << root->size() << " node(s) in tree." << endl;
break;
case 2:
if (root) {
cout << "Tree:" << endl;
root->print_ltr();
}
else cout << "Empty tree.";
cout << endl;
break;
case 3:
if (root) {
cout << "Tree structure:" << endl;
root->print_tree();
}
else cout << "Empty tree.";
cout << endl;
break;
case 4:
cout << "Enter node key: "; cin >> new_key;
cout << "Enter node value: "; cin >> new_val;
if (root) {
inserted = root->insert(new BSTNode<int, char>(new_key, new_val));
}
else {
root = new BSTNode<int, char>(new_key, new_val);
inserted = true;
}
if (inserted) cout << "Success!" << endl;
else cout << "Failed to insert node, key exists." << endl;
break;
case 5:
if (root) {
cout << "Enter key to remove: "; cin >> new_key;
node = root->get(new_key);
if (node) {
root = root->remove(node, removed);
if (removed) {
cout << "Removed node " << new_key << ":" << node->value() << endl;
}
else cout << "Cannot remove." << endl;
}
else {
cout << "Key " << new_key << " not found in tree. Cannot remove." << endl;
}
}
else {
cout << "Empty tree." << endl;
}
break;
case 6:
if (root) {
root->clear();
root = 0;
}
cout << "Tree cleared." << endl;
break;
case 7:
if (root) {
cout << "Enter key: "; cin >> new_key;
node = root->find_node(new_key);
if (node) {
cout << "Node: " << node->k() << ":" << node->value() << endl;
}
else {
cout << "Key not found." << endl;
}
}
else {
cout << "Empty tree." << endl;
}
break;
case 8:
if (!root || root->is_empty()) cout << "Tree is empty." << endl;
else cout << "Tree is not empty, " << root->size() << " nodes." << endl;
break;
case 9:
if (root) {
if (root->isBalanced(root)) {
cout << "Tree is balanced" << endl;
}
else {
cout << "Tree is not balanced" << endl;
}
}
else {
cout << "Empty tree." << endl;
}
break;
case 0:
return 0;
break;
default:
cout << "Incorrect command. Try again." << endl;
}
}
return 0;
}