Зміст
Анотація
Введення
Теоретичний розділ
.1 Визначення бінарного дерева
.2 Впорядковане двійкове дерево і його властивості
. Двійкові дерева пошуку
Проектний розділ
Програмний розділ
Експериментальний розділ
Висновок
Список використаних джерел
Додаток I
Введення
Організація даних за допомогою бінарних дерев полегшує програмування і дозволяє значно скоротити час пошуку потрібного елемента. Пошук елемента в лінійних структурах даних зазвичай здійснюється шляхом послідовного перебору всіх елементів, присутніх в даній структурі. Пошук по дереву не вимагає перебору всіх елементів, тому займає значно менше часу. p align="justify"> Основною метою даної роботи є вивчення фундаментальної абстрактної структури - дерево, а також програмна реалізація додавання даних до впорядкованого двійкове дерево. Крім того, необхідно закріпити теоретичні знання та практичні навички в програмуванні мовою високого рівня C/C + +. p align="justify"> Для досягнення мети були поставлені і вирішені наступні завдання:
) закріпити практичні навички програмування мовою Сі;
) сформулювати завдання;
) виходячи з поставленої мети, побудувати правильний і найбільш оптимальний алгоритм;
) реалізувати його на досліджуваному мові програмування;
) описати результати.
Перший розділ присвячений визначенню бінарного дерева, упорядкованого двійкового дерева, бінарного дерева пошуку, а також опису основних властивостей і особливостей структур таких дерев. Другий розділ присвячений опису формальної постановки задачі, методу розв'язання додавання даних в дерево і дослідженню і вибору алгоритму. Третій розділ містить відомості про логічну структуру і функціонуванні програми, опис використовуваних функцій. Четвертий розділ включає тестування програми, оцінку повноти вирішення поставленого завдання та достовірності отриманих результатів. p align="justify"> Теоретичний розділ
1.1 Визначення бінарного дерева
Бінарне (двійкове) дерево - це впорядкована дерево, кожна вершина якого має не більше двох піддерев, причому для кожного вузла виконується правило: у лівому поддереве містяться тільки ключі, що мають значення, менші, ніж значення даного вузла , а в правому поддереве містяться тільки ключі, що мають значення, більші, ніж значення даного вузла.
Бінарне дерево є рекурсивної структурою, оскільки кожне його піддерево саме є бінарним деревом, і, отже, кожен його вузол у свою чергу є коренем дерева. Вузол дерева, що не має нащадків, називається лис...