еси нової вершини.
Тут тільки остання операція викликає деяку складність, оскільки для доступу до посилального полю батьківського вершини треба знати її адресу.
Ситуація аналогічна додаванню елемента в лінійний список перед заданим, коли для відстеження елемента-попередника при проході за списком використовувався додатковий покажчик. Цей же прийом можна використовувати і для дерев, але є більш елегантне рішення - рекурсивний пошук з додаванням нової вершини при необхідності. Кожен рекурсивний виклик відповідає за обробку чергової вершини дерева, починаючи з кореня, а вся послідовність вкладених викликів дозволяє автоматично запам'ятовувати шлях від кореня до будь поточної вершини. Процедура пошуку повинна мати формальний параметр-змінну посилального типу, який відстежує адресу поточної вершини дерева і як тільки ця адреса стає порожнім, створюється нова вершина і її адресу повертається в викликала процедуру, тим самим автоматично формуючи необхідну посилання у батьківської вершини. p align="justify"> Алгоритм (блок-схеми):
Загальна блок-схема дій, а також блок-схеми пошуку місця для елемента і створення вершини (додавання даних) у впорядкований двійкове дерево представлені на малюнках 4, 5 і 6 відповідно.
В
Рисунок 4 - Загальна блок-схема дій
В
В
Рисунок 5 - Блок-схема пошуку місця для елемента
В
Малюнок 6 - Блок-схема додавання елемента
Програмний розділ
Програма реалізована в середовищі Visual Studio 2008 у консольному додатку Win 32. Проект складається з одного файлу з розширенням. Cpp. p align="justify"> Спочатку створюється структура binary_tree, в якій оголошуються наступні змінні: data - дані, що вводяться, count - лічильник (обидва цілі числа), покажчики на праве і ліве поддеревья binary_tree * left, * right:
struct binar_tree
{data, count; _tree * left, * right;
};
Також глобально обнуляється лічильник count = 0 і кореня дерева root присвоюється значення NULL. Для вирішення завдання додавання даних до впорядкованого двійкове дерево потрібно створити функцію додавання елементів в це саме дерево Add (). Також знадобиться функція перегляду дерева Show (), щоб переконатися, що елементи додаються правильно, і функція очищення дерева Clear () на випадок, якщо виникне необхідність очистити дерево. Кожна функція заснована на рекурсії, тобто викликає саму себе там, де це необхідно. Прототипи цих функцій і опис кожної з них наведено нижче:
1) функція void Add (struct binar_tree ** current, int data): щоб почати додавати елементи в дерево, потрібно перевірити поточний елемент. Якщо він не порожній (current! = NULL), то перевіряється така умова: якщо елемент менше ...
