A b с d
Рис. 5.15
Висячие вершины изображенного дерева соответствуют операндам, а внутренние вершины - арифметическим операциям в выражении.
Вычисление значения выражения при заданных значениях операндов состоит в последовательной свертке дерева, определяемой следующей схемой:
1) в дереве выделяется внутренняя вершина, все потомки которой являются висячими вершинами;
2) вычисляется значение операции, приписанной найденной вершине, для значений операндов, приписанных потомкам этой вершины;
3) вычисленное значение заменяет символ операции, приписанный вершине, а ее потомки удаляются из дерева вместе с ведущими в них ребрами;
4) если полученное в результате дерево содержит более одной вершины, то действия 1 - 4 выполняются еще раз.
Аналогичное представление c помощью нагруженных деревьев может быть использовано и для более сложных видов записи выражений, составленных с помощью арифметических функций и специальных операций, таких как: суммирование, поиск максимума, условное вычисление и др.
Упражнение. Составить алгоритм вычисления значений формул, использующих простые переменные, элементы массивов, сравнения, традиционные арифметические функции и операцию условного суммирования. (Для этого следует использовать представление таких формул с помощью корневых деревьев.)
Практически важным классом деревьев являются бинарные деревья.
Дата добавления: 2015-09-27 | Просмотры: 525 | Нарушение авторских прав
|