Обход в прямом порядке и польская нотация
Деревья выражений — это разновидность бинарных деревьев, представляющих арифметические выражения:
Применив обход в симметричном порядке к дереву выражений, вы получите инфиксную нотацию. Для данного дерева она будет выглядеть так: (10-5)*3.
Применив обход в прямом порядке к дереву выражений, вы получите префиксную нотацию, известную также как польская нотация, — оператор записывается перед операндами. Для данного дерева она будет выглядеть так: *-10 5 3.
Применив обход в обратном порядке к дереву выражений, вы получите постфиксную нотацию, известную также как обратная польская нотация, — оператор записывается после операндов. Для данного дерева она будет выглядеть так: 10 5- 3*.
Реализуйте обход в прямом порядке, чтобы получить префиксную нотацию для этого дерева выражений.
Это упражнение является частью курса
Структуры данных и алгоритмы на Python
Инструкции к упражнению
- Проверьте, существует ли
current_node. - Выведите значение
current_node. - Вызовите функцию
pre_order()рекурсивно для каждой из частей дерева.
Интерактивное практическое упражнение
Попробуйте выполнить это упражнение, дополнив этот пример кода.
import queue
class ExpressionTree:
def __init__(self):
self.root = None
def pre_order(self, current_node):
# Check if current_node exists
____:
# Print the value of the current_node
____
# Call pre_order recursively on the appropriate half of the tree
____
____
et = CreateExpressionTree()
et.pre_order(et.root)