17.14. Пусть в дереве-формуле (см. Упр. 17.13) в качестве терминалов используются не только цифры, но и буквы, играющие, роль переменных. Описать процедуру, которая:
а)* упрощает дерево-формулу T, заменяя в нем все поддеревья, соответствующие формулам (f+0), (0+f),(f—0),
(f*1) и (1*f), на поддеревья, соответствующие формуле f, а поддеревья, соответствующие формулам (f*0) и (0*f),—. на вершину с 0;
б) преобразует дерево-формулу Т, заменяя в нем все поддеревья, соответствующие формулам (f1± f2)*f3) и (f1*(f2±f3), на поддеревья, cоответствующие формулам:
((f1* f3) ± (f2* f3)) ((f1* f2) ± (f1* f3))
в) выполняет в дереве-формуле Т преобразования, обратные преобразованиям из п. б;
г) cтроит дерево-формулу Т1 —производную дерева- формулы Т' по переменной, однобуквенное имя которой являет значением литерного параметра v.
17.15. Предложить и описать на Паскале представление в виде двоичного дерева для формул из упр. 17.13, в которых в качестве терминалов используются любые неотрицательные целые числа. Для такого представления реализовать те же операции, что и в упр. 17.13.
17.16. Деревом поиска, или таблицей в виде дерева, называется двоичное дерево в котором слева от любой вершины находятся вершины с элементами, меньшими элемента из этой вершины, а справа— с большими элементами (предполагается, что все элементы дерева попарно различны и что их тип (ТЭД) допускает применение операций сравнения); пример такого дерева показан на рис. 21.
Считая описанными тип дерево (см. выше) и тип файл
type файл=file of ТЭД;
определить функцию или процедуру, которая:
а) проверяет, входит ли элемент Е в дерево поиска Т;
б) записывает в файл f элементы дерева поиска Т в порядке их возрастания;
в) добавляет к дереву поиска Т новый элемент Е, если его не было в T;
г) по файлу f, все элементы которого различны, строит соответствующее дерево поиска Т.
17.17.
Во внешнем текстовом файле PROG
записана
(без
ошибок) некоторая программа на языке
Паскаль. Известно,
что в этой программе каждый идентификатор
(служебное
слово или имя) содержит не более 9
латинских букв и или цифр. Напечатать
в алфавитном порядке все различные
идентификаторы этой программы, указав
для каждого
из них число его вхождении в текст
программы. (Учесть,
что в идентификаторах одноименные
прописные и
строчные буквы отождествляются, что
внутри литерных 
значений,
строк-констант и комментариев
последовательности
из букв и цифр не являются идентификаторами,
и
что в записи вещественных чисел может
встретиться буква
Е
или
е.)
Для хранения идентификаторов использовать дерево поиска, элементами которого являются пары—идентификаторы и число его вхождений в текст программы.
Решить предыдущую задачу, но вместе с каждым идентификатором печатать в возрастающем порядке номера всех строк текста программы, в которых он встречается.
Решить задачу 17.17 при условии, что максимальная длина идентификаторов заранее не известна.
17.20. Решить задачу 17.18 при условии, что максимальная длина идентификаторов заранее не известна.