|
|||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Удаление узлаПри удалении узла из дерева возможны три ситуации в зависимости от того, сколько сыновей (потомков) имеет удаляемый узел. 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); ¼
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.006 сек.) |