›
›

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

pdf 50 trang hapham 1510
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Toán ứng dụng - Bài 5: Cây và các ứng dụng", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfbai_giang_toan_ung_dung_bai_5_cay_va_cac_ung_dung.pdf

Nội dung text: Bài giảng Toán ứng dụng - Bài 5: Cây và các ứng dụng

  1. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 CÂY VÀ CÁC ỨNG DỤNG
  2. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 CÂY VÀ CÁC ỨNG DỤNG
  3. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Cây và các tính chất cơ bản 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. isobutan Arthur Cayley (1821-1895) CÂY VÀ CÁC ỨNG DỤNG
  4. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Cây và các tính chất cơ bản 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; CÂY VÀ CÁC ỨNG DỤNG
  5. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 CÂY VÀ CÁC ỨNG DỤNG
  6. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 1. Cây và các tính chất cơ bản 1.2 Định nghĩa Ví dụ: a b a b a b a b c c c c d d d d e f e f e f e f G1 G2 G3 G4 G1, G2 là cây; G3, G4 không phải là cây CÂY VÀ CÁC ỨNG DỤNG
  7. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 A F D G C E H CÂY VÀ CÁC ỨNG DỤNG
  8. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 A F G B CÂY VÀ CÁC ỨNG DỤNG
  9. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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ị. CÂY VÀ CÁC ỨNG DỤNG
  10. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 A F D G C E H CÂY VÀ CÁC ỨNG DỤNG
  11. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 A F D G C E H CÂY VÀ CÁC ỨNG DỤNG
  12. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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. B A F E D 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ố? CÂY VÀ CÁC ỨNG DỤNG
  13. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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ị. CÂY VÀ CÁC ỨNG DỤNG
  14. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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. CÂY VÀ CÁC ỨNG DỤNG
  15. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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) CÂY VÀ CÁC ỨNG DỤNG
  16. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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)}. CÂY VÀ CÁC ỨNG DỤNG
  17. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 CÂY VÀ CÁC ỨNG DỤNG
  18. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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. 8 18 9 17 4 CÂY VÀ CÁC ỨNG DỤNG
  19. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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. CÂY VÀ CÁC ỨNG DỤNG
  20. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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ị. CÂY VÀ CÁC ỨNG DỤNG
  21. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 CÂY VÀ CÁC ỨNG DỤNG
  22. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: Cơ sở Logic 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. 9 B 8 9 7 A 5 2 8 7 5 2 C D 4 4 CÂY VÀ CÁC ỨNG DỤNG
  23. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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) 5,9 7,8,9 7 5,8 Loại (A,D) vì tạo chu trình 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) CÂY VÀ CÁC ỨNG DỤNG
  24. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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) cạnh (A,D) không được chọn vì tạo chu trình Loại (A,D) 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 CÂY VÀ CÁC ỨNG DỤNG
  25. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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) CÂY VÀ CÁC ỨNG DỤNG
  26. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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. CÂY VÀ CÁC ỨNG DỤNG
  27. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 2. Cây khung đồ thị 2.5 Thuật toán Prim H 4 Ví dụ 3: G 1 4 Tìm cây khung ngắn nhất 5 K 3 9 Z của đồ thị G B 9 9 10 trong 2 E hình bên. 6 8 4 2 F Sử dụng thuật 12 D 9 3 toán Prim. A 9 8 9 C CÂY VÀ CÁC ỨNG DỤNG
  28. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 B D B D 8 8 7 6 A 2 G A G 3 7 2 C E C E 4 CÂY VÀ CÁC ỨNG DỤNG
  29. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 D A G C E T1 T2 C E E A B D G C B G D A CÂY VÀ CÁC ỨNG DỤNG
  30. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 CÂY VÀ CÁC ỨNG DỤNG
  31. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Cây phân cấp 3.1 Giới thiệu sơ đồ tổ chức công ty máy tính CÂY VÀ CÁC ỨNG DỤNG
  32. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Cây phân cấp 3.1 Giới thiệu Hệ thống thư mục-tệp tin CÂY VÀ CÁC ỨNG DỤNG
  33. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Cây phân cấp 3.1 Giới thiệu Cây hệ thống tên miền Internet - DNS CÂY VÀ CÁC ỨNG DỤNG
  34. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 J gốc gốc của T, khi đó "cha" đỉnh A là của v là đỉnh u sao cho có "cha" của Z A một cạnh từ u đến v. đỉnh D - Các đỉnh của cây gọi là B R D "lá" nếu chúng không có "con". - Cây với n đỉnh Q K A F L "lá" có đúng (n-1) cạnh CÂY VÀ CÁC ỨNG DỤNG
  35. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 3. Cây phân cấp 3.2 Định nghĩa - đỉnh C, E là - Các đỉnh có "con" được gọi là "đỉnh trong" đỉnh trong của cây T. Lá được của cây, gọi là đỉnh ngoài. - đỉnh B, D, G là A "đỉ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. C E Cây con của T - có gốc là đỉnh C G B D CÂY VÀ CÁC ỨNG DỤNG
  36. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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. A A C C E D G H E B D B G G cây nhị phân cây tam phân CÂY VÀ CÁC ỨNG DỤNG
  37. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 T2 T3 cây nhị phân cây ngũ phân cây tam phân đầy đủ đầy đủ không đầy đủ CÂY VÀ CÁC ỨNG DỤNG
  38. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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. A Cây con B C phải Cây con trái D E F G H I J CÂY VÀ CÁC ỨNG DỤNG
  39. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 CÂY VÀ CÁC ỨNG DỤNG
  40. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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ự. CÂY VÀ CÁC ỨNG DỤNG
  41. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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ự. CÂY VÀ CÁC ỨNG DỤNG
  42. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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). CÂY VÀ CÁC ỨNG DỤNG
  43. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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) CÂY VÀ CÁC ỨNG DỤNG
  44. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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ự. CÂY VÀ CÁC ỨNG DỤNG
  45. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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. CÂY VÀ CÁC ỨNG DỤNG
  46. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 - * + - + / a d 2 a b c / * d 2 b c CÂY VÀ CÁC ỨNG DỤNG
  47. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 * - + - + / a b c / a * d 2 d 2 b c CÂY VÀ CÁC ỨNG DỤNG
  48. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 * - + - + / a b c / a * d 2 d 2 b c CÂY VÀ CÁC ỨNG DỤNG
  49. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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 / - * - + - + / a b c / a * d 2 d 2 b c CÂY VÀ CÁC ỨNG DỤNG
  50. TRƯỜNG CAO ĐẲNG NGHỀ CNTT iSPACE Website: 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. CÂY VÀ CÁC ỨNG DỤNG