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

1) Указатель на удаляемый узел сохраняется во временной переменной указателе (этот указатель потом используется для освобождения динамически выделенной памяти).

2) Указатель в родительском узле удаляемого узла устанавливается так, чтобы он указывал на замещающий узел.

3) Указатель в родительском узле замещающего узла устанавливается на нулевое значение.

4) Указатель на правое поддерево в замещающем узле устанавливается так, чтобы указывать на правое поддерево удаляемого узла.

5) Удаляется узел, на который указывает временная переменная указатель.

Действия, предпринятые для замещающего узла с левым узлом-потомком аналогичны действиям для замещающего узла без узлов-потомков; но алгоритм должен также перемещать и узел-потомок. Если замещающий узел имеет левый узел-потомок, то при удалении предпринимаются следующие действия :

1) Указатель на удаляемый узел сохраняется во временной переменной указателе.

2) Указатель в родительском узле удаляемого узла устанавливается так, чтобы он указывал на замещающий узел.

3) Указатель в родительском узле замещающего узла устанавливается на левый узел-потомок замещающего узла.

4) Указатель на правое поддерево в замещающем узле устанавливается так, чтобы указывать на правое поддерево удаляемого узла.

5) Удаляется узел, на который указывает временная переменная указатель.

Напишите функцию deleteNode, которая принимает в качестве аргумента указатель на корневой узел объекта дерева и удаляемое значение. Функция должна найти в дереве узел, содержащий удаляемое значение, и использовать рассмотренные алгоритмы для его удаления. Если в дереве не найдено это значение, то функция должна напечатать сообщение, которое поясняет, удалено или нет указанное значение. Модифицируйте программу, приведенную на рис. 15.16, используя эту функцию. После удаления элемента, вызовите функции обходов inOrder, preOrder и postOrder для подтверждения того, что операция удаления была выполнена корректно.

15.23. (Дерево двоичного поиска) Напишите функцию binaryTreeSearch, которая ищет заданное значение в объекте дерева двоичного поиска. Функция должна принимать в качестве аргументов указатель на корневой узел двоичного дерева и ключ поиска. Если узел, содержащий ключ поиска, найден, то функция должна вернуть ука-

92 72 69 44 32 19 11

затель на этот узел; в противном случае функция должна вернуть нулевой указатель.

15.24. (Послойный обход двоичного дерева) Программа, приведенная на рис. 15.16, демонстрирует три рекурсивных способа обхода двоичного дерева: последовательный обход, обход в ширину и обратный обход. В этом упражнении представлен послойный обход двоичного дерева, при котором значения узлов печатаются от уровня к уровню, начиная с корневого узла. Значения в узлах печатаются по уровням дерева слева направо. Алгоритм послойного обхода не является рекурсивным алгоритмом. Он использует объект очереди для управления процессом вывода узлов на печать. Этот алгоритм заключается в следуюш;ем :

1) В очередь вставляется корневой узел.

2) Пока в очереди существуют узлы. Взять из очереди следующий узел Напечатать значение этого узла

Если указатель на левый узел-потомок имеет ненулевое значение

Вставить левый узел-потомок в очередь

Если указатель на правый узел-потомок имеет ненулевое значение

Вставить правый узел-потомок в очередь.

Напишите функцию-элемент levelOrder для выполнения послойного обхода двоичного дерева. Модифицируйте программу, приведенную на рис. 15.16, чтобы использовать эту функцию. (Замечание: вам необходимо также модифицировать и встроить в программу функции обработки очереди на рис. 15.12).

15.25. (Печать дерева) Напишите рекурсивную функцию-элемент output-Tree для отображения объекта двоичного дерева на экране. Функция должна выводить дерево по слоям, начиная с вершины, находящейся на экране слева, и далее продвигаясь вниз по дереву и вправо по экрану. Каждый уровень выводится на экране вертикально. Например, двоичное дерево, показанное на рис. 15.19, должно выводиться следующим образом:

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

Пока указатель на текущий узел имеет ненулевое значение

Рекурсивно вызывается outputTree для правого поддерева текущего узла с аргументом totalSpace + 5

Используется структура for со счетчиком от 1 до totalSpace для вывода пробелов

Выводится значение в текущем узле

Устанавливается указатель на левое поддерево текущего узла Увеличивается значение totalSpace на 5.

Специальный раздел: построение вашего собственного компилятора

В упражнениях 5.18 и 5.19 главы 5 мы ввели понятие языка машины Простотрон (ЯМП) и вы создали простейшую программу, моделирующую выполнение программ, написанных на ЯМП. В этом разделе мы построим компилятор, который осуществляет преобразование программ, написанных на языке высокого уровня, в программы на ЯМП. Этот раздел объединяет все элементы и этапы программирования в единое целое. Вы напишете программы на этом новом языке высокого уровня, скомпилируете эти программы с помощью построенного вами компилятора и выполните эти программы на модели, которую вы построили в упражнении 5.19 главы 5. Теперь, вам следует без колебаний приступить к реализации вашего компилятора с помощью объектно-ориентированного подхода.

15.26. (Язык Простотрона) До того, как мы начнем строить компилятор, обсудим простейший, но очень мощный язык программирования высокого уровня, аналогичный ранним версиям популярного языка БЕЙСИК. Мы назовем этот язык Языком Простотрона - ЯП. Каждый оператор ЯП состоит из номера строки и инструкции ЯП. Нумерация строк проводится в порядке возрастания. Каждая инструкция начинается с одной из следующих команд ЯП : rem, input, let, print, goto, if/goto или end (см. рис. 15.20). Все команды, за исключением команды end, могут использоваться повторно. В ЯП вычисляются только целые выражения, использующие операции +, -, * и I. Эти операции выполняются с тем же приоритетом, что и в С. Для изменения последовательности выполнения операций в выражениях могут использоваться круглые скобки.