3.3. Реалізація бд пошуку на базі масиву розмірністю 17

Індекси	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Info	0	15	23	18	7	23	21	20	57	3	6	0	0	0	0	0	0
Father	0	0	1	2	1	2	3	6	5	4	9	0	11	12	13	14	15
Left_son	0	4	3	0	9	0	7	0	0	0	0	0	0	0	0	0	0
Right_son	0	2	5	6	0	8	0	0	0	10	0	12	13	14	15	16	0

3.4. Обхід бд пошуку

а) послідовність вершин дерева при проходженні його у прямому порядку

15 7 3 23 18 21 23

б) послідовність листків дерева при проходженні його у зворотньому порядку

6 20 57

в) послідовність вузлів, що мають тільки одного нащадка при проходженні дерева у симетричному порядку

3 7 18 21 23 23

4. Алгоритм розв’язання задачі

Для створення бінарного дерева пошуку спочатку необхідно створити структуру вузла дерева у класі, описати змінні класу, та вказівники. Реалізувати функції які потрібні для роботи із деревом:

addTree(); //додати елемент у дерево

delSearchNode(); //видалити шуканий вузол

clear(); //видаляє все дерево

printTree(); //роздрук дерева

findParent(); //пошук батька для двох вузлів

preorderWalk(); //прямий обхід дерева

postorderWalk(); //зворотній обхід дерева

symmetricalWalk(); //симетричний обхід дерева

Для додавання елементів у дерево необхідно описати функцію addTree(). Перший елемент, який буде записано у дерево стане коренем дерева, а решта елементів будуть додаватись у ті місця бінарного дерева пошуку за принципом: більші або рівні елементи вершині будуть записуватись у праве піддерево, менші елементи від вершини будуть записуватись у ліве піддерево.

Для видалення якогось конкретного елементу із дерева необхідно описати функцію delSearchNode(). Алгоритм видалення листка: при видаленні листка, батьку цього листка записується вказівник на 0, замість вказівника на цей листок. Алгоритм видалення вузла з одним нащадком: батьку вузла записується вказівник на нащадка цього вузла, а сам вузол видаляється. Алгоритм видалення вузла із двома нащадками: цей вузол треба замінити на крайній лівий вузол правого піддерева.

Для знаходження спільного предка двох заданих вузлів необхідно описати функцію findParent(). Шуканим предком двох вузлів буде той вузол на якому розійдуться шляхи до цих двох заданих вузлів.