ев. Будемо вважати, що кожна вершина має якесь ключове поле, що дозволяє впорядкувати безліч вершин. Двійкове дерево називається деревом пошуку або пошуковим деревом, якщо для кожної вершини дерева всі ключі в її лівому поддереве менше ключа цієї вершини, а всі ключі в її правому поддереве більше ключа вершини. p align="justify"> Дерева пошуку є однією з найбільш ефективних структур побудови впорядкованих даних. Як відомо, у впорядкованому масиві дуже ефективно реалізується пошук (дихотомія), але дуже важко виконати додавання і видалення елементів. Навпаки, в упорядкованому списку легко реалізується додавання і видалення елементів, але не ефективна реалізація пошуку через необхідність послідовного перегляду всіх елементів, починаючи з першого. Дерева пошуку дозволяють об'єднати переваги масивом і лінійних списків: легко реалізується додавання і видалення елементів, а також ефективно виконується пошук. p align="justify"> Дерево пошуку слід використовувати для представлення впорядкованих даних, коли число їх досить велике і часто доводиться виконувати операції додавання, видалення та пошуку, [4].
Проектний розділ
бінарний дерево двійковий програмний
Словесна постановка завдання: програмна реалізація додавання даних до впорядкованого двійкове дерево з використанням динамічних структур даних.
Формальна постановка задачі:
Вхідні дані: елементи, які будуть додаватися в дерево (цілі числа).
Вихідні дані: дерево з доданих елементів (цілі числа).
Метод рішення: додавання елемента в двійкове дерево відбуватиметься за наступним алгоритмом: перш за все, треба знайти відповідне місце для нового елемента, тому додавання нерозривно пов'язано з процедурою пошуку. Будемо вважати, що в дерево можуть додаватися елементи з однаковими ключами, і для цього з кожною вершиною зв'яжемо лічильник числа появи цього ключа. p align="justify"> У процесі пошуку може виникнути одна з двох ситуацій:
1) знайдена вершина з заданим значенням ключа, і в цьому випадку просто збільшується лічильник;
2) пошук треба продовжувати по порожній посиланням, що говорить про відсутність в дереві шуканої вершини, більше того, тим самим визначається місце в дереві для розміщення нової вершини.
Само додавання включає наступні кроки:
1) виділення пам'яті для нової вершини;
2) формування інформаційної складової;
) формування двох порожніх посилальних полів на майбутніх нащадків;
) формування в батьківській вершині лівого і правого посилального поля - адр...
