АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

A b с d

Рис. 5.15

Висячие вершины изображенного дерева соответствуют операндам, а внутренние вершины - арифметическим операциям в выражении.

Вычисление значения выражения при заданных значениях операндов состоит в последовательной свертке дерева, определяемой следующей схемой:

1) в дереве выделяется внутренняя вершина, все потомки которой являются висячими вершинами;

2) вычисляется значение операции, приписанной найденной вершине, для значений операндов, приписанных потомкам этой вершины;

3) вычисленное значение заменяет символ операции, приписанный вершине, а ее потомки удаляются из дерева вместе с ведущими в них ребрами;

4) если полученное в результате дерево содержит более одной вершины, то действия 1 - 4 выполняются еще раз.

Аналогичное представление c помощью нагруженных деревьев может быть использовано и для более сложных видов записи выражений, составленных с помощью арифметических функций и специальных операций, таких как: суммирование, поиск максимума, условное вычисление и др.

Упражнение. Составить алгоритм вычисления значений формул, использующих простые переменные, элементы массивов, сравнения, традиционные арифметические функции и операцию условного суммирования. (Для этого следует использовать представление таких формул с помощью корневых деревьев.)

Практически важным классом деревьев являются бинарные деревья.

Дата добавления: 2015-09-27 | Просмотры: 518 | Нарушение авторских прав