Работа с двоичными деревьями: построение, поиск, удаление, включение и обход

     4.6 Вставка 

     Вставка узла в двоичное дерево является просто продолжением операции поиска. Отличие  заключается лишь в том, что, если искомого элемента в дереве нет, мы добавляем в дерево новый узел в то место, на котором он должен быть (см. Рисунок 4.4). 

     int bin_insert(struct bin_tree *tree, int item)

     {

           struct bin_node *node, **new;

           assert(tree != NULL);

           new = &tree->root;

           node = tree->root;

           for (;;) {

                 if (node == NULL) {

                       node = *new = malloc(sizeof *node);

                 if (node != NULL) {

                       node->data = item;

                       node->left = node->right = NULL;

     tree->count++;

     return 1;

                 }

                 else

                       return 0;

                 }

                 else if (item == node->data)

                       return 2;

                 else if (item > node->data){

                       new = &node->right;

                       node = node->right;

                 }

                 else {

                       new = &node->left;

                       node = node->left;

                 }

           }   

     }

     Рисунок 4.4 – Добавление 

     Здесь объявляется функция bin_insert(), которая в качестве аргументов принимает двоичное дерево и элемент, который необходимо вставить. Функция bin_insert() возвращает 1, если элемент успешно был вставлен в дерево, 2 – если элемент с таким же значением уже есть в дереве (двоичное дерево поиска не может содержать в разных узлах несколько одинаковых значений), и 0 – если элемента в дереве нет и вставка невозможна из-за ошибки при выделении памяти. Таким образом, вызывающая программа может проверить успешность выполнения операции вставки по возвращаемому функцией значению.

     Как и ранее, здесь node указывает на текущий узел. Новая переменная new – это двойной указатель, указывающий на указатель, по которому мы попали в узел node. Это очень важный момент, поэтому при рассмотрении кода всегда следует помнить о нём.

     В начале функции мы проверяем, не является ли tree нулевым указателем, затем инициализируем node значением корня дерева и присваиваем переменной new адрес указателя на корень дерева.

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

     Наибольшее  различие функций bin_insert() и bin_search() заключается в их поведении при попадании на нулевой указатель, когда элемента item в дереве нет. Нам необходимо добавить элемент в нужную точку дерева, заменяя нулевой указатель, с помощью которого мы попали в данную точку дерева, новым узлом, содержащим элемент item. К счастью, известно, где находится нулевой указатель, поскольку для его отслеживания используется переменная new. Мы просто выделяем память под новый узел и сохраняем его в *new, проверяя успешность выделения памяти.

     Кроме того, для обеспечения более лёгкого  доступа нужно сохранить новый узел в node. Мы инициализируем новый узел значением item и устанавливаем значения указателей поддеревьев нового узла равными NULL. И наконец, увеличиваем на 1 счётчик элементов дерева и возвращаем значение 1, говорящее о том, что новый узел был успешно вставлен. 

     4.7 Удаление 

     Процесс удаления элементов несколько сложнее, чем процесс вставки (см. Рисунок 4.5). 

     int bin_delete(struct bin_tree *tree, int item)

     {

           struct bin_node **q, *z;

           assert(tree != NULL);

     q = &tree->root;

     z = tree->root;

     for (;;) {

           if (z == NULL)

                 return 0;

           else if (item == z->data)

                 break;

           else if (item > z->data) {

                 q = &z->right;

                 z = z->right;

           }

           else {

                 q = &z->left;

                 z = z->left;

           }

           }

           if (z->right == NULL)

                 *q = z->left;

           else {

                 struct bin_node *y = z->right;

                 if (y->left == NULL) {

                       y->left = z->left;

                       *q = y;

                 }

                 else {

                       struct bin_node *x = y->left;

                       while (x->left !- NULL) {

                             y = x;

                             x = y->left;

                       }

                       y->left = x->right;

                       x->left = z->left;

                       x->right = z->right;

                       *q = x;

                       }

                 }

                 tree->count--;

                 free(z);

                 return 1; 

     }

     Рисунок 4.5 – Удаление 

     Мы  объявляем функцию bin_delete(), которая в качестве аргументов принимает двоичное дерево tree и значение item, которое необходимо удалить. Функция возвращает 0, если значения item в дереве нет, и 1 – если оно было успешно удалено. (Функция, в принципе, не может завершиться неудачно, поэтому в ней не предусмотрено определённого возвращаемого значения на случай неудачи).

     Цикл  в начале функции – это тот  же алгоритм поиска, но здесь node переименован на z, а new на q. Кроме того, если значение item найдено, вместо выполнения вставки элемента цикл просто завершается (с помощью оператора break).

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

     Случай 1. Узел z не имеет правого дочернего узла, следовательно, узел z можно заменить его левым дочерним узлом. Я просто заменяю указатель на z(*q) указателем на левый дочерний узел узла z. Если узел z не имеет и левого дочернего узла, значение *q заменяется на нулевой указатель, что тоже не представляет никаких затруднений.

     Случай 2. узел z имеет правый дочерний узел, но тот не имеет левого дочернего узла. Правый дочерний узел узла z получает левое поддерево узла z, а затем заменяет собой сам узел z. Я заменяю z на y, устанавливая значение *q. Кроме того, чтобы не потерять левое поддерево узла z, нужно скопировать указатель на него в y.

     Случай 3. В оставшемся случае узел z заменяется на дочерний узел x, а затем x удаляется, поскольку у него нет левого дочернего узла. Мы знаем, что у z есть правый дочерний узел и что у правого дочернего узла есть левый дочерний узел, который мы сохраняем в x. Далее цикл проходит по указателю на левый дочерний узел узла x до тех пор, пока не наткнётся на узел без левого дочернего узла. В этом случае x становиться наследником узла z в дереве tree, т.е. x содержит минимальное значение в дереве, которое больше значения узла z. Таким образом, узел y оказывается родительским узлом для узла x.

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

     Теперь  узел x является преемником узла z, а узел y является родительским узлом для узла x. Чтобы эффективно удалить узел z, необходимо его заменить на узел x и свести задачу удаления z к задаче удаления предшествующего узла x. Узел x не имеет левого дочернего узла (иначе он не был бы преемником узла z), поэтому его удаление не представляет сложностей.

     Сначала узел x удаляется из дерева путём замены указателя на левое поддерево узла y (который указывает на x) указателем на правое поддерево узла x. Далее поддеревья узла x заменяются поддеревьями узла z и указатель *q устанавливается на узел x, а не на z.

     После удаления количество узлов уменьшается  на единицу, поэтому значение счётчика tree->count уменьшается на 1. Переменная t больше не используется, поэтому мы её высвобождаем. И наконец, функция bin_delete() возвращает вызывающей программе значение, соответствующее успешному удалению узла.

     В заключение рассмотрим предельный случай, если удаляемый узел оказывается единственным узлом дерева. В этом случае искомым узлом будет z. Он будет обнаружен при первом же прохождении цикла, и цикл завершится. Поскольку узел z является листом (т.е. у него нет правого поддерева), мы можем рассматривать случай 1 и никаких проблем не возникает. 

     4.8 Упорядоченное рекурсивное прохождение 

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

     Но  каким образом распечатывать  поддеревья? Ведь поддеревья двоичного дерева сами являются двоичными деревьями, поэтому их содержимое необходимо распечатывать таким же образом, как и содержимое всего дерева: сначала содержимое левого поддерева, затем значение корня, а затем содержимое правого поддерева. Другими словами, поддеревья распечатываются  рекурсивно – так же, как и корень (см. Рисунок 4.6). 

     Static void walk (const struct bin_node *node)

     {

           if (node == NULL)

                 return;

           walk(node->left);

           printf(“%d”, node->data);

     walk(node->right);

     }