Программирование на языке высокого уровня. Марапулец Ю.В. - 73 стр.

     Для бинарных деревьев определены операции [8]:
• включения узла в дерево;
• поиска по дереву;
• обхода дерева;
• удаления узла.
     Удобнее всего с бинарными деревьями работать с помощью рекурсивных алгорит-
мов (понятие рекурсии будет рассмотрено далее). Но для каждого рекурсивного алго-
ритма можно создать его нерекурсивный эквивалент, который правда несколько услож-
няет написание программного кода.
     Рассмотрим пример исходного кода, реализующего бинарное дерево, представлен-
ное на рис.5. Для формирования дерева и работы с ним удобно иметь два указателя - на
левое и правое поддерево. Как и ранее значения состоят из целых чисел Value, таким об-
разом, получаем следующее описание элемента дерева:

struct X
{
        int Value;
        X *Left;
        X *Right;
};

      Первоначально создадим первый элемент дерева с помощью функции
FirstElement(), исходный код которой практически аналогичен приведенному ранее при
инициализации списка. Функция создает первый элемент, получая его значение A в ка-
честве параметра и выделяя под него память:

X * FirstElement(int A)
{
       X *FirstX;
       FirstX = (X *)malloc(sizeof(X));
       FirstX->Value = A;
       FirstX->Left = 0;
       FirstX->Right = 0;
       return FirstX;
}

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

X * SearchAndInsertElement(X *Root, int A)
{
       X *ElementX = Root;
       X *Prev;
       bool Found = false;
       while (ElementX && !Found)
       { // Поиск заданного элемента
              Prev = ElementX;
              if (A == ElementX->Value)

                                             73