Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Рис. 17.15. Удаление узла с двумя дочерними узлами

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

Теперь можно приступать к планированию необходимых функций, разделив работу на две задачи. Первая задача предусматривает связывание конкретного элемента с узлом, подлежащим удалению, а вторая заключается в действительном удалении узла. Следует отметить, что во всех случаях требуется модификация указателя в родительском узле, а это приводит к двум важным последствиям.

• Программа должна идентифицировать родительский узел удаляемого узла.

• Для изменения указателя код должен передавать функции удаления адрес этого указателя.

К первому моменту мы вернемся несколько позже, а пока проанализируем второй момент. Указатель, который нужно изменять, имеет тип Trnode *, т.е. является указателем на Trnode. Поскольку аргумент функции — адрес этого указателя, типом аргумента будет Trnode **, или указатель на указатель на Trnode. Предполагая, что подходящий адрес доступен, функцию удаления можно реализовать следующим образом:

Расширенное представление данных

В этой функции явно обрабатываются три случая: узел без левого дочернего узла, узел без правого дочернего узла и узел с двумя дочерними узлами. Узел без дочерних узлов можно считать особым случаем узла без левого дочернего узла. Если узел не имеет левого дочернего узла, код присваивает адрес правого дочернего узла указателю на родительский узел. Но если узел не имеет также и правого узла, то значением этого указателя будет NULL, которое является полностью подходящим значением для случая узла без дочерних узлов.

Обратите внимание, что для отслеживания адреса удаляемого узла в коде применяется временный указатель. В результате переустановки родительского указателя (*ptr) программа утратила бы информацию о местоположении удаленного узла, а эта информация нужна для функции free(). Таким образом, исходное значение *ptr сохраняется в переменной temp, а затем используется для освобождения памяти, занимаемой удаленным узлом.

В коде для случая узла с двумя дочерними узлами вначале применяется указатель temp в цикле for для поиска свободного места в правой части левого поддерева. После его нахождения к нему присоединяется правое поддерево. Затем снова используется указатель temp для отслеживания местоположения удаленного узла. И, наконец, левое поддерево присоединяется к родительскому узлу, после чего узел, на который указывает temp, освобождается.

Обратите внимание, что поскольку ptr имеет тип Trnode * *, то *ptr относится к типу Trnode *, делая его совпадающим по типу с указателем temp.

Удаление элемента

Оставшаяся нерешенной часть задачи касается связи узла с определенным элементом. Чтобы сделать это, можно воспользоваться функцией Seekltem(). Вспомните, что она возвращает структуру, содержащую указатель на родительский узел и указатель на узел, в котором находится элемент. Следовательно, указатель родительского узла можно применять для получения подходящего адреса и его передачи в функцию DeleteNode(). Такой план реализован в показанной ниже функции Deleteltem().

776 глава 17

Возвращаемое значение функции Seekltem() присваивается переменной look типа структуры. Если значение look, child равно NULL, поиск элемента безуспешен, и функция DeleteItem() завершает работу, возвращая false. Если элемент Item найден, функция обрабатывает три случая. Прежде всего, значение NULL переменной look.parent говорит о том, что элемент был найден в корневом узле. В таком случае родительский узел, который нужно было бы обновить, отсутствует. Вместо этого должен быть обновлен указатель root в структуре Tree. Следовательно, функция передает адрес этого указателя в функцию DeleteNode(). В противном случае код выясняет, в левом или правом дочернем узле родительского узла расположен удаляемый узел, и затем передает адрес соответствующего указателя.

Обратите внимание, что функция открытого интерфейса (Deleteltem()) оперирует понятиями, близкими конечному пользователю (элементами и деревьями), а скрытая функция DeleteNode() выполняет будничные действия с указателями.