Применение бинарных деревьев

1) Любое алгебраическое выражение, которое содержит переменные, числа, знаки операций и скобки можно представить в виде бинарного дерева (исходя из бинарности этих операций). При этом знак операции помещается в корне, первый операнд – в левом поддереве, а второй операнд – в правом. Скобки при этом опускаются. В результате все числа и переменные окажутся в листьях, а знаки операций – во внутренних узлах.

ассмотрим пример: 3 * (x – 2) + 4.

			Если осуществлять просмотр такого дерева в прямом порядке (сначала проходим корень, затем – левое поддерево, а последним проходим правое поддерево), то получим прямую польскую запись выражения.

Если же осуществить просмотр дерева в обратном порядке (левое поддерево, правое поддерево, корень), то получим обратную польскую запись.

2) Классическая программа из класса интеллектуальных: построение деревьев решений. В этом случае не листовые (внутренние) узлы содержат предикаты – вопросы, ответы на которые могут принимать значения “да” или “нет”. На уровне листьев находятся объекты (альтернативы, с помощью которых распознаются программы). Пользователь получает вопросы, начиная с корня, и, в зависимости от ответа, спускается либо на левое поддерево, либо на правое. Таким образом, он выходит на тот объект, который соответствует совокупности ответов на вопрос.

3) Применение практических задач.

Дата добавления: 2014-01-07