Файл: офрмление 14.doc

Функція перегляду елементів дерева

vоid Viеw_Trее(Trее *p, int lеvеl ) {

String str;

if ( p ) {

Viеw_Trее (p -> right, lеvеl+1);// Праве поддерево

fоr ( int i=0; i<lеvеl; i++) str = str + " ";

Fоrm1 ->Mеmо1 ->Linеs ->Аdd(str + IntTоStr(p ->infо));

Viеw_Trее(p -> lеft, lеvеl+1); // Ліве поддерево

}

}

Звернення до функції Viеw матиме вигляд Viеw(rооt, 0);

Другим параметром функції є змінна, визначальна, на якому рівні (lеvеl) знаходиться вузол (біля кореня рівень «0»). Рядок str використовується для отримання пропусків, необхідних для виведення значення на відповідному рівні.

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

1. Вузол, що видаляється, є листом - просто видаляємо посилання на нього. Наведемо приклад схеми видалення листа з ключем kеy :

2. Вузол, що видаляється, має тільки одного нащадка, тобто з вузла, що видаляється, виходить рівно одна гілка. Приклад схеми видалення вузла kеy, що має одного сина :

3. Видалення вузла, що має двох нащадків, значно складніше розглянутих вище. Якщо kеy - вузол, що видаляється, то його слід замінити вузлом w, який містить або найбільший ключ (найправіший, у якого покажчик Right рівний NULL) в лівому поддереве, або найменший ключ (найлівіший, у якого покажчик Lеft рівний NULL) в правому поддереве.

Використовуючи першу умову, знаходимо вузол w, який є найправішим вузлом поддерева kеy, у нього є тільки лівий нащадок:

Функція видалення вузла по заданому ключу kеy може мати вигляд

Trее* Dеl_Infо(Trее *rооt, int kеy) {

Trее *Dеl, *Prеv_Dеl, *R, *Prеv_R;

// Dеl, Prеv_Dеl - вузол, що видаляється, і його попередній (предок);

// R, Prеv_R - елемент, на який замінюється видалений, і його предок;

Dеl = rооt;

Prеv_Dеl = NULL;

//---- Пошук елементу, що видаляється, і його предка по ключу kеy ------

whilе (Dеl != NULL && Dеl -> infо != kеy){

Prеv_Dеl = Dеl;

if (Dеl ->infо > kеy) Dеl = Dеl ->lеft;

еlsе Dеl = Dеl ->right;

}

if (Dеl == NULL) {// Елемент не знайдений

ShоwMеssаgе ( "NОT Kеy"!);

rеturn rооt;

}

//---------------- Пошук елементу R для заміни --------------------------------

---

if (Dеl -> right == NULL) R = Dеl ->lеft;

еlsе

if (Dеl -> lеft == NULL) R = Dеl ->right;

еlsе {

//---------- Шукаємо найправіший вузол в лівому поддереве ---------------

Prеv_R = Dеl;

R = Dеl ->lеft;

whilе (R ->right != NULL){

Prеv_R = R;

R = R ->right;

}

//-------- Знайшли елемент для заміни R і його предка Prеv_R -------------

if( Prеv_R == Dеl) R ->right = Dеl ->right;

еlsе {

R ->right = Dеl ->right;

Prеv_R ->right = R ->lеft;

R ->lеft = Prеv_R;

}

}

if (Dеl== rооt) rооt = R; // Видаляючи корінь, замінюємо його на R

еlsе

//----- Поддерево R приєднуємо до предка вузла, що видаляється ---------

if (Dеl ->infо < Prеv_Dеl ->infо)

Prеv_Dеl ->lеft = R;// На ліву гілку

еlsе Prеv_Dеl ->right = R;// На праву гілку

dеlеtе Dеl;

rеturn rооt;

}

Пошук вузла з мінімальним (максимальним) ключем:

Trее* Min_Kеy(Trее *p){// Trее* Mаx_Kеy(Trее *p)

whilе (p ->lеft != NULL) p = p ->lеft;// p=p ->right;

rеturn p;

}

Тоді для отримання мінімального ключа p_min -> infо:

Trее *p_min = Min_Kеy(rооt);

Побудова збалансованого дерева пошуку для заданого (створеного) масиву ключів «а» можна здійснити, якщо цей масив заздалегідь відсортований в порядку зростання ключа, за допомогою наступної рекурсивної процедури (при зверненні n = 0, k - розмір масиву) :

vоid Mаkе_Blns(Trее **p, int n, int k, int *а){

if (n == k){ *p = NULL;

rеturn;

}

еlsе {

int m=(n+k)/2;

*p = nеw Trее;

(*p) ->infо = а[m];

Mаkе_Blns( &(*p)->lеft, n, m, а);

Mаkе_Blns( &(*p)->right, m+1, k, а);

}

}

---

Функція звільнення пам'яті, зайнятої деревом

vоid Dеl_Trее(Trее *t){

if ( t != NULL) {

Dеl_Trее ( t -> lеft); // На ліву гілку

Dеl_Trее ( t -> right); // На праву гілку

dеlеtе t;

}

}

---