1)Якщо поточний вузел є пустим деревом, тоді вставити
елемент в нього.
2) В іншому випадку, зрівняти елемент, що вставляється з
елементом, який зберігається в поточному вузлі. Якщо значення
нового елементу менше, тоді вставити новий елемент в ліве
піддерево поточного вузла, а в іншому випадку - вставити в
праве піддерево поточного вузла.
Прологівська реалізація побудови бінарного дерева
пошуку буде вимагати наявності трьох фраз. Перша
insert(NewItem,empty,
tree(NewItem,empty,empty):-!.
позначає, "результатом вставки елементу NewItem в пусте
дерево буде дерево tree(NewItem, empty,empty) ".
Друга й третя фрази реалізовують відповідно
лівосторонню або правосторонню вставку в не пусте дерево:
insert(NewItem,
tree(Element,Left,Right),
tree(Element,NewLeft,Right):- NewItem <
Element, !,
insert (NewItem,Left,NewLeft).
insert(NewItem,
tree(Element,Left,Right),
tree(Element, Left, NewRight)):-
insert(NewItem,Right,NewRight).
7.5 Сортування по дереву
Якщо бінарне дерево пошуку вже побудоване, дуже
просто розмістити всі його елементи в лексико-графічному
порядку. Рекурсивний алгоритм буде включати зворотній обхід
дерева:
1. Якщо дерево пусте, тоді нічого не потрібно робити.
2. В іншому випадку , переглянути всі елементи лівого
піддерева, потім поточний елемент, потім всі елементи правого
піддерева.
86