Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 7
з дисципліни «Програмування складних алгоритмів»
Тема «. Поняття бінарного дерева. Обхід бінарного дерева. Створення, відображення дерева. Вставлення, видалення елементів»
Варіант № 24
Дата «20» червня 2022
1.1 Завдання до лабораторної роботи:
1. сформулювати математичну постановку задачі;
2. обрати метод розв’язання задачі, якщо це необхідно;
3. розробити графічну схему алгоритму;
4. записати розроблений алгоритм мовою програмування;
5. представити звіт до роботи
Варіант завдання:
/
1.2 Теоретичні відомості
Дерево – це структура даних, що являє собою сукупність елементів і відносин, що утворюють ієрархічну структуру цих елементів.
Кожен елемент дерева називається вершиною (вузлом) дерева. Вершини дерева з’єднані спрямованими дугами, які називають гілками дерева. Початковий вузол дерева називають коренем дерева, йому відповідає нульовий рівень. Листями дерева називають вершини, в які входить одна гілка і не виходить жодної гілки.
Кожне дерево має такі властивості:
1) існує вузол, в який не входить ні одна дуга (корінь);
2) у кожну вершину, крім кореня, входить одна дуга.
Дерева особливо часто використовують на практиці при зображенні різних ієрархій
Бінарні дерева є деревами зі ступенем не більше двох.
Бінарне (двійкове) дерево − це динамічна структура даних, що являє собою дерево, в якому кожна вершина має не більше двох нащадків. Таким чином, бінарне дерево складається з елементів, кожен з яких містить інформаційне поле і не більше двох посилань на різні бінарні піддерева. На кожен елемент дерева є рівно одне посилання.
Кожна вершина бінарного дерева є структурою, що складається з чотирьох видів полів.
Вмістом цих полів будуть відповідно:
• інформаційне поле (ключ вершини);
• службове поле (їх може бути декілька або жодного);
• покажчик на ліве піддерево;
• покажчик на праве піддерево
1.3. Результати роботи
Було створено програму для запису чисел у вигляді бінарного дерева. На екран виводяться: елементи дерева, сума елементів, їх середнє арифметичне, і листи дерева, що мають непарні значення.
1.4. Лістинг програми
#include <malloc.h> #include <stdio.h> #include <stdlib.h> //Бінарне дерево typedef struct tree { int key; struct tree *left; struct tree *right; } tree_t; tree_t *tree_insert(tree_t **tr, int key); void tree_clear(tree_t *tr); //Прямий обхід дерева void tree_out_width(const tree_t *tr, int *u, double *counter) { if (tr == NULL) return; printf("%d ", tr->key); // Спосіб визначення суми з викор. вказівника *u = (*u) + tr->key; (*counter)++; tree_out_width(tr->left, u, counter); //За допомогою рекурсії відвідуємо ліве піддерево tree_out_width(tr->right, u, counter); //За допомогою рекурсії відвідуємо праве піддерево } void tree_out_2(const tree_t *tr) { if (tr == NULL) return; if (tr->left == NULL & tr->right == NULL & tr->key % 2 != 0) { printf("%d ", tr->key); } tree_out_2(tr->left); //За допомогою рекурсії відвідуємо ліве піддерево tree_out_2(tr->right); //За допомогою рекурсії відвідуємо праве піддерево } int main(void) { int i; tree_t *tr = NULL; srand(time(NULL)); for (i = 0; i < 10; ++i) tree_insert(&tr, rand() % 10); int sum = 0; int *poi = ∑ double coun = 0; double *pcoun = &coun; printf("Бінарне дерево: "); tree_out_width(tr, poi, pcoun); printf("\nСума елементів дерева: %d ", *poi); printf("\nСереднє арифметичне елементів дерева: %.2f", (*poi) / (*pcoun)); // tree_clear(tr); printf("\nЛисти дерева, що мають непарні значення: "); tree_out_2(tr); printf("\n"); return 0; } //вставка tree_t *tree_insert(tree_t **tr, int key) { tree_t *p = *tr; while (p != NULL) { if (key == p->key) //дублікати відкидаємо return p; else if (key < p->key) { tr = &p->left; p = p->left; } else { tr = &p->right; p = p->right; } } p = (tree_t *) malloc(sizeof(tree_t)); if (p != NULL) { p->key = key; p->left = p->right = NULL; *tr = p; } return p; } //удаление всех void tree_clear(tree_t *tr) { if (tr != NULL) { if (tr->left != NULL) tree_clear(tr->left); if (tr->right != NULL) tree_clear(tr->right); free(tr); } }
Результат виконання:
/
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора