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

Идея поиска проста. Алгоритм поиска в ДДП по своей природе рекурсивен. При его описании проще всего использовать понятие поддерева. Поиск начинается с корня дерева, который принимается за корень текущего поддерева, и его ключ сравнивается с искомым. Если они равны, то, очевидно, поиск закончен. Если ключ, который мы ищем, оказался больше текущего, то, очевидно, что нужная вершина находится в правом поддереве, иначе – в левом. Далее эта операция повторяется для правого или левого поддерева. В условном коде это можно описать так:

Рекурсивно:

TreeSearch(node, key)

Begin

 // Если вершина равна NIL, то нечего в ней искать. Так же и возвращаем.

 // Это нужно для поиска по не существующим потомкам

 If (node == NIL) Then

   Return node;

 // Если нашли, то возвращаем указатель на найденную вершину.

 If (node.key == key) Then

   Return node;

 // Если ключ найденной вершины больше того, который мы ищем

 If (node.key > key) Then

   // То искать в левом поддереве

   Return TreeSearch(node.left, key);

 Else

   // Иначе в правом поддереве

   Return TreeSearch(node.right, key);

End

Итеративно:

TreeSearch(node,key)

Begin

 // Пока ещё есть вершины среди которых можно искать

 //(мы просматриваем не все, но несколько) и пока мы не нашли

 While (node != NIL) and (node.key != key) Do

 Begin

   // Если ключ найденногй вершины больше того который мы ищем

   If (node.key > key) Then

     node = node.left; //

Проблемы возникают и при удалении. Нам необходимо сохранить свойство упорядоченности ДДП. При удалении возможны три случая: у удаляемой вершины нет потомков, у удаляемой вершины есть один потомок и у удаляемой вершины два потомка. Если потомков нет, то вершину можно просто удалить. Если потомок один, то удаляемую вершину можно “вырезать”, указав её родителю в качестве потомка единственного имеющегося потомка удаляемой вершины. Если же потомков два, требуются дополнительные действия. Нужно найти следующую за удаляемой (по порядку ключей) вершину, скопировать её содержимое (ключ и данные) в удаляемую вершину (она теперь никуда не удаляется физически, хотя логически исчезает) и удалить найденную вершину (у неё не будет левого потомка). Сначала функция TreeDelete ищет вершину, которую надо удалить, затем переменной nodeTemp присваивается указатель на существующего потомка удаляемой вершины (или NIL, если потомков нет). Далее вершина удаляется из дерева, при этом отдельно рассматриваются случаи: когда потомков нет и когда удаляемая вершина – это корень дерева. Возвращаемое значение – это указатель на удалённую вершину. На неё уже нет никаких ссылок в самом дереве, но она всё ещё занимает память. Момент её реального удаления зависит от используемых методов распределения памяти.

TreeDelete(Tree,node)

Begin

 // Если потомков не более одного (случаи 1 и 2)

 If (node.left == NIL) or (node.right == NIL) Then

   del = node; // физически удаляем текущую вершину

 Else

   del = TreeNext(node); // Иначе следующую

 If (del.left != NIL) Then // Пытаемся найти хоть одного потомка

   nodeTemp = del.left;

 Else

   nodeTemp = del.right;

 // Если есть, родителем потомка делаем родителя

 // удаляемой вершины (случай 2)

 If (nodeTemp != NIL) Then

   nodeTemp.nodeParent = del.nodeParent;

 // Если удаляем корень дерева, надо указать новый корень дерева

 If (del.nodeParent == NIL) Then

   Tree.root = nodeTemp;

 Else

 Begin

   // Указываем родителю удаляемой вершины качестве потомка

   // потомок удаляемой вершины

   If (del.nodeParent.left == del) Then

     del.nodeParent.left = nodeTemp;

   Else

     del.nodeParent.right = nodeTemp;

 End

 If (del != node) Then // Если случай 3

 Begin

   node.key = del.key; // Скопировать ключ

   { копирование дополнительных данных }

 End

 Return del;

End