Використання обходу pre-order з польською нотацією
Дерева виразів — це різновид бінарних дерев, що представляють арифметичні вирази:
Якщо виконати обхід in-order для дерева виразів, ви отримаєте інфіксну нотацію. Для наведеного дерева це буде (10-5)*3.
Якщо виконати обхід pre-order для дерева виразів, ви отримаєте префіксну нотацію, або польську нотацію, де оператор розміщується перед операндами. Для наведеного дерева це буде *-10 5 3.
Якщо виконати обхід post-order для дерева виразів, ви отримаєте постфіксну нотацію, або зворотну польську нотацію, де оператор розміщується після операндів. Для наведеного дерева це буде 10 5- 3*.
Реалізуйте обхід pre-order, щоб отримати префіксну нотацію цього дерева виразів.
Ця вправа є частиною курсу
Структури даних і алгоритми в 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)