Функция просмотра элементов дерева

void View_Tree(Tree *p, int level) {

String str;

if (p) {

View_Tree (p -> right, level+1); // Правое поддерево

for (int i=0; i< level; i++) str = str + " ";

Form1-> Memo1-> Lines-> Add(str + IntToStr(p-> info));

View_Tree(p -> left, level+1); // Левое поддерево

}

}

Обращение к функции View будет иметь вид View(root, 0);

Вторым параметром функции является переменная, определяющая, на каком уровне (level) находится узел (у корня уровень «0»). Строка str используется для получения пробелов, необходимых для вывода значения на соответствующем уровне.

Удаление узла с заданным ключом из дерева поиска, сохраняя его свойства, выполняется в зависимости от того, сколько сыновей (потомков) имеет удаляемый узел.

1. Удаляемый узел является листом – просто удаляем ссылку на него. Приведем пример схемы удаления листа с ключом key:

2. Удаляемый узел имеет только одного потомка, т.е. из удаляемого узла выходит ровно одна ветвь. Пример схемы удаления узла key, имеющего одного сына:

3. Удаление узла, имеющего двух потомков, значительно сложнее рассмотренных выше. Если key – удаляемый узел, то его следует заменить узлом w, который содержит либо наибольший ключ (самый правый, у которого указатель Right равен NULL) в левом поддереве, либо наименьший ключ (самый левый, у которого указатель Left равен NULL) в правом поддереве.

Используя первое условие, находим узел w, который является самым правым узлом поддерева key, у него имеется только левый потомок:

Функция удаления узла по заданному ключу key может иметь вид

Tree* Del_Info(Tree *root, int key) {

Tree *Del, *Prev_Del, *R, *Prev_R;

// Del, Prev _ Del – удаляемый узел и его предыдущий (предок);

// R, Prev _ R – элемент, на который заменяется удаленный, и его предок;

Del = root;

Prev_Del = NULL;

//-------- Поиск удаляемого элемента и его предка по ключу key ---------

while (Del! = NULL & & Del -> info! = key) {

Prev_Del = Del;

if (Del-> info > key) Del = Del-> left;

else Del = Del-> right;

}

if (Del == NULL) { // Элемент не найден

ShowMessage (" NOT Key! ");

return root;

}

//-------------------- Поиск элемента R для замены --------------------------------

if (Del -> right == NULL) R = Del-> left;

else

if (Del -> left == NULL) R = Del-> right;

else {

//---------------- Ищем самый правый узел в левом поддереве -----------------

Prev_R = Del;

R = Del-> left;

while (R-> right! = NULL) {

Prev_R = R;

R = R-> right;

}

//----------- Нашли элемент для замены R и его предка Prev _ R -------------

if(Prev_R == Del) R-> right = Del-> right;

else {

R-> right = Del-> right;

Prev_R-> right = R-> left;

R-> left = Prev_R;

}

}

if (Del== root) root = R; // Удаляя корень, заменяем его на R

else

//------- Поддерево R присоединяем к предку удаляемого узла -----------

if (Del-> info < Prev_Del-> info)

Prev_Del-> left = R; // На левую ветвь

else Prev_Del-> right = R; // На правую ветвь

delete Del;

return root;

}

Поиск узла с минимальным (максимальным) ключом:

Tree* Min_Key(Tree *p) { // Tree* Max_Key(Tree *p)

while (p-> left! = NULL) p = p-> left; // p=p-> right;

return p;

}

Тогда для получения минимального ключа p_min -> info:

Tree *p_min = Min_Key(root);

 

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

void Make_Blns(Tree **p, int n, int k, int *a) {

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

return;

}

else {

int m=(n+k)/2;

*p = new Tree;

(*p)-> info = a[m];

Make_Blns(& (*p)-> left, n, m, a);

Make_Blns(& (*p)-> right, m+1, k, a);

}

}