Определение длины внутреннего пути дерева
Новосибирский Государственный Технический Университет
Контрольная работа.
Коллекция данных – дерево поиска.
Выполнил:студент 3 курса
группы ЗФ-322
Белич Владимир
Проверила:Романенко Т. А.
Новосибирск 2016
Цели работы
Освоение технологии реализации ассоциативных нелинейных коллекций на примере АТД «Двоичное дерево поиска».
Задание
Спроектировать, реализовать и протестировать АТД «BST-дерево» для коллекции, содержащей данные произвольного типа. Тип коллекции задаётся клиентской программой.
Двоичное дерево поиска (Binary Search Tree – BST) представляет упорядоченное, иерархическое, ассоциативное множество элементов, между которыми существуют структурные отношения «предки – потомки».
Интерфейс АТД «BST-дерево» включает следующие операции:
· опрос размера дерева (количества узлов),
· очистка дерева (удаление всех узлов),
· проверка дерева на пустоту,
· поиск данных с заданным ключом,
· включение в дерево нового узла с заданным ключом и данными,
· удаление из дерева узла с заданным ключом,
· обход узлов в дереве по схеме, заданной в варианте задания, и вывод ключей в порядке обхода,
· дополнительная операция, заданная в варианте задания.
Для тестирования коллекции интерфейс АТД «BST – дерево» включает дополнительные операции:
· вывод структуры дерева на экран.
Алгоритмы основных операций АТД (вставки, удаления и поиска) реализуются в рекурсивной форме.
Схема операции обхода: t Lt Rt.
Дополнительная операция: определение длины внутреннего пути дерева (длина внутреннего пути = сумма глубин внутренних узлов).
3. Описание АТД «Дерево»
Разработанный абстрактный тип данных представляет собой ассоциативную структуру, в которой каждый экземпляр данных хранится в связке с ключом — уникальным идентификатором этих данных, встречающийся в списке единожды.
Доступ к данным осуществляется по значению ключа.
Данные:
Параметры:
Структура данных:
Бинарное дерево
Операции:
Конструктор
Вход: нет
Предусловия: нет
Процесс: создание пустой коллекции
Выход: нет
Постусловия: создана коллекция с пустой вершиной
Деструктор
Вход: нет
Предусловия: нет
Процесс: удаление коллекции
Выход: нет
Постусловия: коллекция удалена
Получение размера коллекции
Вход: нет
Предусловия: нет
Процесс: обход дерева с подсчетом
Выход: текущий размер коллекции
Постусловия: нет
Очистка коллекции
Вход: нет
Предусловия: нет
Процесс: удаление всех значений коллекции
Выход: нет
Постусловия: коллекция пуста
Проверка коллекции на пустоту
Вход: нет
Предусловия: нет
Процесс: проверка дерева на пустоту
Выход: возврат булевского значения
Постусловия: нет
Вставка значения в коллекцию
Вход: ключ Kи значение T
Предусловия: ключ Kне встречается в дереве
Процесс: вставка узла сключом Kи значением T в коллекцию
Выход: false, если элемент не был вставлен, true, если элемент был вставлен
Постусловия: в коллекцию добавлено значение Tс ключом K
Получение доступа к элементу
Вход: ключ элемента K
Предусловия: нет
Процесс: рекурсивный поиск элемента с ключом K
Выход: получение значения T элемента с ключом K
Постусловия: нет
Удаление значения
Вход: ключ K
Предусловия: коллекция содержит ключ K
Процесс: удаление узла c ключом K
Выход: true, если узел был удален, false, если узел не был удален
Постусловия: из коллекции удалён узел с ключом K
Вывод коллекции на экран
Вход: нет
Предусловия: нет
Процесс: вывод коллекции на экран
Выход: нет
Постусловия: коллекция выведена на экран
Демонстрация порядка обхода t – L – R
Вход: нет
Предусловия: нет
Процесс: обход элементов коллекции в порядке t-L-R
Выход: нет
Постусловия: ключи коллекции выведены на экран в порядке t-L-R
Определение длины внутреннего пути дерева
Вход: нет
Предусловия: коллекция не пуста
Процесс: подсчет длины внутреннего пути
Выход: возврат числового значения
Постусловия:нет
4.Клиентское описание класса Tree:
Tree() // конструктор
~ Tree() // деструктор
int nodeCount() // получение размера коллекции
void clear() // очистка коллекции
bool isClean() // проверка коллекции на пустоту
bool add(const K &key, const T &elem) // вставка в коллекцию
T search(T key) // получения значения элемента по ключу
bool removeByKey(K key) // удаление значения из коллекции по ключу
void print() // вывод коллекции на экран
void tLR() // демонстрация порядка обохода t-L-R
int getLength() // определение длины внутреннего пути дерева
Выводы
В результате проделанной работы был создан абстрактный тип данных — двоичное дерево поиска. Работоспособность класса была проверена с помощью созданной программы-меню, дающей доступ ко всем методам созданного класса.
Приложение А
Исходный код класса
Файл classes.h
#ifndef __CLASSES_H__
#define __CLASSES_H__
template <class K, class T>
class Tree {
protected:
class Node {
public:
K key;
T item;
Node *left;
Node *right;
Node(K k, T i, Node *s = NULL, Node *b = NULL){
key = k;
item = i;
left = s;
right = b;
}
};
Node *root;
public:
K tmpKey;
T tmpItem;
int length;
Tree(){
root = NULL;
length = 0;
}
~Tree(){
deleteSubtree(root);
}
int nodeCount(){
return nodeCount_helper(root);
};
void clear(){
deleteSubtree(root);
root = NULL;
};
bool isClean(){
return (root)? true : false;
}
bool add(const K &key, const T &elem){
return add_helper(root, key, elem);
}
T search(K search){
return search_helper(root, search);
}
bool removeByKey(K key){
bool deleted = false;
removeByKey_helper(root, key, deleted);
return deleted;
};
void print(){
print_helper(root, 0);
}
void tLR(){
return tLR_helper(root);
}
int getLength(){
return getLength_helper(root, 1);
}
private:
int nodeCount_helper(Node *node);
bool add_helper(Node *&node, const K &key, const T &elem);
T search_helper(Node *node, K search);
Node* removeByKey_helper(Node *&root, K key, bool &deleted);
void print_helper(Node *node, int spaces);
void tLR_helper(Node *node);
int getLength_helper(Node *node, int i);
void deleteSubtree(Node *node);
Node* findMin(Node *root);
};
template <class K, class T>
typename Tree<K, T>::Node* Tree<K, T>::findMin(Node* root){
while(root->left != NULL) root = root->left;
return root;
};
template <class K, class T>
typename Tree<K, T>::Node* Tree<K, T>::removeByKey_helper(Node *&root, K data, bool &deleted){
if(root == NULL){
return root;
} else if(data < root->key){
root->left = removeByKey_helper(root->left, data, deleted);
} else if (data > root->key){
root->right = removeByKey_helper(root->right, data, deleted);
} else {
if(root->left == NULL && root->right == NULL) {
delete root;
root = NULL;
deleted = true;
} else if(root->left == NULL && root->right != NULL) {
Node *temp = root;
root = root->right;
delete temp;
deleted = true;
} else if(root->right == NULL && root->left != NULL) {
Node *temp = root;
root = root->left;
delete temp;
deleted = true;
} else {
Node *temp;
if(root->right)
temp = findMin(root->right);
else
temp = root->left;
root->key = temp->key;
root->item = temp->item;
root->right = removeByKey_helper(root->right, temp->key, deleted);
}
}
return root;
};
template <class K, class T>
int Tree<K, T>::getLength_helper(Node *node, int i){
int local = 0;
if(!node){
return 0;
}
if(node->left && node->right)
local += i;
local += getLength_helper(node->left, i+1) + getLength_helper(node->right, i+1);
return local;
};
template <class K, class T>
void Tree<K, T>::tLR_helper(Node *node){
if(node){
cout << node->key << " ";
tLR_helper(node->left);
tLR_helper(node->right);
}
};
template <class K, class T>
int Tree<K, T>::nodeCount_helper(Node *node){
int cnt = 0;
if(node){
cnt += nodeCount_helper(node->right);
cnt += nodeCount_helper(node->left);
cnt++;
}
return cnt;
};
template <class K, class T>
void Tree<K, T>::deleteSubtree(Node *node){
if(node){
deleteSubtree(node->left);
deleteSubtree(node->right);
delete node;
}
};
template <class K, class T>
bool Tree<K, T>::add_helper(Node *&node, const K &key, const T &item){
if(node == NULL){
node = new Node(key, item);
return true;
} else if(key == node->key){
return false;
} else if(key < node->key){
add_helper(node->left, key, item);
} else {
add_helper(node->right, key, item);
}
};
template <class K, class T>
T Tree<K, T>::search_helper(Node *node, K search){
if (node == NULL){
T val;
return val;
}
if(node->key == search){
return node->item;
}
if(search <= node->key){
if(node->left != NULL)
return search_helper(node->left, search);
} else {
if(node->right != NULL)
return search_helper(node->right, search);
}
T val;
return val;
};
template <class K, class T>
void Tree<K, T>::print_helper(Node *node, int spaces){
while (node != NULL){
if(node->right)
print_helper(node->right, spaces + 5);
for (int i = 1; i < spaces; ++i)
std::cout << ' ';
//std::cout << "(" << node->key << ")=" << node->item << std::endl;
std::cout << "(" << node->key << ")" << std::endl;
node = node->left;
spaces += 5;
}
};
#endif // __CLASSES_H__
Исходный код программы