АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Удаление узла

Читайте также:
  1. Ввод и удаление информации из ячеек
  2. Вопрос 72. Удаление главы МО в отставку
  3. Вставка и удаление строк и столбцов
  4. Дегазация — комплекс мероприятий, направленных на уничтожение (нейтрализацию) боевых отравляющих веществ или удаление их с зараженной поверхности.
  5. Добавление и удаление элементов диаграммы
  6. Менеджер расширений: установка и удаление расширений
  7. Оптимальное удаление образующихся взвесей холодного сусла
  8. Создание, открытие, закрытие и удаление файлов.
  9. Статья 295. Удаление суда в совещательную комнату для постановления приговора
  10. Удаление зарегистрированных барменов/ официантов
  11. УДАЛЕНИЕ ЗУБОВ У ДЕТЕЙ
  12. Удаление из солода пыли и камней

При удалении узла из дерева возможны три ситуации в зависимости от того, сколько сыновей (потомков) имеет удаляемый узел.

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);

¼

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | 82 | 83 |


При использовании материала, поставите ссылку на Студалл.Орг (0.014 сек.)