Рекурсивна функція формує

бінарне дерево пошуку, вона приймає два параметри:

-  вказівник root на кореневий

вузол – як посилання;

-  значення value

інформаційного поля шуканого вузла (або новоствореного вузла).

Функція повертає

вказівник на знайдений чи новостворений вузол – як результат та булеве значення

found – як вихідний параметр, що вказує, чи існував вузол

із вказаним значенням (true) чи ні (false).

При першому виклику –

якщо параметр root має значення NULL, створюється

новий вузол, його поля зв’язку заповнюються значеннями NULL, а ключове поле – значенням value; параметр found отримує значення false, вказівник root отримує значення вказівника на новостворений вузол та функція повертає

вказівник на цей вузол.

Функція здійснює

бінарний пошук за таким правилом: якщо вузол із заданим значенням ключа

знайдено, то параметр found отримує значення true та функція

повертає вказівник на знайдений вузол. Інакше, якщо шукане значення – менше

ключового поля поточного вузла, пошук продовжується в його лівому під-дереві, в

іншому випадку – в правому під-дереві.

Якщо переглянута вся

відповідна гілка дерева, і шуканого значення не знайдено, відбувається вставка

нового вузла за тим же правилом, що і для першого вузла.

Для дерева із

7 вузлів користувач ввід наступні значення: 

1, 2, 3, 4, 5,

6, 7

Вказати, які

значення будуть виведені при префіксному обході такого дерева: