Cây biểu thức
Cây biểu thức là những cây trong đó các nút lá có giá trị được vận hành và các nút bên trong chứa toán tử mà trên đó nút lá sẽ được thực hiện.
Ví dụ
4 + ((7 + 9) * 2) sẽ có một cây biểu thức như sau
Thuật toán tạo cây biểu thức
Gọi T là cây biểu thức.
If T is not NULL:
If T->data is an operand:
return T.data
A = solve(T.left)
B = solve(T.right)
--> Calculate operator for 'T.data' on A and B, and call recursively,
return calculate(A, B, T.data)
Làm thế nào để xây dựng một cây biểu thức?
Để tạo Cây biểu thức cho biểu thức đã cho, chúng tôi thường sử dụng Cấu trúc dữ liệu ngăn xếp.
Ban đầu, chúng tôi Lặp lại biểu thức postfix đã cho và làm theo các bước như dưới đây -
- Nếu chúng ta nhận được một toán hạng trong biểu thức đã cho, thì hãy đẩy nó vào ngăn xếp. Nó sẽ trở thành gốc của Cây biểu thức.
- Nếu một toán tử nhận được hai giá trị trong biểu thức, thì hãy thêm vào cây biểu thức làm con của nó và đẩy chúng vào nút hiện tại.
- Lặp lại Bước-1 và Bước-2 cho đến khi chúng tôi không hoàn thành biểu thức đã cho.
- Bây giờ, hãy kiểm tra xem mọi nút gốc có chứa gì ngoài các toán hạng hay không và mọi nút con chỉ chứa các giá trị.