Постройте деревья соответствующие следующим арифметическим выражениям

Постройте деревья соответствующие следующим арифметическим выражениям

Ответы

(О нет! Что-то пошло не так во время добавления ответа
Слишком коротко. Напишите минимум 20 символов, чтобы объяснить все.)

(О нет! Что-то пошло не так во " alt="Решение приложил.

Ответ

Проверено экспертом

Деревья строятся просто: добавляем узел – операцию, которая выполняется последней, и к ней два потомка – аргументы этой операции. Например, для выражения a + b операцией будет "+", а аргументами – a и b. Затем в таком же виде представляем аргументы этой операции, пока все аргументы не будут содержать выражений. Построенные деревья во вложении.

Префиксная форма записи заключается в том, что сначала записывается операция, потом префиксная запись её первого аргумента, потом второго аргумента. Это соответствует обходу дерева сверху вниз и слева направо, записываем, что сверху, потом идем вниз. Вот что получится в итоге:
а) * + a b + c * 2 d
б) + * — * 2 a * 3 d c * 2 b
в) — * 3 a * + * 2 b c d

В постфиксной записи, наоборот, записываются сначала аргументы, потом операция. Это соответствует обходу дерева снизу-вверх.
а) a b + c 2 d * + *
б) 2 a * 3 d * — c * 2 b * +
в) 3 a * 2 b * c + d * —

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

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

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

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

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

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

Читайте также:  Перетащите файлы сюда или загрузите вручную

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

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

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

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

Соответствующее бинарное дерево.

Рис. Бинарное дерево, представляющее

Тогда три варианта обхода этого дерева порождают три известные формы записи арифметического выражения:

1) КЛП — префиксную запись

2) ЛКП — инфиксную запись (без скобок, необходимых для задания последовательности выполнения операций)

3) ЛПК — постфиксную запись

ЛЕКЦИЯ 12. ГРАФЫ ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ. СПОСОБЫ ЗАДАНИЯ И РЕАЛИЗАЦИЯ

Цели и задачи лекции: показать способы задания и реализация графов

Основные рассматриваемые вопросы. Основные определения. Способы задания и реализация графов. Наличие циклов, связность.

Граф G — это упорядоченная пара (V, Е), где V- непустое множество вершин, Е — множество пар элементов множества V, называемое множеством ребер.

Упорядоченная пара элементов из V называется дугой. Если все пары в Е упорядочены, то граф называется ориентированным (орграфом).

Если дуга е ведет от вершины vl к вершине v2, то говорят, что дуга е инцидентна вершине v2, а вершина v2 являются смежной вершине vv В случае неориентированного графа ребро е является инцидентной обеим вершинам vl и v2, а сами вершины — взаимно смежными.

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

Читайте также:  Как узнать номер таксофона

Путь, начинающийся и заканчивающийся в одной и той же вершине, называется циклом. Граф, в котором отсутствуют циклы, называется ациклическим.

Петля — дуга, соединяющая некоторую вершину сама с собой.

— Выбор структуры данных для хранения графа в памяти имеет принципиальное значение при разработке эффективных алгоритмов.

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

Матрица смежности — это двумерный массив V, размером пХп:

При этом vij=0, если вершина i не смежна вершине; vij=весу ребра (дуги), если вершина i смежна вершине j, vij=весу петли.

Пространственная сложность этого способа V(n)

O(n 2 ). Способ очень хорош, когда надо часто проверять смежность или находить вес ребра по двум заданным вершинам.

Матрица инцидентности — это двумерный массив U размером пХт:

При этом uij=0, если вершина i не инцидентна ребру j, uij=весу ребра, если вершина инцидентна ребру j.

Пространственная сложность этого способа V(n, m)

O(n*m). Матрица инцидентности лучше всего подходит для операции «перечисление ребер, инцидентных вершине х».

Списки смежных вершин — это одномерный массив размером п, содержащий для каждой вершины указатели на списки смежных с ней вершин:

Weight: integer; <вес ребра>
Next: PNode;

TAdjacencyList = array [l..n] of record
NodeWeight: integer; <вес вершины>
Name: string;

Пространственная сложность этого способа Fmax(w)

0(w 2 ). Хранение списков в динамической памяти позволяет сократить объем расходуемой памяти, так как в этом случае не будет резервироваться место под п соседей для каждой вершины. Можно и сам массив представить в виде динамического списка, но это не имеет особого смысла, так как граф обычно является статичной (неизменяемой) структурой.

Читайте также:  Термометр и снежинка на айфон

Этот способ хранения лучше всех других подходит для операции «перечисление всех вершин, смежных с х».

Список ребер — это одномерный массив размером т, содержащий список пар вершин, инцидентных с одним ребром графа:

Пространственная сложность этого способа V(m)

O(m). Этот способ хранения графа особенно удобен, если главная операция, которой чаще всего выполняется, это перечисление ребер или нахождение вершин и ребер, находящихся в отношениях инцидентности.

PBranch = A TBranch;

Next: PNode; <следующая вершина>end; TBranch = record

Пространственная сложность этого способа V(n, m)

Дата добавления: 2018-05-02 ; просмотров: 1229 ;

Ссылка на основную публикацию
Перетащите файлы сюда или загрузите вручную
Файлы с компьютера можно с помощью перетаскивания отправить в библиотеку OneDrive для бизнеса или на сайт группы SharePoint. Можно также...
Ошибка пакета безопасности на транспортном уровне
Накануне столкнулся с одной проблемой. При подключении к удаленному рабочему столу на Windows Server 2008 R2 со старых клиентов RDP...
Ошибочное имя локализации 1с
Язык интерфейса платформы (Language of platform interface) Различные языки интерфейса платформы позволяют создавать прикладные решения для пользователей, говорящих на языках,...
Покупка не завершена компания выдавшая
Сведения о кредитной карте отклонены компанией, обслуживающей кредитную карту. Имейте в виду, что в некоторых случаях средства на вашем счете...
Adblock detector