Dùng duyệt pre-order với ký pháp Ba Lan (Polish notation)
Cây biểu thức là một dạng cây nhị phân dùng để biểu diễn các biểu thức số học:
Bằng cách áp dụng duyệt in-order cho một cây biểu thức, bạn sẽ thu được ký pháp trung tố (infix). Với cây đã cho, ký pháp này sẽ là (10-5)*3.
Bằng cách áp dụng duyệt pre-order cho một cây biểu thức, bạn sẽ thu được ký pháp tiền tố (prefix), còn gọi là ký pháp Ba Lan (Polish notation), trong đó toán tử đứng trước các toán hạng. Với cây đã cho, ký pháp này sẽ là *-10 5 3.
Bằng cách áp dụng duyệt post-order cho một cây biểu thức, bạn sẽ thu được ký pháp hậu tố (postfix), còn gọi là ký pháp Ba Lan đảo (reverse Polish notation), trong đó toán tử đứng sau các toán hạng. Với cây đã cho, ký pháp này sẽ là 10 5- 3*.
Hãy viết mã duyệt pre-order để bạn có thể thu được ký pháp tiền tố của cây biểu thức này.
Bài tập này là một phần của khóa học
Cấu trúc dữ liệu và Thuật toán với Python
Hướng dẫn bài tập
- Kiểm tra xem
current_nodecó tồn tại không. - In giá trị của
current_node. - Gọi đệ quy hàm
pre_order()trên các nhánh phù hợp của cây.
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
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)