Программирование бинарных деревьев на языке СС++

      Запуск  процесса построения как обычно выполняется  из главной программы с помощью  вызова  AddNodes(&Root, N). В этом вызове фактический параметр N обязательно должен иметь конкретное значение, например – заданное пользователем количество вершин в строящемся ИСД. Однако, первый фактический параметр Root, являясь выходным,  получит свое значение лишь после отработки всех рекурсивных вызовов, при возврате в главную программу.

      Для понимания работы приведенной процедуры  целесообразно вручную расписать шаги ее работы для простейшего дерева из трех вершин. Пусть элементами дерева являются символы  A, B, C. В результате работы мы должны получить: 
Root = A,  A->Left = B,  A->Right = C, 
B->Left = NULL,  B->Right = NULL, 
C->Left = NULL,  C->Right = NULL.

      Двоичные  деревья представляют эффективный способ поиска. Двоичное дерево представляет собой структурированную коллекцию узлов. Коллекция может быть пустой и в этом случае мы имеем пустое двоичное дерево. Если коллекция непустая, то она подразделяется на три раздельных семейства узлов: корневой узел n (или просто корень), двоичное дерево, называемое левым поддеревом для n, и двоичное дерево, называемое правым поддеревом для n. На рис. 1а узел, обозначенный буквой А, является корневым, узел В называется левым потомком А и является корнем левого поддерева А, узел С называется правым потомком А и является корнем правого поддерева А.

      

      Рис. 1 Двоичное дерево с показанными внешними узлами (а) и без них (б)

      Двоичное  дерево на рис. 1а состоит из четырех  внутренних узлов (обозначенных на рис. кружками) и пяти внешних (конечных) узлов (обозначены квадратами). Размер двоичного дерева определяется числом содержащихся в нем внутренних узлов. Внешние узлы соответствуют пустым двоичным деревьям. Например, левый потомок узла В — непустой (содержит узел D), тогда как правый потомок узла В — пустое дерево. В некоторых случаях внешние узлы обозначаются каким-либо образом, в других — на них совсем не ссылаются и они считаются пустыми двоичными деревьями (на рис. 1 внешние узлы не показаны).

      При реализации двоичных деревьев, основанной на точечном представлении, узлы являются объектами класса TreeNode.

      template<class T> class TreeNode {

       protected:

        TreeNode  *_lchild;

        TreeNode  *_rchild;

        Т val;

       public:

        TreeNode(T);

        virtual ~TreeNode(void);

        friend class SearchTree<T>;  // возможные пополнения

        friend class BraidedSearchTree<T>; // структуры

      };

      Элементы  данных _lchild и _rchild обозначают связи текущего узла с левым и правым потомками соответственно, а элемент данных val содержит сам элемент.

      Конструктор класса формирует двоичное дерево единичного размера — единственный внутренний узел имеет два пустых потомка, каждое из которых представлено нулем NULL:

      template<class T> TreeNode<T>::TreeNode(T v) :

        val(v), _lchild(NULL), _rchild (NULL)

      {

      }

      Деструктор ~TreeNode рекурсивно удаляет оба потомка  текущего узла (если они существуют) перед уничтожением самого текущего узла:

      template<class T> TreeNode<T>::~TreeNode(void)

      {

        if (_lchild) delete _lchild;

        if (_rchild) delete _rchild;

      } 
 
 
 

      Двоичные  деревья поиска  

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

      

      Рис. 2 Три двоичных дерева поиска с одним и тем же набором элементов

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

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

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

      Конструкторы  и деструкторы

 

      Конструктор SearchTree инициализирует элементы данных cmp для функции сравнения и root для пустого дерева поиска:

      template<class T> SearchTree<T>::SearchTree (int (*с) (Т, Т) ) :

        cmp(с), root (NULL)

      {

      }

      Дерево  поиска пусто только, если в элементе данных root содержится нуль (NULL) вместо разрешенного указателя:

      template<class T> int SearchTree<T>::isEmpty (void)

      {

        return (root == NULL);

      }

      Деструктор  удаляет все дерево путем обращения  к деструктору корня:

      template<class T> SearchTree<T>::~SearchTree (void)

      {

        if (root) delete root;

      }

      Поиск

      Чтобы найти заданный элемент val, мы начинаем с корня и затем следуем  вдоль ломаной линии уникального  пути вниз до узла, содержащего val. В  каждом узле n вдоль этого пути используем функцию сравнения для данного  дерева на предмет сравнения val с элементом n->val, записанном в n. Если val меньше, чем n->val, то поиск продолжается, начиная с левого потомка узла n, если val больше, чем n->val, то поиск продолжается, начиная с правого потомка n, в противном случае возвращается значение n->val (и задача решена). Путь от корневого узла вниз до val называется путем поиска для val.

      Этот  алгоритм поиска реализуется в компонентной функции find, которая возвращает обнаруженный ею указатель на элемент или NULL, если такой элемент не существует в дереве поиска.

      template<class T> T SearchTree::find (T val)

      {

        TreeNode *n = root;

        while (n) {

          int result = (*cmp) (val, n->val);

          if (result < 0)

            n = n->_lchild;

            else if (result > 0)

            n = n->_rchild;

            else

            return n->val;

        }

        return  NULL;

      }

      Этот  алгоритм поиска можно сравнить с  турниром, в котором участвуют  некоторые кандидаты. В начале, когда  мы начинаем с корня, в состав кандидатов входят все элементы в дереве поиска. В общем случае для каждого  узла n в состав кандидатов входят все потомки n. На каждом этапе производится сравнение val с n->val. Если val меньше, чем n->val, то состав кандидатов сужается до элементов, находящихся в левом поддереве, а элементы в правом поддереве n, как и сам элемент n->val, исключаются из соревнования. Аналогичным образом, если val больше, чем n->val, то состав кандидатов сужается до правого поддерева n. Процесс продолжается до тех пор, пока не будет обнаружен элемент val или не останется ни одного кандидата, что означает, что элемент val не существует в дереве поиска.

      Для нахождения наименьшего элемента мы начинаем с корня и прослеживаем связи с левым потомком до тех  пор, пока не достигнем узла n, левый  потомок которого пуст — это означает, что в узле n содержится наименьший элемент. Этот процесс также можно уподобить турниру. Для каждого узла n состав кандидатов определяется потомками узла n. На каждом шаге из состава кандидатов удаляются те элементы, которые больше или равны n->val и левый потомок n будет теперь выступать в качестве нового n. Процесс продолжается до тех пор, пока не будет достигнут некоторый узел n с пустым левым потомком и, полагая, что не осталось кандидатов меньше, чем n->val, и будет возвращено значение n->val.

      Компонентная  функция findMin возвращает наименьший элемент в данном дереве поиска, в ней происходит обращение к компонентной функции _findMin, которая реализует описанный ранее алгоритм поиска, начиная с узла n :

      template<class T> T SearchTree<T>::findMin (void)

      {

        TreeNode<T> *n = _findMin (root);

        return (n ? n->val : NULL);

      } 

      template<class T>

      TreeNode<T> *SearchTree<T>::_findMin (TreeNode<T> *n)

      {

        if (n  == NULL)

          return NULL;

        while   (n->_lchild)

          n = n->_lchild;

        return n;

      }

      Наибольший  элемент в дереве поиска может  быть найден аналогично, только отслеживаются связи с правым потомком вместо левого.

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

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

      

      Рис. 4 Три ситуации, возникающие при удалении элемента из двоичного дерева поиска

      Чтобы удалить элемент из дерева поиска, вначале мы отслеживаем путь поиска элемента, начиная с корня и  вниз до узла n, содержащего элемент. В этот момент могут возникнуть три ситуации, показанные на рис. 4:

1. Узел n имеет пустой левый потомок. В этом случае ссылка на n (записанная в предке n, если он есть) заменяется на ссылку на правого потомка n.
2. У узла n есть непустой левый потомок, но правый потомок пустой. В этом случае ссылка вниз на n заменяется ссылкой на левый потомок узла n.
3. Узел n имеет два непустых потомка. Найдем последователя для n (назовем его m), скопируем данные, хранящиеся в m, в узел n и затем рекурсивно удалим узел m из дерева поиска.