1. Học hỏi
    2. /
  2. Khoa Học
    3. /
  3. Cấu trúc dữ liệu và Thuật toán với Python
Connected

Bài tập

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:

Graphical representation of a binary tree that has arithmetic expressions.

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.

Hướng dẫn

100 XP
  • Kiểm tra xem current_node có 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.