Определение длины внутреннего пути дерева

Новосибирский Государственный Технический Университет

Контрольная работа.

Коллекция данных – дерево поиска.

Выполнил:студент 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__

Исходный код программы