tailieunhanh - GIÁO TRÌNH TOÁN RỜI RẠC - CHƯƠNG VI CÂY_4

Duyệt cây nhị phân trong hình trên theo trung thứ tự là: a+b c d/2 và đây là biểu thức (1) đã bỏ đi các dấu ngoặc. Ta nói rằng biểu thức (1) được biểu diễn bằng cây nhị phân T( ) trong hình trên, | CHƯƠNG VI CÂY . Ký pháp Ba Lan Xét biểu thức đại số sau đây a b c- 1 Ta vẽ một cây nhị phân như hình dưới đây trong đó mỗi đỉnh trong mang dấu của một phép tính trong 1 gốc của cây mang phép tính sau cùng trong 1 ở đây là dấu nhân ký hiệu là mỗi lá mang một số hoặc một chữ đại diện cho số. Duyệt cây nhị phân trong hình trên theo trung thứ tự là a b c - d 2 2 và đây là biểu thức 1 đã bỏ đi các dấu ngoặc. Ta nói rằng biểu thức 1 được biểu diễn bằng cây nhị phân T trong hình trên hay cây nhị phân T này tương ứng với biểu thức 1 . 87 Ta cũng nói cách viết ký pháp quen thuộc trong đại số học như cách viết biểu thức 1 là ký pháp trung thứ tự kèm theo các dấu ngoặc. Ta biết rằng các dấu ngoặc trong 1 là rất cần thiết vì 2 có thể hiểu theo nhiều cách khác 1 chẳng hạn là a b c - d 2 3 hoặc là a b c - d 2 4 Các biểu thức 3 và 4 có thể biểu diễn bằng cây nhị phân trong các hình sau. Hai cây nhị phân tương ứng là khác nhau nhưng đều được duyệt theo trung thứ tự là 2 . Đối với cây trong hình thứ nhất nếu duyệt theo tiền thứ tự ta có a b - c d 2 5 88 và nếu duyệt theo hậu thứ tự ta có a b c d 2 - 6 Có thể chứng minh được rằng 5 hoặc 6 xác định duy nhất cây nhị phân trong hình thứ nhất do đó xác định duy nhất biểu thức 1 mà không cần dấu ngoặc. Chẳng hạn cây nhị phân trên hình thứ hai được duyệt theo tiền thứ tự là - a b c d 2 khác với 5 . và được duyệt theo hậu thứ tự là a b c d 2 - khác với 6 . Vì vậy nếu ta viết các biểu thức trong đại số trong lôgic bằng cách duyệt cây tương ứng theo tiền thứ tự hoặc hậu thứ tự thì ta không cần dùng các dấu ngoặc mà không sợ hiểu nhầm. Người ta gọi cách viết biểu thức theo tiền thứ tự là ký pháp Ba Lan còn cách viết theo hậu thứ tự là ký pháp Ba Lan đảo để ghi nhớ đóng góp của nhà toán học và lôgic học Ba Lan Lukasiewicz 18781956 trong vấn đề này. Việc chuyển một biểu thức viết theo ký pháp quen thuộc có dấu ngoặc sang dạng ký pháp Ba Lan hay ký pháp Ba Lan đảo hoặc ngược lại có thể thực hiện bằng cách vẽ cây nhị phân tương ứng như đã .