Динамічні структури даних
Мiнiстерство освiти і науки, молоді та спорту України
Національний університет «Львівська політехніка»
Кафедра ЕОМ
Курсова
робота
з дисципліни «Програмування. Частина
ІІІ.
Структури даних та алгоритми»
Завдання 2: Динамічні структури даних
Вибір індивідуального варіанту:
Вибір АТД: № = (12 + 1994 + 97)%4+1= 4 – АТД «Дерево»
Вибір номера завдання: № = (7 + 1993 + 66)%10+1 = 6 – варіант завдання
Виконав:
студент групи КІ-23
Барнінець Юрій
Прийняла:
Матвейчук Т.А
Львів – 2013
Зміст
Завдання 2: Динамічні структури даних
ЗМІСТ
1. ТЕОРЕТИЧНА
ЧАСТИНА ______________________________
2. ЗАВДАННЯ
3. ПОБУДОВА АТД ______________________________
2.1. Постановка
задачі________________________
2.2. Динаміка
вмісту________________________
2.3. Результати
виконання програми______________________
3. ЗАВДАННЯ
4. ЗАСТОСУВАННЯ АТД__________________________
3.1. Постановка
задачі________________________
3.2. Алгоритм
розв’язання задачі________________________
3.2.1. Словесний
опис алгоритму________________
3.2.2. Граф-схема
алгоритму_____________________
3.3. Результати
виконання програми______________________
ВИСНОВКИ
СПИСОК ЛІТЕРАТУРИ
ДОДАТОК А. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 3
ДОДАТОК Б. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ
4
Завдання 2: Динамічні структури даних
1. ТЕОРЕТИЧНА ЧАСТИНА
Дерево – одна з найбільш широко поширених структур даних в інформатиці, рафіч деревоподібну структуру у вигляді набору пов’язаних вузлів. Є пов’язаною графом, що не містить цикли. Більшість джерел також додають умова на те, що ребра графа не повинні бути орієнтованими. На додаток до цих трьох обмежень, в деяких джерелах вказуються, що ребра графа не повинні бути зваженими.
Визначення
- Кореневий
вузол – самий верхній вузол дерева.
- Корінь – одна з вершин, за бажанням
спостерігача.
- Листовий вузол або лист – вузол самого
нижнього рівня дерева.
- Листя дерева – коріння, з яких не виходить
жодної дуги.
- Внутрішній вузол – будь-який вузол
дерева, що має нащадків, і таким чином
не є листовим вузлом.
- Дерево вважається орієнтованим, якщо
в корінь не заходить ні одне ребро.
- Дерево визначення – рафічна діаграма
схеми бази даних.
- Повний зчеплений ключ – ідентифікатор
запису, який утворюється шляхом конкатенації
всіх ключів примірників батьківських
записів (груп).
Вузли
Вузол є екземпляром одного з двох типів елементів графа, відповідним об’єкту деякої фіксованої природи. Вузол може містити значення, стан або подання окремої інформаційної структури або самого дерева. Кожен вузол дерева має нуль або більше вузлів-нащадків, які розташовуються нижче по дереву (за угодою, дерева ‘ростуть’ вниз, а не вгору, як це відбувається з справжніми деревами). Вузол, що має нащадка, називається вузлом-батьком щодо свого нащадка (або вузлом-попередником, або старшим). Кожен вузол має не більше одного предка. Висота вузла – це максимальна довжина спадного шляху від цього вузла до самого нижнього вузла (крайовій вузла), званому листом. Висота кореневого вузла дорівнює висоті всього дерева. Глибина вкладеності вузла дорівнює довжині шляху до кореневого вузла
Кореневі вузли
Самий верхній вузол дерева називається кореневим вузлом. Бути самим верхнім вузлом на увазі відсутність у кореневого вузла предків. Це вузол, на якому починається виконання більшості операцій над деревом (хоча деякі алгоритми починають виконання з «листків» і виконуються, поки не досягнуть кореня). Всі інші вузли можуть бути досягнуті шляхом переходу від кореневого вузла по ребрах (або посилання). (Згідно формального визначення, кожен подібний шлях повинен бути унікальним). У діаграмах він зазвичай зображується на самій вершині. У деяких деревах, наприклад, купах, кореневий вузол має особливі властивості. Кожен вузол дерева можна розглядати як кореневий вузол піддерева, «зростаючого» з цього вузла.
Листові вузли
Вузли самого нижнього рівня дерева називаються листовими вузлами або листям. Так як вони знаходяться на самому нижньому рівні, вони не мають жодних нащадків.
Внутрішні вузли
Внутрішній
вузол – будь-який вузол дерева, що має
нащадків, і таким чином не є листовим
вузлом.
Піддерева
Піддерево – частина деревообразной структури даних, яка може бути представлено у вигляді окремого дерева. Будь-який вузол дерева T разом з усіма його вузлами-нащадками є піддерево дерева T. Для будь-якого вузла піддереві або має бути шлях у кореневий вузол цього піддерева, або сам вузол повинен бути кореневим. Тобто піддерево пов’язано з кореневим вузлом цілим деревом, а відносини піддерева з усіма іншими вузлами визначаються через поняття відповідне піддерево (за аналогією з терміном «відповідне підмножина»).
Упорядкування дерев
Існує два основних типи дерев. У рекурсивному дереві чи неврегульованих дереві має значення лише структура самого дерева без урахування порядку нащадків для кожного вузла. Дерево, в якому заданий порядок (наприклад, кожному ребру, ведучому до нащадка, надані різні натуральні числа) називається деревом з іменованими ребрами або впорядкованим деревом із структурою даних, визначеної перед ім’ям і званої структурою даних упорядкованого дерева.
Впорядковані дерева є найбільш поширеними серед деревоподібних структур. Бінарне дерево пошуку – одна з різновидів упорядкованого дерева.
Представлення дерев
Існує безліч різних способів подання дерев. Найбільш загальний спосіб представлення зображує вузли як записи, розташовані в динамічно виділюваної пам’яті з дороговказами на своїх нащадків, предків (або і тих і інших), або як елементи масиву, пов’язані між собою відносинами, певними їх позицій в масиві (наприклад, двійкова купа) .
Дерева як графи
У теорії графів дерево – пов’язаний ациклічний граф. Кореневе дерево – це граф з вершиною, виділеної в якості кореневої. У цьому випадку будь-які дві вершини, пов’язані ребром, успадковують відносини «батько-нащадок». Ациклічний граф з безліччю пов’язаних компонентів або набір кореневих дерев іноді називається лісом.
Методи обходу
Покроковий перебір елементів дерева у зв’язках між предками-вузлами і нащадками-вузлами називається обходом дерева, а сам процес називається обходом по дереву. Найчастіше, операція може бути виконана переходом покажчика по окремих вузлах. Обхід, при якому кожен вузол-предок проглядається насамперед його нащадків називається предупорядоченним обходом або обходом в прямому порядку (pre-order walk), а коли проглядаються спочатку нащадки, а потім предки, то обхід називається поступорядоченним обходом або обходом у зворотному порядку (post- order walk). Існує також симетричний обхід, при якому відвідується спочатку ліве піддерево, потім вузол, потім – праве піддерево, і обхід в ширину, при якому вузли відвідуються рівень за рівнем (N-й рівень дерева – безліч вузлів з висотою N). Кожен рівень обходиться зліва направо.
2.ЗАВДАННЯ 3. ПОБУДОВА АТД
2.1. Постановка задачі
Побудувати бінарне дерево пошуку для послідовності чисел, що вводяться з клавіатури. Реалізувати операції додавання та вилучення вузлів з бінарного дерева пошуку. Виконати обхід дерева у заданому порядку та показати:
1. Послідовність вершин дерева при проходженні його у прямому порядку;
2. Послідовність листків дерева при проходженні його у зворотньому порядку;
3. Послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку.
Виконати індивідуальне
Вилучити з дерева всi вузли, що мають тільки одного безпосереднього нащадка.
2.2. Динаміка вмісту дерева
Послідовність 10 чисел:
15, 2, 8, 17, 3, 9, 19, 1, 16, 22
Схематичне зображення БД пошуку після
обробки кожного числа з
Add(15);
Add(2);
Add(8);
Add(3);
Add(9);
Add(19);
Add(1);
Add(16);
Add(22);
Реалізація БД пошуку на базі масиву розмірністю 17:
Оскільки отримане бінарне дерево не є повним, а повне дерево найзручніше представляти у вигляді масивів, тому що воно завжди має строго певне число вершин на кожному рівні. Вершини можна пронумерувати зліва направо послідовно по рівнях і використати ці номери як індекси в одновимірному масиві. Отож, я виконаю модифікацію отриманого БД до повного. Після того, як я отримаю повне БД пошуку, я можу виконувати нумерацію вершин.
індекс |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
data |
15 |
2 |
17 |
1 |
8 |
16 |
19 |
x |
x |
3 |
9 |
x |
x |
x |
22 |
x |
x |
Головним недоліком
Обхід БД пошуку:
а) послідовність вершин дерева при проходженні його у прямому порядку:
15 – 2 – 1 – 8 – 3 – 9 – 17 – 16 – 19 – 22
б) послідовність листків дерева при проходженні його у зворотному порядку:
1 – 3 – 9 – 16 – 22
в) послідовність вузлів, що мають
тільки одного нащадка при проходженні
дерева у симетричному порядку:
19
г) Вилучити з дерева всi вузли, що мають тільки одного безпосереднього нащадка:
2.3. Результати виконання програми
Результат виконання програми показано на рис. 1
Рис.1
3. ЗАВДАННЯ 4. ЗАСТОСУВАННЯ АТД
3.1. Постановка задачі
Задано рядок символів S і набір слів А[1], …, A[k]. Написати програму розбиття рядка S на слова з набору всіма можливими способами.
Приклад: Вхідні дані Результат розбиття
S=ABBC S = A – B – BC
A[1]=A, S = A – BBC
A[2]=AB, S = AB – BC
A[3]=BC,
A[4]=BBC,
A[5]=H,
A[6]=B
3.2. Алгоритм розв’язання задачі
3.2.1. Словесний опис алгоритму
Грубо кажучи алгоритм реалізації даної задачі зводиться до двох етапів:
- Реалізувати алгоритм, який би на базі БД пошуку представив всі можливі комбінації розбиття рядка S на підрядки:
- В корені дерева зберігається рядок, який необхідно розділити на всі можливі комбінації
- Я умовно виділив 2 правила, послідовно застосовуючи які,ми отримуємо необхідне дерево:
1 правило розподілу:
Беремо першу літеру з вузла та розміщуємо її як лівого сина даного вузла, а правим сина робимо копію батька. Дальше, для другого вузла беремо дві літери і розміщуємо як лівого сина для даного вузал, а правим сином знову робимо копію батька, цей процес виконуємо доти, доки довжина лівого сина не буде менша за батька на 1.
Проілюструю графічно цей процес:
Після виконання правила 1 нам необхідно виконати над листками правило 2, які утворились після виконання правила 1
2 правило розподілу:
Нам необхідно знайти батька листка і зробити різницю рядків між ним і листком, тобто ті символи, які відсутні в листка, а є в батька, записати правому сину даного листка.
Проілюструю графічно цей процес:
Отож, правило 1 та правило 2 необхідно послідовно виконувати над даним деревом доти, доки не утворяться листки, для яких це правило не є актуальним:
- Листок містить одну літеру і не підлягає поділу
- Листок містить к-сть літер, які і його батько і не підлягає правилу 2
Виконуючи дані правила у нас утвориться БД пошуку, яке містити всі можливі комбінації розбиття рядка S на підрядки.
- Маючи БД пошуку з усіма можливими комбінаціями ми виконуємо над ним відповідний прохід, аналізуючи який, шукаємо комбінації, які можуть складатись із слів масиву.
Що я маю на увазі під «відповідним» проходом?
Подивившись на дерево яке утвориться, стає не важко помітити те, що всі вузли, які не мають лівого нащадка є елементами можливих комбінацій. Прохід необхідно виконувати в прямому порядку по вузлах, які не мають лівого нащадка. Якщо ми під час проходу зустрічаємо вузол, значення якого не має в жодному елементі масиву, то немає необхідності дальше виконувати прохід, оскільки дана комбінація нас не задовольнятиме, в такому випадку нам необхідно припинити прохід, перейти в корінь і виконати наступний обхід.
Комбінація нас задовольнятиме в тому випадку, якщо під час проходу по дереву зустрічались в нашому масиві всі значення вузлів, аж до самого листка включно.
- Граф-схема алгоритму
Рис. 2 Граф-схема алгоритму
3.3. Результати виконання програми
Для наочності та універсальності алгоритму я вирішив навести скріни з декількома комбінаціями вхідних даних:
Висновки
Виконуючи практичну
сторону теоретичного матеріалу, який
ми вивчали на лекціях про АТД
«Дерево» я засвоїв принцип реалізації
АТД «Дерева» на базі вказівників. Також,
я усвідомив наскільки
Список літератури
- Шпак 3.Я. Програмування мовою С. - Львів: Оріяна-Нова, 2006. - 432 с.
- Грегори К. Использование Visual С++. Специальное издание. - М.: «Диалектика», 1999.
- Мешков А.В., Тихомиров Ю.В. Visual С++ и MFC. Пер. с англ. – 2-е изд. перераб. и доп. – СПб.: БХВ - Петербург, 2002. – 1040 с.
- Страуструп Б. Язык программирования С++. Третье издание. - М.: «Издательство Бином», 1999.
- Трамбле Ж., Соренсон П. Введение в структуры данных. – М.:Машиностроение, 1982
- Уильям Топп, Уильям Форд. Структуры данных в С++. – М.:Бином, 2000 - 700 с
- Конспект лекцій
Додатки
ДОДАТОК А. ТЕКСТ ПРОГРАМИ ДО ЗАВДАННЯ 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) // доки не кінець дерева
- Династия Бахрушиных
- Династия как субъект социально-культурной деятельности
- Династия Мин: от становления до заката
- Династия Романовых
- Династия Романовых
- Династия Романовых. Роль отца в жизни Николая 2
- Дини туризм
- Динаміка політичної довіри сучасних українських громадян
- Динаміка процесу заучування у молодших підлітків
- Динаміка систем багатьох частинок
- Динаміка сукупного попиту в Україні за 2008 – 2010р
- Динаміка чисельності населення Тернопільської області за 2000-2010 роки
- Динаміки чисельності населення і його статево-віковою склад за період 1996 - 2006 рік
- Динамічні процеси в малій групі