Дерево вычисления

Определения и обозначения

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

Вершина дерева — его элемент, обозначающий число, переменную или операцию. Число или переменная задают значение, с которым работают, а операция указывает, что нужно сделать с её операндами. Различая эти виды вершин, можно понять, где в дереве находятся исходные данные, а где — действия.

Лист дерева — вершина, у которой нет дочерних вершин, то есть от неё не отходят ветви к другим элементам. Обычно листьями становятся числа и переменные: над ними не нужно выполнять дальнейшие действия внутри этого дерева. Листья служат исходными значениями, от которых начинается вычисление.

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

Как это устроено

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

Главную операцию нельзя выбирать по тому, какой знак встретился первым слева: запись символов не всегда совпадает с порядком выполнения действий. Сначала учитывают скобки, затем правила приоритета, например умножение обычно выполняется раньше сложения. Поэтому в выражении 2 + 3 * 4 корнем будет сложение, а умножение окажется в поддереве. Если поставить в корень умножение, дерево покажет другой порядок действий и будет соответствовать уже иному выражению.

Вычислять дерево начинают с листьев, потому что операция не даёт результата, пока неизвестны её операнды. Сначала находят значения чисел и переменных, а затем переходят к вершинам-операциям, у которых уже вычислены все дочерние части. Например, в дереве выражения 2 + 3 * 4 сперва вычисляют 3 * 4, затем складывают результат с 2. Так движение от листьев к корню повторяет порядок вычисления исходного выражения.

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

При нескольких уровнях вложенности каждый операнд-выражение получает своё поддерево, а его вершиной становится главная операция именно этой части. В выражении (8 − 2) * (3 + 1) / 2 сначала выделяют действия в скобках, а затем учитывают, что умножение и деление имеют одинаковый приоритет и выполняются слева направо. Поэтому корнем будет деление, слева от него — поддерево умножения, справа — число 2. В поддереве умножения находятся отдельные поддеревья вычитания и сложения.

Элементы дерева вычисления и их роль

Сначала определите роль каждой вершины: исходное это значение, операция или целая часть выражения. Затем проверьте, что у каждой операции в дочерних вершинах стоят её операнды, а поддерево соответствует отдельному выражению. Такая проверка помогает заметить пропущенное действие или неверно выбранный корень.

Разбор задач

Задача 1. Постройте дерево вычисления для выражения 7 + 3.

1. Единственная операция здесь — сложение, поэтому она является главной и помещается в корень.
2. Её операнды — числа 7 и 3. Размещаем их в двух дочерних вершинах; у этих вершин нет потомков, значит, это листья.
3. Проверяем структуру: от корня + отходят две ветви к 7 и 3. Дерево сохраняет исходный смысл сложения этих чисел.

Ответ: корень — +, его листья — 7 и 3; значение выражения равно 10.

Задача 2. Постройте дерево и найдите значение выражения 2 + 3 * 4.

1. Сначала определяем главную операцию. Умножение выполняется раньше сложения, поэтому последним выполняется сложение, оно и становится корнем.
2. Левый операнд корня — число 2, а правый — выражение 3 * 4. В его поддереве ставим умножение и помещаем числа 3 и 4 в листья.
3. Вычисляем снизу вверх: сначала 3 * 4 = 12, затем 2 + 12 = 14. Порядок вычислений совпадает с приоритетом операций в исходной записи.

Ответ: корень — +, поддерево справа — 3 * 4; значение выражения равно 14.

Задача 3. Постройте дерево и вычислите (8 − 2) * (3 + 1) / 2.

1. Вычисления в скобках выполняются отдельно. Но между умножением и делением приоритета нет, а действия идут слева направо, поэтому последней будет операция деления.
2. Деление помещаем в корень: слева строим поддерево для (8 − 2) * (3 + 1), справа ставим лист 2. В левом поддереве корень — умножение, а его дочерние поддеревья соответствуют вычитанию и сложению.
3. Сначала получаем 8 − 2 = 6 и 3 + 1 = 4. Затем вычисляем 6 * 4 = 24, а в корне — 24 / 2 = 12.

Ответ: корень — деление, под ним находятся поддерево умножения и лист 2; значение выражения равно 12.

Типичные ошибки

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

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

Ошибка — считать операнд листом, даже если он сам является выражением. Это упрощение пропускает операции внутри операнда и не показывает, откуда берётся его значение. Если в дочерней части записи есть действие, постройте для неё поддерево и проверьте, что все операции исходного выражения попали в дерево.

Ошибка — вычислять дерево сверху вниз, пытаясь сразу найти значение корня. Корневая операция зависит от значений дочерних вершин, поэтому такой способ не даёт результата, пока операнды неизвестны. Начинайте с листьев и переходите к операции лишь тогда, когда вычислены все её операнды; проверка проста: у каждой выполняемой вершины уже должны быть известны дочерние значения.

Связь с другими темами

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

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

Что запомнить

• Корень дерева соответствует главной операции выражения.
• Операнды операции располагаются в дочерних вершинах.
• Числа и переменные без дальнейших операций обычно образуют листья.
• Скобки влияют на структуру дерева, но не становятся его вершинами.
• Вычисление дерева выполняют от листьев к корню.
• Одному выражению соответствует дерево, сохраняющее его порядок вычислений.