(←) предыдущая запись ; следующая запись (→)
Мы же с вами напоследок разберём совсем простую операцию — вычисление результата выражения. Мы начинаем с корня дерева (он сверху, не удивляйтесь) и применяем операции одна за другой.
Сначала мы хотим вычислить сумму. Сумму единицы и… правой ветки.
Чтобы вычислить результат операции в вершине, нужно сначала вычислить значения в ветках, и только потом вернуться к исходной операции. Это легко делается при помощи рекурсии. Я же тут покажу только последовательность преобразований дерева, которая происходит.
Стартуем с такого дерева:
+
/ \
/ \
1 +
/ \
* 4
/ \
2 3
Спускаемся до того места, где можем что-то конкретное вычислить. Вычисляем и заменяем целую ветку на результат:
+
/ \
/ \
1 +
/ \
6 4
Теперь мы можем подняться выше. Нам повезло: все операнды уже вычислены, и нам не надо снова спускаться вниз по дереву. Достаточно посчитать результат и снова подняться выше:
+
/ \
/ \
1 10
Ну и последнее вычисление даёт нам дерево с одной вершиной, вершиной результата:
11
Готово! Вот так просто!
Не понимаю, почему мне учителя не объяснили это ещё в первом классе?! Моя жизнь не была бы прежней.
(9/9)
в начало (↑)