Автор: Пользователь скрыл имя, 10 Апреля 2013 в 01:11, курсовая работа
Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати:
1. Послідовність вершин дерева при проходженні його у прямому порядку;
2. Послідовність листків дерева при проходженні його у зворотньому порядку;
3. Послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку.
1. ТЕОРЕТИЧНА ЧАСТИНА _______________________________________3
2. ЗАВДАННЯ 3. ПОБУДОВА АТД _______________________________ 6
2.1. Постановка задачі_________________________________________ 6
2.2. Динаміка вмісту___________________________________________ 6
2.3. Результати виконання програми______________________________9
3. ЗАВДАННЯ 4. ЗАСТОСУВАННЯ АТД__________________________10
3.1. Постановка задачі_________________________________________10
3.2. Алгоритм розв’язання задачі________________________________10
3.2.1. Словесний опис алгоритму_____________________________11
3.2.2. Граф-схема алгоритму_________________________________12
3.3. Результати виконання програми_____________________________13
ВИСНОВКИ
СПИСОК ЛІТЕРАТУРИ
ДОДАТОК А. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 3
ДОДАТОК Б. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ
Виконуючи дані правила у нас утвориться БД пошуку, яке містити всі можливі комбінації розбиття рядка S на підрядки.
Що я маю на увазі під «відповідним» проходом?
Подивившись на дерево яке утвориться, стає не важко помітити те, що всі вузли, які не мають лівого нащадка є елементами можливих комбінацій. Прохід необхідно виконувати в прямому порядку по вузлах, які не мають лівого нащадка. Якщо ми під час проходу зустрічаємо вузол, значення якого не має в жодному елементі масиву, то немає необхідності дальше виконувати прохід, оскільки дана комбінація нас не задовольнятиме, в такому випадку нам необхідно припинити прохід, перейти в корінь і виконати наступний обхід.
Комбінація нас задовольнятиме в тому випадку, якщо під час проходу по дереву зустрічались в нашому масиві всі значення вузлів, аж до самого листка включно.
Рис. 2 Граф-схема алгоритму
3.3. Результати виконання програми
Для наочності та універсальності алгоритму я вирішив навести скріни з декількома комбінаціями вхідних даних:
Висновки
Виконуючи практичну
сторону теоретичного матеріалу, який
ми вивчали на лекціях про АТД
«Дерево» я засвоїв принцип реалізації
АТД «Дерева» на базі вказівників. Також,
я усвідомив наскільки
Список літератури
Додатки
ДОДАТОК А. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 3
main.cpp
#include "binary_tree.h"
typedef int TypeOfElement;
void main()
{
setlocale (0, "Ukr");
// Створення вектора
елементів в якому
vector<TypeOfElement> item;
TypeOfElement t; // тимчасова змінна, яку використовуємо для введення кожного елементу
BinaryTree<TypeOfElement> tr;
cout << "Введiть послiдовнiсть з 10 елементiв:\n";
for (int i=0;i<10;i++) {
cin >> t;
item.push_back(t); // зчитування 1-ї послiдовностi
}
//Отримавши вектор із послідовністю формуємо БД пошуку
for (int i = 0; i < item.size(); ++i)
{
tr.Add(tr.RefRoot(), item[i]);
cout << "\n---------------------------
tr.PrintTree(tr.RRoot(), 20, 1); // Ф-ція, яка виводить дерево
}
cout << endl;
cout << "Прямий прохiд по дереву:\n";
tr.Direct_way(tr.RRoot()); // прямий прохiд
cout << endl;
cout << "Зворотнiй прохiд по дереву:\n";
tr.Reverse_way(tr.RRoot()); // послiдовнiсть листкiв дерева при проходженнi його у зворотньому порядку
cout << endl;
cout << "Симетричний прохiд по дереву:\n";
tr.Symmetric_way(tr.RRoot()); // послiдовнiсть вузлiв, що мають тiльки одного нащадка при проходженнi дерева у симетричному порядку
cout << endl;
cout << "Дерево пiсля видалення вузлiв, як мають тiльки одного безпосереднього нащадка:\n";
tr.induvidual(tr.RefRoot());
tr.PrintTree(tr.RRoot(), 20, 1);
cout << endl;
system("pause");
}
binary_tree.h
#include <iostream>
#include <vector>
using namespace std;
template <class T>
class BinaryTree
{
private:
struct TreeElement
{
TreeElement *right;
TreeElement *left;
T data;
}; // опис структури зберігання
TreeElement *root; // вказівник на корінь
void Del_Help(TreeElement **root_ptr, TreeElement **del_node_ptr); // допоміжна ф-я для видалення
TreeElement * LeftSon(TreeElement *tr) // визначення лівого елемента
{
if (tr != NULL)
return tr->left;
else
return tr;
};
TreeElement * RightSon(TreeElement *tr) // визначення правого елемента
{
if (tr != NULL)
return tr->right;
else
return tr;
};
public:
BinaryTree(); // конструктор за замовчуванням
BinaryTree(T item, TreeElement *lptr = NULL, TreeElement *rptr = NULL); // конструктор з параметрами
~BinaryTree(); // деструктор
bool Add(TreeElement **rt, T item); // додавання елемента до дерева
bool Delete(TreeElement **rt, T item); // видалення заданого вузла
TreeElement ** RefRoot() { return &root; } // повернення ссилки кореня
TreeElement * RRoot() const { return root; } // повернення вказiвника на корiнь
void PrintTree(TreeElement * rt, int k, int i); // Вивiд дерева
void Direct_way(TreeElement *rt); // Проходження всiх вузлiв БД в прямому порядку
void Symmetric_way(TreeElement *rt); // послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку
void Reverse_way(TreeElement *rt); // послідовність листків дерева при проходженні його у зворотньому порядку
bool empty() const; // визначення чи пусте дерево
void induvidual(TreeElement **rt) // допоміжна функція для функцій is_mirror
{
if ( ((LeftSon(*rt)==NULL) & (RightSon(*rt)!=NULL)) | ((LeftSon(*rt)!=NULL) & (RightSon(*rt)==NULL)) ) {
TreeElement *del;
del = *rt; // зберігаєм адресу елемента для видалення
if (!del->right) // якшо немає правого елемента
*rt = LeftSon(del); // ставим замість нього лівий
else if (! LeftSon(del)) // якшо немає лівого елемента
*rt = RightSon(del); // ставим замість нього правий
else // якщо є 2 елементи
if (! LeftSon(del))
*rt = RightSon(del);
else
Del_Help(&del->right, &del); // виклик допоміжної ф-ї
delete del; // видаляєм вузол
} else {
if ( (LeftSon(*rt)!=NULL) & (RightSon(*rt)!=NULL) ) {
induvidual(&(*rt)->left);
induvidual(&(*rt)->right);
}
}
}
};
template <class T>
BinaryTree<T>::BinaryTree() // ств. пустого дерева
{
root = new TreeElement;
root = NULL;
}
template <class T>
BinaryTree<T>::BinaryTree(T item, TreeElement *lptr, TreeElement *rptr)
{
root = new TreeElement; // ств. дерева, із з"єднанням
root->data = item;
root->left = lptr;
root->right = rptr;
}
template <class T>
BinaryTree<T>::~BinaryTree() // деструктор
{}
template <class T>
bool BinaryTree<T>::empty() const // true якщо дерево пусте та false в іншому випадку
{
return root == NULL;
}
template <class T>
void BinaryTree<T>::Direct_way(
{
if (rt)
{
cout << rt->data << " ";
Direct_way(LeftSon(rt));
Direct_way(RightSon(rt));
};
}
template <class T>
void BinaryTree<T>::Symmetric_way(
{
if (rt)
{
Symmetric_way(LeftSon(rt));
if (!(rt->left == NULL && rt->right == NULL)) // якщо не 2 нащадки
if (rt->left == NULL || rt->right == NULL) // якщо лише один нащадок
cout << rt->data << " ";
Symmetric_way(RightSon(rt));
}
}
template <class T>
void BinaryTree<T>::Reverse_way(
{
if (rt)
{
Reverse_way(LeftSon(rt));
Reverse_way(RightSon(rt));
if (rt->left == NULL && rt->right == NULL) // якщо це листок
cout << rt->data << " ";
}
}
template <class T>
bool BinaryTree<T>::Add(TreeElement **rt, T item) // додавання ел. в БД
{
if (*rt == NULL) // якщо немає наступного вузла
{
TreeElement *add = new TreeElement; // виділення пам"яті під ел.
add->data = item; // заносим в інформаційне поле
add->left = add->right = NULL; // занулюєм Вказівники на наступні ел.
*rt = add; // з"єднуєм з деревом
}
else
{
if (item < ((*rt)->data))
Add(&((*rt)->left), item); // переходим на наступний лівий
else
Add(&((*rt)->right), item); // переходим на наступний правий
}
return true;
}
template <class T>
void BinaryTree<T>::Del_Help(
{
if (LeftSon(*root_ptr)) // якщо лівий ел. != NULL
Del_Help(&((*root_ptr)->left), del_node_ptr); // виконуєм цю ф-ю для наступного лівого ел.
else // в іншому випадку
{
(*del_node_ptr)->data = (*root_ptr)->data; // заміщуєм інформаційне поле
*del_node_ptr = *root_ptr; // присвоюєм адресу для видалення
*root_ptr = RightSon(*root_ptr); // підтягуєм нижній елемент
}
}
template <class T>
bool BinaryTree<T>::Delete(
{
TreeElement *del;
if (*rt) // якщо не кінець дерева
if (item < (*rt)->data)
Delete(&((*rt)->left), item); // проходим на лівий
else if (item > (*rt)->data)
Delete(&((*rt)->right), item); // проходим на правий
else
{
del = *rt; // зберігаєм адресу елемента для видалення
if (!del->right) // якшо немає правого елемента
*rt = LeftSon(del); // ставим замість ньго лівий
else if (! LeftSon(del)) // якшо немає лівого елемента
*rt = RightSon(del); // ставим замість ньго правий
else // якщо є 2 елементи
if (! LeftSon(del))
*rt = RightSon(del);
else
Del_Help(&del->right, &del); // виклик допоміжної ф-ї
delete del; // видаляєм вузол
}
return true;
}
template <class T>
void BinaryTree<T>::PrintTree(
{
char c;
if (rt != NULL) // доки не кінець дерева
{
cout << endl;
for (c = 1; c <= 40 + i; c++)
cout << " "; // відступ
cout << rt->data; // вивід інф. поля
// рекурсивний виклик ф-й
PrintTree(rt->left, k/2, i-k);
PrintTree(rt->right, k/2, i+k);
}
return;
}
ДОДАТОК Б. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 4
main.cpp
#include "tree.h"
void main()
{
setlocale (0, "Ukr");
int count,i;
string S; //рядок символів
cout << "Введiть рядок S:";
cin >> S;
cout << "Введiть к-сть слiв в масивi A:";
cin >> count;
BinaryTree<string> tr(S,count); //створюємо об'єкт типу дерево
tr.input_words(count); //вводимо масив слів
tr.first_rule(tr.RefRoot()); //Генеруємо дерево за першим правилом на початковий етап генерації
//Визначаємо довжину
вхідного рядка, для того,щоб
знати скільки раз
for (i=0; i<(S.length()+1)*2;i++) {//ГЕНЕРАЦІ ДЕРЕВА З УСІМА МОЖЛИВИМИ КОМІБАНЦІЯМИ
tr.go_for_lustok_2(tr.RRoot())
tr.go_for_lustok_1(tr.RRoot())
}
cout << "\nРезультат розбиття:\n";
tr.check_comb(tr.RRoot(),1); //ОБХІД ПО ВСІХ КОМБІНАЦІЯХ ДЕРЕВА ТА ПОРІВНЯННЯ З МАСИВОМ ПІДРЯДКІВ
cout << endl;
}
tree.h
#include <iostream>
#include <string>
#include <vector>
using namespace std;
template <class T>
class BinaryTree
{
string *A;//Масив слів
string tmp[100],comb; //тимчасові службові дані
int count;//К-сть слів в масиві
private:
struct TreeElement
{
TreeElement *right;
TreeElement *left;
TreeElement *parent;
T data;
int plv; // актуальний тільки для правого нащадка(оскільки там поділ)
int go_l; //мітка про відвідування 0 - небув, 1 - був
int go_r;
}; // опис структури зберігання
TreeElement *root; // вказівник на корінь
void Del_Help(TreeElement **root_ptr, TreeElement **del_node_ptr); // допоміжна ф-я для //видалення
public:
BinaryTree(); // конструктор за замовчуванням
BinaryTree(T item, int count); // конструктор з параметрами
~BinaryTree(); // деструктор
bool Add(TreeElement **rt, T item); // додавання елемента до дерева
bool Delete(TreeElement **rt, T item); // видалення заданого вузла
TreeElement ** RefRoot() { return &root; } // повернення ссилки кореня
TreeElement ** Right_Son() { return &root->right; } // повернення ссилки кореня
TreeElement ** Left_Son() { return &root->left; } // повернення ссилки кореня
TreeElement * RRoot() const { return root; } // повернення вказiвника на корiнь
void PrintTree(TreeElement * rt, int k, int i); // Вивiд дерева
bool empty() const; // визначення чи пусте дерево
TreeElement * LeftSon(TreeElement *tr) // визначення лівого елемента
{
if (tr != NULL)
return tr->left;
else
return tr;
};
TreeElement * RightSon(TreeElement *tr) // визначення правого елемента
{
if (tr != NULL)
return tr->right;
else
return tr;
};
void first_rule(TreeElement **rt); // допоміжна функція для функцій is_mirror
void second_rule(TreeElement **rt);
void go_for_lustok_2(TreeElement * rt);
void go_for_lustok_1(TreeElement * rt);
void check_comb(TreeElement *rt,int stan);
void find_db_vuzol(TreeElement *rt);
void Reverse_way(TreeElement *rt);
void input_words(int count);
};
template <class T>
BinaryTree<T>::BinaryTree() // ств. пустого дерева
{
root = new TreeElement;
root = NULL;
}
template <class T>
BinaryTree<T>::BinaryTree(T item, int cnt)
{
root = new TreeElement; // ств. дерева, із з"єднанням
root->data = item;
root->left = NULL;
root->right = NULL;
root->parent = 0;
root->plv = 0;
root->go_r=0;
root->go_l=0;
A=new string[cnt];//динамічно виділяємо пам'ять під слова
count = cnt; //ініціалізуємо змінну, яка зберігає к-сть слів
}
template <class T>
BinaryTree<T>::~BinaryTree(){}
template <class T>
bool BinaryTree<T>::empty() const // true якщо дерево пусте та false в іншому випадку
{
return root == NULL;
}
template <class T>
void BinaryTree<T>::go_for_lustok_
if (rt != NULL) // доки не кінець дерева