Структуры и алгоритмы обработки данных

Икеа спб еще на сайте. | самый лучший кондиционер для белья. | купить спортивный костюм мужской. | Смотрите на сайте косметолог подольск. | Автосалон Ац гранд, ац гранд свежие отзывы покупателей. |

Представление выражений с помощью деревьев


С помощью деревьев можно представлять произвольные арифметические выражения. Каждому листу в таком дереве соответствует операнд, а каждому родительскому узлу v операция. В общем случае дерево при этом может оказаться не бинарным.

Однако если число операндов любой операции будет меньше или равно двум, то дерево будет бинарным. Причем если все операции будут иметь два операнда, то дерево окажется строго бинарным.

pic4_16.gif (3415 bytes)

Рис.4.16. Представление арифметического выражения произвольного вида в виде дерева.

pic4_17.gif (1654 bytes)

Рис. 4.17. Представление арифметического выражения в виде бинарного дерева

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

Затем от листьев к корню производится выполнение операций. В процессе выполнения в узел операции записывается результат ее выполнения. В конце вычислений в корень будет записано значение, которое и будет являться результатом вычисления выражения.

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

pic4_18.gif (2559 bytes)

Рис.4.18. Вычисление арифметического выражения с помощью бинарного дерева

pic4_19.gif (2898 bytes)

Рис. 4.19. Представление логического выражения в виде бинарного дерева




Начало  Назад  Вперед



Книжный магазин