Удаление узла
При удалении узла из дерева возможны три ситуации в зависимости от того, сколько сыновей (потомков) имеет удаляемый узел.
1. Удаляемый узел является листом – просто удаляем ссылку на него. Приведем пример схемы удаления листа с ключом key:
2. Удаляемый узел имеет только одного потомка, т.е. из удаляемого узла выходит ровно одна ветвь. Пример схемы удаления узла key, имеющего одного сына:
3. Удаление узла, имеющего двух сыновей, значительно сложнее рассмотренных выше. Если key – удаляемый узел, то его следует заменить узлом w, который содержит либо наибольший ключ (самый правый, у которого указатель Right равен NULL) в левом поддереве, либо наименьший ключ (самый левый, у которого указатель Left равен NULL) в правом поддереве.
Используя первое условие, находим узел w, который является самым правым узлом поддерева key, у него имеется только левый сын:
В построенном ранее дереве удалим узел key (6). Используем второе условие, т.е. ищем самый левый узел в правом поддереве – это узел w (указатель Left равен NULL):
Функция удаления узла по заданному ключу key может иметь вид
Tree* Del(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) { // Элемент не найден
puts("\n NO 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; // на правую ветвь
printf("\n Delete element %d \n", Del->info);
free(Del);
return Root;
}
Участок программы с обращением к данной функции будет иметь вид
¼
printf("\n Input Del Info : ");
scanf(“%d”, &key);
Root = Del(Root, key);
¼
Дата добавления: 2014-12-30; просмотров: 1162;