Bài giảng MH/MĐ: Toán ứng dụng - Bài 5: Cây và các ứng dụng

TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG MÔN HỌC: TOÁN ỨNG DỤNG Bài 1: CƠ SỞ LOGIC Bài 2: BÀI TOÁN ĐẾM VÀ BÀI TOÁN TỒN TẠI Bài 3: LÝ THUYẾT ĐỒ THỊ Bài 4: BIỂU DIỄN ĐỒ THỊ VÀ CÁC THUẬT TOÁN TÌM KIẾM Bài 5: CÂY VÀ CÁC ỨNG DỤNG TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG Bài 5: CÂY VÀ CÁC ỨNG DỤNG 1. CÂY VÀ CÁC TÍNH CHẤT CƠ BẢN 1.1 Giới thiệu 1.2 Định nghĩa 1.3 Các tính chất cơ bản 2. CÂY KHUNG CỦA ĐỒ THỊ 2.1 Giới thiệu 2.2 Định nghĩa 2.3 Bài toán tìm cây khung ngắn nhất 2.4 Thuật toán Kruskal 2.5 Thuật toán Prim 3. CÂY PHÂN CẤP 3.1 Giới thiệu 3.2 Định nghĩa 3.3 Duyệt cây nhị phân 3.4 Một số ứng dụng của cây TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 1.1 Giới thiệu - Cây là một dạng của đồ thị được nhà toán học Anh, Arthur Cayley, phát biểu và sử dụng từ năm 1857 cho việc xác định những cấu trúc hợp chất hóa học. 1. Cây và các tính chất cơ bản Arthur Cayley (1821-1895) isobutan TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 1.1 Giới thiệu - Sau đó cây được sử dụng nhiều trong khoa học máy tính để xây dựng các thuật toán hiệu quả; tính toán chi phí xây dựng mạng máy tính; mã hóa dữ liệu;... 1. Cây và các tính chất cơ bản TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 1. Cây và các tính chất cơ bản 1.2 Định nghĩa Định nghĩa Cây Cho G=(V,E) là đồ thị vô hướng. G được gọi là một Cây (tree) nếu và nếu G liên thông và không có chu trình đơn. Định nghĩa Rừng - Rừng (forest) là đồ thị mà mỗi thành phần liên thông của nó là một cây. Rừng cây TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 1. Cây và các tính chất cơ bản 1.2 Định nghĩa Ví dụ: c e f d a b c e f d a b c e f d a b c e f d a b G1 G2 G3 G4 G1, G2 là cây; G3, G4 không phải là cây TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 1. Cây và các tính chất cơ bản 1.3 Các tính chất cơ bản Phát biểu 1: Với cây T có n đỉnh, các phát biểu dưới đây là tương đương: 1- T liên thông và có n-1 cạnh. 2- T không có chu trình đơn và có n-1 cạnh . 3- Giữa hai đỉnh bất kỳ có đúng một đường đi đơn. 4- T liên thông và mỗi cạnh là một cầu. B G D E FA C H TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 1. Cây và các tính chất cơ bản 1.3 Các tính chất cơ bản Phát biểu 2: Với cây T là cây có n đỉnh, T có ít nhất là 2 đỉnh treo. D G B F A TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.1 Giới thiệu Cách tạo cây khung của đồ thị Trong đồ thị liên thông G, chúng ta thực hiện loại bỏ một cạnh nằm trên một chu trình nào đó sẽ tạo ra đồ thị G' vẫn có tính liên thông. Thực hiện tiếp việc loại bỏ các cạnh ở các chu trình khác cho đến khi đồ thị T không còn chu trình nhưng vẫn liên thông thì chúng ta thu được một cây nối tất cả các đỉnh của G - gọi là cây khung của đồ thị. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.1 Giới thiệu Ví dụ: Cho đồ thị G trong hình dưới đây, hãy thực hiện tìm các cây khung của đồ thị G. B G D E FA C H TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.2 Định nghĩa Định nghĩa cây khung của đồ thị Cho G=(V,E) là đồ thị vô hướng, liên thông. Cây T=(V,F) với F  E được gọi là cây khung của đồ thị G. B G D E FA C H TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.3 Bài toán tìm cây khung nhỏ nhất Số cây khung của một đồ thị đầy đủ Kn - có n đỉnh - được tính theo công thức là n n-2 . Một đồ thị đầy đủ có 5 đỉnh sẽ có số cây khung là 53= 125. Vậy làm thế nào để tìm được cây khung có độ dài ngắn nhất cho đồ thị có trọng số? B DE F A TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.3 Bài toán tìm cây khung ngắn nhất Cho G=(V,E) là đồ thị vô hướng, liên thông có trọng số. Độ dài m(T) của cây khung T là tổng trọng số các cạnh của cây: Bài toán: Trong số tất cả các cây khung của đồ thị G, hãy tìm ra cây khung có độ dài ngắn nhất - gọi là cây khung ngắn nhất của đồ thị. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.3 Bài toán tìm cây khung ngắn nhất Các bài toán thực tế 1- Bài toán nối mạng máy tính: Với mạng máy tính gồm n máy đánh số từ 1 đến n. Biết chi phí nối máy i với máy j là m(i,j) (chi phí phụ thuộc vào độ dài cáp nối cần sử dụng). Hãy tìm cách nối mạng sao cho tổng chi phí là nhỏ nhất. 2- Bài toán xây dựng hệ thống đường sắt: Chúng ta muốn xây dựng một hệ thống đường sắt nối n thành phố để hành khách từ một thành phố có thể đi đến bất kỳ các thành phố còn lại. Yêu cầu thiết kế để chi phí xây dựng hệ thống đường đi là nhỏ nhất. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.4 Thuật toán Kruskal (năm 1956) - Đồ thị G=(V,E), liên thông, có trọng số - Cây khung T=(V,F), với F  E Thuật toán Kruscal tìm cây khung ngắn nhất B0. F = ø; B1. sắp xếp các cạnh của G thành dãy q(e) các cạnh theo thứ tự tăng dần của trọng số. B2. Repeat Bắt đầu từ cạnh đầu tiên của dãy W, chúng ta nạp dần các cạnh của dãy q(e) vào F theo nguyên tắc cạnh nạp vào F không tạo thành chu trình trong T. Until |F|=n-1 // số phần tử của tập F bằng (n-1) TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.4 Thuật toán Kruskal Ví dụ: Tìm cây khung ngắn nhất của đồ thị G trong hình bên. Giải: Đặt tập là F=ø (F-là tập cạnh của cây khung ngắn nhất) Sắp xếp các cạnh của đồ thị G theo trọng số tăng dần: {(v3, v5), (v4, v6), (v4, v5), (v5, v6), (v3, v4), (v1, v3), (v2, v3), (v2, v4), (v1, v2)}. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.4 Thuật toán Kruskal Ví dụ: (tiếp theo) Thêm vào cạnh (v3, v5) vào F; |F|=1 Xét lực lượng của F, |F|<5, nên tiếp tục quá trình xét nạp: - nạp cạnh (v4, v6) vào F; |F|=2 - nạp cạnh (v4, v5) vào F; |F|=3 - không nạp cạnh (v5, v6) vào F vì tạo chu trình. - không nạp cạnh (v3, v4) vào F vì tạo chu trình. - nạp cạnh (v1, v3) vào F; |F|=4 - nạp cạnh (v2, v3) vào F; |F|=5 Kết thúc vì |F|=5 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.4 Thuật toán Kruskal Ví dụ: (tiếp theo) Kết quả: Cây khung ngắn nhất của đồ thị G như dưới đây. 17 18 4 9 8 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.4 Thuật toán Kruskal Ví dụ: Tìm cây khung ngắn nhất của đồ thị G trong hình dưới. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.5 Thuật toán Prim (năm 1957) - Thuật toán Kruskal không đạt hiệu quả cao trong việc tìm cây khung ngắn nhất cho đồ thị vì số bước thực hiện được tính theo số cạnh của đồ thị. - Thuật toán Prim được đánh giá có hiệu quả hơn với những đồ thị có số cạnh m > n(n-1)/2. Thuật toán được thực hiện theo cách duyệt các đỉnh của đồ thị. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.5 Thuật toán Prim (năm 1957) - Đồ thị G=(V,E), liên thông, có trọng số - Cây khung T=(V,F), với F  E Thuật toán Prim tìm cây khung ngắn nhất Gán F = ø; Chọn u là đỉnh bất kỳ của G; Xác định e là cạnh bất kỳ liên thuộc u, có w(e) bé nhất; Gán F = F  {e}; While (|F|<n-1) do Xác định e, với e là cạnh có trọng số bé nhất, liền kề với một cạnh trong F và không tạo ra chu trình; Gán F = F  {e}; End While TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.5 Thuật toán Prim (năm 1957) Ví dụ 1: Tìm cây khung ngắn nhất của đồ thị G trong hình dưới. Cơ sở Logic C A 7 D 5 4 2 4 2 9 B 79 5 8 8 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.5 Thuật toán Prim Ví dụ 1: Lấy đỉnh xuất phát là A. Bảng thực hiện như sau: B. Tập F A B C D 1 (A,C) 2*,5,9 7,8,9 2*,4,7 4,5,8 2 (C,D),(A,C) 5,9 7,8,9 4*,7 4*,5,8 3 (C,D),(A,C) Loại (A,D) vì tạo chu trình 5,9 7,8,9 7 5,8 4 (C,D),(A,C) 9 7*,8,9 7* 8 5 (B,C),(C,D),(A,C) 9 8,9 8 KQ: độ dài cây khung ngắn nhất là (2+4+7) TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.5 Thuật toán Prim Ví dụ 1: Lấy đỉnh xuất phát là A. B. Tập F Giải thích 1 (A,C) đầu tiên cạnh (A,C) được chọn vì có trọng số nhỏ nhất khi xét tập hợp các cạnh liên thuộc đỉnh A gồm: (A,C) và (A,B) 2 (C,D),(A,C) cạnh (C,D)-cạnh tiếp theo được chọn vì có trọng số nhỏ nhất khi xét tập hợp các cạnh liên thuộc với A, C gồm: (A,B), (C,B), (C,D) 3 (C,D),(A,C) Loại (A,D) vì tạo chu trình cạnh (A,D) không được chọn vì tạo chu trình với 2 cạnh (C,D) và (A,C) đã chọn 4 (C,D),(A,C) cạnh (B,C) là cạnh tiếp theo được chọn vì có trọng số nhỏ nhất (xét dãy các cạnh liên thuộc đỉnh A,C và D) và không tạo chu trình 5 (B,C),(C,D),(A,C) Do số cạnh là 3 = n-1 nên kết thúc việc xét TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.5 Thuật toán Prim Ví dụ 1: Lấy đỉnh xuất phát là B. Bảng thực hiện như sau: B. Tập F A B C D 1 (B,C) 2,5,9 7*,8,9 2,4,7* 4,5,8 2 (C,A), (B,C) 2*,5,9 8,9 2*,4 4,5,8 3 (C,A),(B,C) 5,9 8,9 4* 4*,5,8 4 (C,D), (C,A),(B,C) 5,9 8,9 5,8 KQ: độ dài cây khung ngắn nhất là (7+2+4) TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2. Cây khung đồ thị 2.5 Thuật toán Prim Ví dụ 2: Tìm cây khung ngắn nhất của đồ thị G dưới đây. Sử dụng thuật toán Prim. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 2.5 Thuật toán Prim Ví dụ 3: Tìm cây khung ngắn nhất của đồ thị G trong hình bên. Sử dụng thuật toán Prim. 2. Cây khung đồ thị 12 10 9 9 5 4 9 9 9 9 6 4 A B D C E F G H K Z 2 2 8 4 1 3 3 8 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.1 Giới thiệu Trên một cây khung ngắn nhất của đồ thị G, chúng ta xác định một đỉnh gọi là gốc. - Từ gốc chúng ta vẽ được các đường đi có hướng đi đến các đỉnh khác của cây khung, và tạo ra cây gọi là cây phân cấp. Quan hệ giữa các đỉnh là "cha-con". 5 C A 6 D 7 8 7 4 2 3 G 8 B 2 E G B C A D E TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.1 Giới thiệu Từ cây khung ngắn nhất của đồ thị G, chúng ta vẽ được cây T1 có gốc là C; cây T2 có gốc là E. B C A D E G E B D CG A E C A GDB T1 T2 TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.1 Giới thiệu Một số ứng dụng thực tế sử dụng cây để vẽ mô hình: 1- sơ đồ tổ chức 2- cây thư mục trong hệ điều hành 3- cây tên miền Internet TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.1 Giới thiệu sơ đồ tổ chức công ty máy tính TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3.1 Giới thiệu 3. Cây phân cấp Hệ thống thư mục-tệp tin TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3.1 Giới thiệu 3. Cây phân cấp Cây hệ thống tên miền Internet - DNS TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.2 Định nghĩa Với T là cây có gốc. - Có 1 đỉnh là gốc. - Nếu v là một đỉnh khác gốc của T, khi đó "cha" của v là đỉnh u sao cho có một cạnh từ u đến v. - Các đỉnh của cây gọi là "lá" nếu chúng không có "con". - Cây với n đỉnh có đúng (n-1) cạnh J Z A DRB LFAKQ "lá" đỉnh A là "cha" của đỉnh D gốc TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.2 Định nghĩa - Các đỉnh có "con" được gọi là đỉnh trong của cây T. Lá được gọi là đỉnh ngoài. - Nếu v là một đỉnh của cây T thì đỉnh v và các con cháu tạo thành cây con của cây T - có gốc là v. E C A DB G Cây con của T - có gốc là đỉnh C - đỉnh C, E là "đỉnh trong" của cây, - đỉnh B, D, G là "đỉnh ngoài" TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.2 Định nghĩa - Cây T được gọi là cây k-phân nếu mỗi đỉnh trong của T có nhiều nhất là k con. E C A G D G B cây nhị phân E C A H D B G cây tam phân TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.2 Định nghĩa - Cây T được gọi là cây k-phân đầy đủ nếu mọi đỉnh trong của T có đúng k con. T1 cây nhị phân đầy đủ T2 cây ngũ phân đầy đủ T3 cây tam phân không đầy đủ TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.2 Định nghĩa - Cây nhị phân là cây mà mỗi đỉnh trong của cây có tối đa là hai con. - Cây nhị phân được sắp thứ tự trái-phải cho các cây con để thực hiện việc duyệt (hay còn gọi là "thăm viếng") các đỉnh. B A JI D F G H C E Cây con trái Cây con phải TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.3 Duyệt cây nhị phân - Có ba kiểu duyệt cây thường được sử dụng để duyệt cây nhị phân: Duyệt theo kiểu tiền thứ tự (Pre-order) Node - Left - Right Duyệt theo kiểu trung thứ tự (In-order) Left - Node - Right Duyệt theo kiểu hậu thứ tự (Post-order) Left - Right - Node TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.3 Duyệt cây nhị phân Duyệt theo kiểu tiền thứ tự Node - Left - Right Cách thực hiện: - Trước tiên thăm gốc (node) - Duyệt cây con bên trái theo kiểu tiền thứ tự - Duyệt cây con bên phải theo kiểu tiền thứ tự. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.3 Duyệt cây nhị phân Duyệt theo kiểu trung thứ tự Left - Node - Right Cách thực hiện: - Duyệt cây con bên trái theo kiểu trung thứ tự - Thăm gốc (node) - Duyệt cây con bên phải theo kiểu trung thứ tự. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.3 Duyệt cây nhị phân Duyệt theo kiểu hậu thứ tự Left - Right - Node Cách thực hiện: - Duyệt cây con bên trái theo kiểu hậu thứ tự - Duyệt cây con bên phải theo kiểu hậu thứ tự - Thăm gốc (node). TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.3 Duyệt cây nhị phân Hình minh họa cho ba kiểu duyệt cây (Pre-order) (In-order) (Post-order) TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.4 Một số ứng dụng của cây Ứng dụng 1: Trong tổ chức cây thư mục của hệ điều hành, để tính dung lượng của thư mục, chúng ta duyệt cây theo kiểu hậu thứ tự. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.4 Một số ứng dụng của cây Ứng dụng 2: Biểu diễn biểu thức số học theo dạng cây để lập chương trình tính biểu thức. - Năm 1920, nhà toán học Ba lan, Jan Łukasiewic, đề xuất dùng cây để biểu diễn và tính toán biểu thức số học trong lập trình máy tính. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.4 Một số ứng dụng của cây Ứng dụng 2: Ví dụ: Biểu thức số học dưới đây được biểu diễn theo dạng cây B1=(a+b) * (c - d/2) B2=(a+b*c) - d/2 + * 2 b ca - d / + - 2 b da / c * TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.4 Một số ứng dụng của cây Ứng dụng 2: Ví dụ: (tt) Thực hiện việc duyệt cây B1 và cây B2 theo kiểu trung thứ tự chúng ta có cùng 1 kết quả như sau: a + b * c - d /2 + * 2 b ca - d / + - 2 b da / c * TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.4 Một số ứng dụng của cây Ứng dụng 2: Ví dụ: (tt) Thực hiện việc duyệt cây B1 và cây B2 theo kiểu tiền thứ tự chúng ta có 2 kết quả khác nhau: B1: * + a b - c / d 2 B2: - + a * b c / d 2 + * 2 b ca - d / + - 2 b da / c * TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.4 Một số ứng dụng của cây Ứng dụng 2: Ví dụ: (tt) Thực hiện việc duyệt cây B1 và cây B2 theo kiểu hậu thứ tự chúng ta có 2 kết quả khác nhau: B1: a b + c d 2 / - * B2: a b c * + d 2 / - + * 2 b ca - d / + - 2 b da / c * TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: CÂY VÀ CÁC ỨNG DỤNG 3. Cây phân cấp 3.4 Một số ứng dụng của cây Ứng dụng 2: - Việc biểu diễn biểu thức số học theo dạng tiền thứ tự (hoặc hậu thứ tự) cho phép bỏ dấu ngoặc đơn trong cách biểu diễn biểu thức số học, vẫn đảm bảo tính đúng của kết quả tính toán. - Chúng ta gọi cách viết biểu thức theo kiểu tiền thứ tự là KÝ PHÁP BA LAN. - Chúng ta gọi cách viết biểu thức theo kiểu hậu thứ tự là KÝ PHÁP BA LAN NGƯỢC.