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

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

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

Такой узел называется листом. В этом случае понадобится только переустановить указатель в родительском узле в NULL и с помощью функции free() освободить память, занимаемую удаленным узлом.

Следующая по сложности задача — удаление узла с одним дочерним узлом. Удаление узла ведет к отделению дочернего поддерева от остального дерева. Для исправления такой си туации адрес дочернего поддерева должен быть сохранен в родительском узле в позиции, которая ранее была занята адресом удаленного узла (рис. 17.14).

Рис. 1 7.14. Удаление узла с одним дочерним узлом

Последний случай связан с удалением узла, имеющего два поддерева. Одно поддерево, скажем, левое, может быть присоединено к тому узлу, к которому вначале был присоединен удаленный узел. Но куда поместить оставшееся поддерево? Вспомним базовый принцип формирования древовидной структуры. Каждый элемент в левом поддереве предшествует элементу в родительском узле, а каждый элемент в правом поддереве следует за элементом в родительском узле. Эго означает, что каждый элемент в правом поддереве расположен в структуре дальше любого элемента из левого поддерева. Кроме того, поскольку правое поддерево ранее было частью поддерева, начинающегося с удаленного узда, каждый элемент в правом поддереве предшествует родительскому узлу удаленного узла. Вообразите себе спуск по дереву в поисках позиции для помещения начала правого поддерева. Он предшествует родительскому узлу, поэтому далее необходимо следовать вниз по левому поддереву. Однако начало поддерева должно быть расположено после всех элементов в левом поддереве, поэтому необходимо последовать правой ветвью левого поддерева и выяснить, имеется ли в ней место для нового узла. Если нет, потребуется продолжать спуск по правой ветви

774 глава 17 левого поддерева до тех пор, пока свободное место не будет найдено. Этот подход продемонстрирован на рис. 17.15.

Рис. 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(). В противном случае код выясняет, в левом или правом дочернем узле родительского узла расположен удаляемый узел, и затем передает адрес соответствующего указателя.