Составители:
Рубрика:
в) с помощью построения дерева-формулы t преобразовать заданную фор-
мулу f из инфиксной формы в префиксную (перечисление узлов t в порядке
КЛП) или в постфиксную (перечисление в порядке ЛПК);
г) выполнить с формулой f преобразования, обратные преобразованиям
из п. в);
д) если в дереве-формуле t терминалами являются только цифры, то вы-
числить (как целое число) значение дерева-формулы t;
е) упростить дерево-формулу t, заменяя в нем все поддеревья, соответст-
вующие формулам (f + 0), (0 + f), (f - 0), (f * 1), (1 * f), на поддеревья, соответ-
ствующие формуле f, а поддеревья, соответствующие формулам (f * 0) и (0 *
f), - на узел с 0;
ж) преобразовать дерево-формулу t, заменяя в нем все поддеревья, соот-
ветствующие формулам ( f
1
* ( f
2
+ f
3
) ) и ( ( f
1
+ f
2
) * f
3
), на поддеревья, соот-
ветствующие формулам ( ( f
1
* f
2
) + ( f
1
* f
3
) ) и ( ( f
1
* f
3
) + ( f
2
* f
3
) );
з) выполнить в дереве-формуле t преобразования, обратные преобразова-
ниям из п. ж);
и) построить дерево-формулу t1 - производную дерева-формулы t по за-
данной переменной.
10. Деревом поиска, или таблицей в виде дерева, называется бинарное де-
рево, в котором слева от любого узла находятся узлы с элементами, меньшими
элемента из этого узла, а справа − с большими элементами. Предполагается,
что все элементы дерева попарно различны и что их тип Elem допускает при-
менение операций сравнения; пример дерева поиска показан на рис.3.13.
6
3 9
1 5 7
Рис. 3.13. Пример дерева поиска
Требуется:
а) по заданному файлу F (типа
file of Elem), все элементы которого различ-
ны, построить соответствующее дерево поиска ts;
б) для заданного дерева поиска ts проверить, входит ли в него элементе ти-
па Elem, и если не входит, то добавить элементе в дерево поиска ts;
в) записать в файл F элементы заданного дерева поиска ts в порядке их
возрастания.
11
4 8
65
в) с помощью построения дерева-формулы t преобразовать заданную фор-
мулу f из инфиксной формы в префиксную (перечисление узлов t в порядке
КЛП) или в постфиксную (перечисление в порядке ЛПК);
г) выполнить с формулой f преобразования, обратные преобразованиям
из п. в);
д) если в дереве-формуле t терминалами являются только цифры, то вы-
числить (как целое число) значение дерева-формулы t;
е) упростить дерево-формулу t, заменяя в нем все поддеревья, соответст-
вующие формулам (f + 0), (0 + f), (f - 0), (f * 1), (1 * f), на поддеревья, соответ-
ствующие формуле f, а поддеревья, соответствующие формулам (f * 0) и (0 *
f), - на узел с 0;
ж) преобразовать дерево-формулу t, заменяя в нем все поддеревья, соот-
ветствующие формулам ( f1 * ( f2 + f3 ) ) и ( ( f1 + f2 ) * f3 ), на поддеревья, соот-
ветствующие формулам ( ( f1 * f2 ) + ( f1 * f3 ) ) и ( ( f1 * f3 ) + ( f2 * f3 ) );
з) выполнить в дереве-формуле t преобразования, обратные преобразова-
ниям из п. ж);
и) построить дерево-формулу t1 - производную дерева-формулы t по за-
данной переменной.
10. Деревом поиска, или таблицей в виде дерева, называется бинарное де-
рево, в котором слева от любого узла находятся узлы с элементами, меньшими
элемента из этого узла, а справа − с большими элементами. Предполагается,
что все элементы дерева попарно различны и что их тип Elem допускает при-
менение операций сравнения; пример дерева поиска показан на рис.3.13.
6
3 9
1 5 7 11
4 8
Рис. 3.13. Пример дерева поиска
Требуется:
а) по заданному файлу F (типа file of Elem), все элементы которого различ-
ны, построить соответствующее дерево поиска ts;
б) для заданного дерева поиска ts проверить, входит ли в него элементе ти-
па Elem, и если не входит, то добавить элементе в дерево поиска ts;
в) записать в файл F элементы заданного дерева поиска ts в порядке их
возрастания.
65
