Алгоритм вставки вузла у бінарне дерево пошуку

Теорія графів.

Лабораторна робота №6.

Тема. Робота з бінарними деревами пошуку.

Мета. Використовуючи довільну мову програмування, побудувати бінарне дерево пошуку, вивести значення його вузлів у префіксному, інфіксному та постфіксному порядку, реалізувати можливість витирання довільного вузла дерева.

Короткі теоретичні відомості.

Принципи побудови бінарного дерева пошуку.

Одним із способів застосування дерев є бінарні дерева пошуку – це однокореневе дерево 2-го порядку, вузли якого розміщуються згідно наступного правила: у кожному лівому піддереві вузла р містяться всі вузли, значення яких менші за значення у вузлі р, а у правому піддереві – всі вузли, значення яких більші за значення у вузлі р.

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

Алгоритм вставки вузла у бінарне дерево пошуку.

Правило побудови бінарного дерева пошуку однозначно формує алгоритм вставки вузла у дерево. Згідно цього правила, а отже і згідно алгоритму, новий вузол може бути вставлений тільки як листок.

Функція, яка виконує вставку вузла повинна приймати два аргументи: 1 – вказівник на вершину дерева TREENODEPTR treePtr (див. означення типу нижче) та 2 – значення нового вузла. При чому кожен вузол, в т.ч. і новий – це структура (чи клас), що обов’язково повинна містити три поля (мал. 1):

1 – data поле значення вузла (тип поля відповідає типу даних, з яких будуватиметься дерево);

2 – *lPtr поле з вказівником на таку ж структуру (вузол) на ліве піддерево;

3 – *rPtr поле з вказівником на таку ж структуру (вузол) на праве піддерево.

В загальному випадку можна створити шаблон класу-контейнера, який би міг будувати бінарне дерево пошуку з значеннями у вузлах будь-якого типу, для котрого визначена операція порівняння (менше, більше).

Наприклад, фрагмент програми, що описує таку структуру на мові С++ (той же вигляд і на С) може бути такий:

//означення типу – структури вузла дерева

struct treeNode {

int data; //дані у вузлі

struct treeNode* lPtr; //вказівник на ліве піддерево

struct treeNode* rPtr; //вказівник на праве піддерево

};

typedef struct treeNode TREENODE; //псевдонім для типу вузла дерева

typedef TREENODE* TREENODEPTR; /*псевдонім для типу вказівника

на вузол дерева*/

Порядок алгоритму вставки вузла:

1) якщо treePtr == NULL то створити вузол-корінь дерева, значення вузла присвоїти полю data, а вказівникам на ліве та праве піддерева присвоїти значення NULL.

2) якщо treePtr!= NULL і значення вузла для вставки менше за treePtr -> data, то визвати функцію вставки вузла для treePtr -> lPtr. В противному випадку визвати функцію вставки для treePtr ->rPtr.

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