›
›

Bài giảng Lý thuyết đồ thị - Chương 5: Cây

pdf 58 trang phuongnguyen 2521
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Lý thuyết đồ thị - Chương 5: Cây", để 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_ly_thuyet_do_thi_chuong_5_cay.pdf

Nội dung text: Bài giảng Lý thuyết đồ thị - Chương 5: Cây

  1. Môn học: Lý thuyết đồ thị Chương 5: Cây Trường ĐHSPKT TP. HCM Khoa Công nghệ Thông tin Email: levinhcntt@yahoo.com
  2. Nội dung I. Định nghĩa II. Cây khung của đồ thị III. Tập các chu trình cơ bản IV. Cây khung nhỏ nhất V. Cây có gốc Chương 5 - Cây 2 Lý thuyết đồ thị
  3. I. Định nghĩa ™Cây là đồ thị vô hướng ƒ Liên thông ƒ Không có chu trình ™Rừng là đồ thị vô hướng ƒ Không có chu trình Chương 5 - Cây 3
  4. I. Định nghĩa ™Định lý nhận biết cây Cho T =(V, E) là đồ thị vô hướng n đỉnh. Các mệnh đề sau đây là tương đương: ƒ MĐ1: T là cây ( T liên thông và không chứa chu trình ). ƒ MĐ2: T không chứa chu trình và có n-1 cạnh. ƒ MĐ3: T liên thông và có n-1 cạnh. ƒ MĐ4: T liên thông và mỗi cạnh của nó đều là cầu. ƒ MĐ5: Hai đỉnh bất kỳ của T được nối với nhau bởi đúng 1 đường đi đơn. ƒ MĐ6: T không chứa chu trình nhưng hễ cứ thêm vào nó một cạnh ta thu được đúng 1 chu trình. Chương 5 - Cây 4
  5. I. Định nghĩa ™Định lý nhận biết cây ™Chứng minh: Ta sẽ chứng minh định lý trên theo sơ đồ sau: ƒ MĐ1 ⇒ MĐ2 ⇒ MĐ3 ⇒ MĐ4 ⇒ MĐ5 ⇒ MĐ6 ⇒ MĐ1 Chương 5 - Cây 5
  6. I. Định nghĩa ™ Chứng minh MĐ1 ⇒ MĐ2: Nếu T là cây n đỉnh thì T không có chu trình và có n-1 cạnh Chứng minh bằng phương pháp quy nạp ƒ Với n=1 thì đồ thị có n-1 = 1 – 1 = 0 (Đúng) ƒ Giả sử khẳng định đúng ∀ cây có k ≥1 đỉnh. Ta sẽ chỉ ra ∀ cây T có k+1 ≥1 đỉnh sẽ có số cạnh là k. Chọn đường đi dài nhất trong G là P = (v1 ,v2 , ,vm).Rõ ràng v1 là đỉnh treo : • v1 không thể kề với các đỉnh v3, ,vm vì G không có chu trình. • v1 không thể được nối với các đỉnh khác vì P là dài nhất Xét G’ = G \ { v1, (v1 ,v2) } (Không thể bỏ các đỉnh trung gian). Ta được G’ có k đỉnh. Theo giả thiết quy nạp G’ có k-1 cạnh. Do đóG cók cạnh (ĐPCM) Chương 5 - Cây 6
  7. I. Định nghĩa ™ Chứng minh MĐ2 ⇒ MĐ3: Nếu T không chứa chu trình và có n-1 cạnh thì T liên thông. Chứng minh bằng phương pháp phản chứng. ƒ Giả sử T không liên thông, khi đó T được phân rã thành k>1 thành phần liên thông T1, T2, , Tk .Vì T không chứa chu trình (theo giả thiết) nên các cây cũng vậy, suy ra Ti là cây. ƒ Gọi v(T) và e(T) tương ứng là số đỉnh và cạnh của T. Theo phần trước MĐ1 ⇒ MĐ2 ta có: e(Ti) = v(Ti) – 1. Suy ra: • ∑ e(Ti) = ∑ (v(Ti) -1) = ∑ v(Ti) – k Ùe(T) = v(T) – k Ùn - 1 = n - k . Vô lý với k>1 (ĐPCM) Chương 5 - Cây 7
  8. I. Định nghĩa ™ Chứng minh MĐ3 ⇒ MĐ4:Nếu T liên thông và có n-1 cạnh thì mỗi cạnh của T là cầu ƒ Suy luận tương tự như chứng minh MĐ1 ⇒ MĐ2. ƒ Chọn đường đi dài nhất P = (v1, v2, v3, ,vm). ƒ Nếu từ đồ thị T ta bỏ đi một cạnh nào đó trên đường đi P, thì rõ ràng không còn con đường nào khác để đi từ v1 đến vm (vì nếu ngược lại thì T có chu trình). Vì vậy các cạnh của T đều là cầu. Chương 5 - Cây 8
  9. I. Định nghĩa ™ Chứng minh MĐ4 ⇒ MĐ5:Nếu T liên thông và mỗi cạnh của T là cầu thì hai đỉnh bất kỳ của T được nối với nhau đúng bởi 1 đường đơn. ƒ T liên thông nên mọi 2 đỉnh của T tồn tại đường nối giữa chúng. Đường nối này là duy nhất vì trái lại T sẽ có chu trình và các cạnh trên chu trình đósẽ không thể là cầu.(ĐPCM) Chương 5 - Cây 9
  10. I. Định nghĩa ™ Chứng minh MĐ5 ⇒ MĐ6:Nếu hai đỉnh bất kỳ của T được nối với nhau đúng bởi 1 đường đơn thì T không chứa chu trình nhưng hễ cứ thêm vào nó 1 cạnh ta thu được đúng 1 chu trình ƒ T không chứa chu trình vì nếu T có chu trình thì sẽ có cặp đỉnh được nối với nhau bởi 2 đường đơn. ƒ Thêm vào cạnh (u,v) ta sẽ nhận được chu trình gồm đường đơn nối u với v và cạnh (u,v) mới. ƒ Do đường đơn nói trên là duy nhất nên chu trình nhận được cũng là duy nhất. ƒ (ĐPCM) Chương 5 - Cây 10
  11. I. Định nghĩa ™ Chứng minh MĐ6 ⇒ MĐ1:T không chứa chu trình nhưng hễ cứ thêm vào nó một cạnh ta thu được đúng 1 chu trình thì T là cây (liên thông và không có chu trình). ƒ Chứng minh bằng phản chứng Chương 5 - Cây 11
  12. Nội dung I. Định nghĩa II. Cây khung của đồ thị III. Tập các chu trình cơ bản IV. Cây khung nhỏ nhất V. Cây có gốc Chương 5 - Cây 12 Lý thuyết đồ thị
  13. II.1. Định nghĩa ƒ Cho đồ thị G =(V, E) vô hướng, liên thông. Một cây T=(V,F) được xây dựng từ G với F ⊂ E (Tchứa tất cả các đỉnh của G và tập cạnh F là con của tập cạnh E) được gọi là cây khung của đồ thị G. ƒ Cây bao trùm hay cây tối đại. Chương 5 - Cây 13
  14. II.2. Định lý Cayley n-2 ƒ Số cây khung của đồ thị Kn là n abc, bcd, cda, dab, afc, dfb, aec, deb, aed, afb, bec, cfd, efc, efd, efa, efb. Số cây khung là: 42 = 16 Chương 5 - Cây 14
  15. II.3. Xây dựng cây khung ƒ Xây dựng theo chiều sâu ƒ Xây dựng theo chiều rộng Tham số • Input: Đồ thị G lưu dưới dạng danh sác kề -Mảng Ke[] • Output: Cây khung T của đồ thị Mảng ChuaXet[] dùng để đánh đấu các đỉnh đã được xét hay chưa. Chương 5 - Cây 15
  16. II.3.a. X/d theo chiều sâu /* Khai báo các biến toàn cục ChuaXet, Ke, T */ void Tree_DFS(v); { ChuaXet[v] = 0; for (u ∈ Ke(v)) if (ChuaXet[u]) { T = T ∪ (v,u); Tree_DFS(u); }; } main(){ /* Nhập đồ thị, tạo biến Ke */ for (v ∈ V) ChuaXet[v] = 1; /* Khởi tạo cờ cho đỉnh */ T = ∅; /* T là tập cạnh cây khung */ Tree_DFS(root); /* root là đỉnh nào đócủa đồ thị */ } Chương 5 - Cây 16
  17. II.3.a. X/d theo chiều sâu ™ Ví dụ Đỉnh v Ke(v) 12, 3 24, 1 3 1, 6, 5, 4 4 2, 3, 7, 8 56, 3 63, 5 74,8 8 7, 4, 10, 9 98, 10 10 8, 9 1Æ 2 Æ 4 Æ 3 Æ 6 Æ 5 7 Æ 8 Æ 10 Æ 9 Cây khung của G là: {(1, 2), (2, 4), (4, 3), (3, 6), (6, 5), (4, 7), (7, 8), (8, 10), (10, 9)} Chương 5 - Cây 17
  18. II.3.b. X/d theo chiều rộng /* Khai báo các biến toàn cục ChuaXet, Ke, QUEUE */ void Tree_BFS(r);{ QUEUE = ∅; QUEUE ⇐ r; ChuaXet[r] = 0; while (QUEUE != ∅ ){ v ⇐ QUEUE; for (u ∈ Ke(v)) if ( ChuaXet[u] ){ QUEUE ⇐ u; ChuaXet[u] = 0; T = T ∪ (v,u); }; } } main() /* Nhập đồ thị, tạo biến Ke */{ for (v ∈ V) ChuaXet[v] = 1; /* Khởi tạo cờ cho đỉnh */ T = ∅; /* T là tập cạnh cây khung */ Tree_DFS(root); /* root là đỉnh nào đócủa đồ thị */ } Chương 5 - Cây 18
  19. II.3.b. X/d theo chiều rộng ™ Ví dụ Đỉnh v Ke(v) 12, 3 24, 1 3 1, 6, 5, 4 4 2, 3, 7, 8 56, 3 63, 5 74,8 8 7, 4, 10, 9 98, 10 1 Æ 2 Æ 3 10 8, 9 4 Æ 6 Æ 5 7 Æ 8 10 Æ 9 Cây khung của G là: {(1, 2), (2, 3), (2, 4), (4, 6), (6, 5), (4, 7), (7, 8), (8, 10), (10, 9)} Chương 5 - Cây 19
  20. Nội dung I. Định nghĩa II. Cây khung của đồ thị III. Tập các chu trình cơ bản IV. Cây khung nhỏ nhất V. Cây có gốc Chương 5 - Cây 20 Lý thuyết đồ thị
  21. III.Tập các chu trình cơ bản ™ Định nghĩa ƒ Giả sử G=(V,E) là đơn đồ thị vô hướng liên thông, H=(V,T) là cây khung của G. ƒ Nếu thêm một cạnh e ∈ E\T vào cây khung H ta sẽ thu được đúng 1 chu trình trong H, ký hiệu nó là Ce. Tập các chu trình: ƒ Ω = { Ce : e ∈ E\T } được gọi là tập các chu trình cơ bản của đồ thị G. Chương 5 - Cây 21
  22. III.Tập các chu trình cơ bản ™ Tính chất ƒ Tập các chu trình cơ bản phụ thuộc vào cây khung của đồ thị. Hai cây khung khác nhau có thể cho hai tập chu trình cơ sở khác nhau. ƒ Nếu một đồ thị liên thông có n đỉnh, m cạnh. Khi đó cây khung có n-1 cạnh, còn lại m-n+1 cạnh ngoài. Tương ứng với mỗi cạnh ngoài, ta có một chu trình cơ bản. Vì vậy, số chu trình cơ bản của một đồ thị liên thông là m-n+1. ƒ Tập các chu trình cơ bản là một tập nhiều nhất các chu trình thỏa mãn điều kiện: Mỗi chu trình có đúng một cạnh riêng, cạnh đó không nằm trong các chu trình còn lại và việc loại bỏ cạnh này không ảnh hưởng đến tính liên thông của đồ thị và không ảnh hưởng đến các chu trình còn lại. Như vậy ta có thể bỏ tối đa m - n+1 cạnh mà vẫn đảm bảo tính liên thông của đồ thị. Chương 5 - Cây 22
  23. III.Tập các chu trình cơ bản ™ Ý nghĩa ƒ Các bài toán về mạch điện ƒ Mỗi mạch vòng tương ứng với một chu trình cơ bản. ƒ Tổng hiệu điện thế dọc theo một mạch vòng bằng 0. (ĐL Kirchoff) ƒ Lập hệ PT tuyến tính Î Tính toán hiệu điện thế trên mọi đường dây của mạng điện. Chương 5 - Cây 23
  24. III.Tập các chu trình cơ bản ™ Thuật toán /* Khai báo các biến toàn cục d, num, STACK, Index, Ke */ void Cycle(int v);{ d ++; STACK[d] = v; num ++; Index[v] = num; for (u ∈ Ke(v)) if (Index[u] ==0 ) Cycle(u); else if (( u != STACK[d-1] ) && ( Index[v] > Index[u] ) ) Ghi nhận chu trình STACK[d], , STACK[c], với STACK[c] =u; d ; } main(){ for (v ∈ V) Index[v] = 0; /* Khởi tạo cờ cho đỉnh */ num = 0; d = 0; STACK[0] = 0; for (v ∈ V) if (Index[v] == 0) Cycle(v); } Chương 5 - Cây 24
  25. III.Tập các chu trình cơ bản ™ Ví dụ Đỉnh v Ke(v) 1 2, 7, 3 26, 1 3 5, 4, 1 43, 5 53, 4 6 8, 9, 7, 2 7 6, 9, 1 86 97, 6 Chương 5 - Cây 25
  26. III.Tập các chu trình cơ bản Chương 5 - Cây 26
  27. Nội dung I. Định nghĩa II. Cây khung của đồ thị III. Tập các chu trình cơ bản IV. Cây khung nhỏ nhất V. Cây có gốc Chương 5 - Cây 27 Lý thuyết đồ thị
  28. IV. Cây khung nhỏ nhất Cây khung nhỏ nhất 1. Khái niệm 2. Thuật toán Kruskal 3. Thuật toán Prim Chương 5 - Cây 28
  29. IV.1. Khái niệm ƒ Cho G = (V, E) là đồ thị vô hướng liên thông. ƒ Mỗi cạnh e của đồ thị được gán với một số không âm w(e) gọi là độ dài (Trọng số) của nó. ƒ Giả sử T = (V, F) là cây khung của G ƒ Trọng số của cây khung T: w(T) = ∑ w(e) e∈F ƒ Bài toán: Tìm T sao cho w(T) nhỏ nhất Chương 5 - Cây 29
  30. IV.1. Khái niệm ™Ứng dụng ƒ Bài toán xây dựng hệ thống đường sắt ƒ Bài toán nối mạng máy tính Chương 5 - Cây 30
  31. IV.2. Thuật toán Kruskal ƒ Đồ thị G=(V, E), Xây dựng tập cạnh F của T=(V, F) theo từng bước: 1. Sắp xếp các cạnh của G theo thứ tự trọng số (độ dài) tăng dần 2. Bắt đầu với F= Ø bổ xung dần các cạnh của G vào F với điều kiện không tạo nên chu trình trong T. 3. Thuật toán dừng lại khi có n-1 cạnh được chọn. Chương 5 - Cây 31
  32. IV.2. Thuật toán Kruskal ™ Ví dụ (d, e) (a, f) (b, f) (c, d) (c, e) (a, b) (f, e) (b, c) 13457122024 (d, e) (a, f) (b, f) (c, d) (f, e) 134520 Chương 5 - Cây 32
  33. IV.2. Thuật toán Kruskal Void Kruskal; { F = ∅; while ( ( |F| < n-1 ) && ( E != ∅ ) ) { Chọn e = min ∈ E; E = E \ {e}; if ( F ∪ {e} không chứa chu trình ) F = F ∪ {e}; } if ( |F| < n-1 ) cout << “Đồ thị không liên thông”; } Chương 5 - Cây 33
  34. IV.3. Thuật toán Prim Cho đồ thị G=(V, E), Xây dựng tập đỉnh VT và tập cạnh F của cây khung T=(VT , F) theo từng bước: 1. Bắt đầu với VT = s, một đỉnh bất kỳ và T=∅. Trong tất cả các cạnh có 1 đỉnh ∉ VT và 1 đỉnh ∈ VT chọn cạnh có trọng số nhỏ nhất. 2. Bổ sung cạnh đó vào F và đỉnh tương ứng vào VT . 3. Thuật toán dừng lại khi có n-1 cạnh được chọn (hoặc VT=V ) . Chương 5 - Cây 34
  35. IV.3. Thuật toán Prim (a, f) (e, f) (d, e) (c, f) (a, b) 321412 Chương 5 - Cây 35
  36. IV.3. Thuật toán Prim ™Cài đặt void Prim() { F = ∅; VT = u; while ( |F| < n-1 ) { Chọn e = { min w(u,v) (u∈ VT ) & (v∉ VT ) }; F = F ∪ {e}; VT = VT ∪ {v}; } } Chương 5 - Cây 36
  37. IV. Cây khung nhỏ nhất ƒ Chứng minh tính đúng đắn và nhận xét hai thuật toán Kruskal và Prim ? Chương 5 - Cây 37
  38. Nội dung I. Định nghĩa II. Cây khung của đồ thị III. Tập các chu trình cơ bản IV. Cây khung nhỏ nhất V. Cây có gốc Chương 5 - Cây 38 Lý thuyết đồ thị
  39. V. Cây có gốc Cây có gốc 1. Các khái niệm 2. Cây tìm kiếm nhị phân 3. Cây quyết định 4. Các phương pháp duyệt cây Chương 5 - Cây 39
  40. V.1. Các khái niệm ƒ T là một cây có gốc ƒ x, y, z là các đỉnh trong T ƒ v0, v1, , vn là một đường đi đơn trong T ƒ Vn-1 là cha (parent) của vn ƒ v0 ,v1 , ,vn-1 là các tiền bối ( ancestor) của vn ƒ vn là con (child) của vn-1 ƒ Nếu x là tiền bối của y thì y là hậu duệ (descendant) của x ƒ Nếu y, z là con của x thì y và z là anh em (siblings) Chương 5 - Cây 40
  41. V.1. Các khái niệm ƒ Nếu x không có con thì x là lá (leaf) ƒ Nếu x không là lá thì x là đỉnh trong (branch vertex) ƒ Mức (level) của đỉnh x là chiều dài (số cành) của đường đơn từ gốc v0 tới x. level(v0) = 0 ƒ Chiều cao (height) của một cây là mức lớn nhất trong cây ƒ Cây con (subtree) của T gốc tại x là đồ thị con của T mà • Tập đỉnh gồm x và tất cả các hậu duệ của x • Tập các cành gồm mọi cành nối tới các hậu duệ của x Chương 5 - Cây 41
  42. V.1. Các khái niệm ƒ Cha của c là b ƒ Các lá : d, e, f, l, m, i, n, o ƒ Con của g là h, i, j ƒ Mức của c là 2, của k là 3 ƒ Các tiền bối của e là c, b, a ƒ Chiều cao của cây là 4 ƒ Các hậu duệ của b là c, d, e ƒ Cây con gốc g. ƒ Các đỉnh trong : a, b, c, g, h, j, k Chương 5 - Cây 42
  43. V.1. Các khái niệm Một cây có gốc gọi là: ƒ m – cây (m-ary tree) nếu mỗi đỉnh trong không có quá m con ƒ m – cây đầy (full m-ary tree) nếu mỗi đỉnh trong có đúng m con ƒ Cây nhị phân (binary tree) nếu mỗi đỉnh không có quá 2 con ƒ Cây có gốc thứ tự (Ordered rooted tree) nếu các con của mỗi đỉnh trong được xếp thứ tự từ trái qua phải Chương 5 - Cây 43
  44. V.1. Các khái niệm ƒ Đặc biệt: Cây nhị phân có thứ tự: Nếu một đỉnh trong có đủ 2 con thì • Con thứ nhất là con bên trái ( left child) • Con thứ 2 là con bên phải ( right child) ƒ Một m – cây với chiều cao h gọi là thăng bằng ( balanced) nếu tất cả các lá đều ở mức h hay h-1. Chương 5 - Cây 44
  45. V.1. Các khái niệm ™ Một số ví dụ ƒ Mô hình gia phả một dòng họ ƒ Mô hình biểu diễn của các tổ chức • Ví dụ: Mô hình tổ chức Trường Đại Học Chương 5 - Cây 45
  46. V.1. Các khái niệm ™ Một số ví dụ ƒ Mô hình các tập tin trong máy tính • Các tập tin trong máy tính được tổ chức thành các thư mục, các thư mục được tổ chức dưới dạng cây, trong đó thư mục gốc là gốc của cây Chương 5 - Cây 46
  47. V.2. Cây tìm kiếm nhị phân ™Một cây tìm kiếm nhị phân là một cây nhị phân T mà trong đó: ƒ Mỗi đỉnh được gán cho một nhãn ƒ Các nhãn có thể so sánh được với nhau ƒ ∀ đỉnh v∈T, các nhãn trong cây con bên trái của v đều nhỏ hơn nhãn của v và các nhãn trong cây con bên phải của v đều lớn hơn nhãn của v Chương 5 - Cây 47
  48. V.2. Cây tìm kiếm nhị phân ™Ví dụ:: 30, 20, 10, 40, 32, 27, 17, 8, 42, 78, 35. Chương 5 - Cây 48
  49. V.2. Cây tìm kiếm nhị phân ™Thuật toán tìm kiếm trên cây tìm kiếm nhị phân ƒ Giả sử ta có một cây tìm kiếm, x là một giá trị nào đó ƒ Xác định vị trí của biến x nếu x là nhãn của một đỉnh v ƒ Nếu thấy rằng x không là nhãn của một đỉnh nào cả thì tạo ra một đỉnh mới và gán nhãn x cho đỉnh đó ƒ Độ phức tạp thuật toán: O(log n) Chương 5 - Cây 49
  50. V.2. Cây tìm kiếm nhị phân ™ Thuật toán tìm kiếm trên cây tìm kiếm nhị phân void TK( Cây NPTK T, phần tử x); { v = gốc của T; if (v == NULL ) thêm đỉnh r vào cây và gán cho nó nhãn là x while ((v != NULL) && (label(v) != x) ) { if (x == label(v)) cout label(v)) if (con bên phải v != NULL) v = con bên phải v; else thêm đỉnh nhãn x là con bên phải v và đặt v:=NULL; } } Chương 5 - Cây 50
  51. V.3. Cây quyết định ™ Thuật toán tìm kiếm trên cây tìm kiếm nhị phân ƒ Cây quyết định là cây có gốc mà: • Mỗi đỉnh tương ứng với 1 quyết định • Mỗi cây con tại các đỉnh này ứng với mỗi kết cục có thể của của quyết định ƒ Một lời giải là một đường đi từ gốc đến lá ƒ Ví dụ: Cho 8 đồng xu, trong đócómột đồng nhẹ hơn. Xác định nó bằng 1 cái cân thăng bằng. Chương 5 - Cây 51
  52. V.3. Cây quyết định ƒ Có 3 trạng thái sau mỗi lần cân. Do đó cây quyết định cho một dãy các lần cân là cây tam phân ƒ Có ít nhất 8 lá trong cây quyết định vì có 8 kết cục có thể và mỗi kết cục cần biểu diễn bằng ít nhất 1 lá ƒ Số lần cân nhiều nhất để xác định đồng xu giả là chiều cao của cây h ƒ Ta có h ≥⎡log38⎤ = 2 (làm tròn tăng) Chương 5 - Cây 52
  53. V.3. Cây quyết định Chương 5 - Cây 53
  54. V.4. Các phương pháp duyệt cây ™ Thuật toán viếng thăm mọi đỉnh của một cây có gốc có thứ tự đúng 1 lần một cách có hệ thống gọi là thuật toán duyệt cây ™ Có 3 thuật toán phổ thông: ƒ Duyệt tiền tự (Preoder traversal) ƒ Duyệt trung tự (Inorder traversal) ƒ Duyệt hậu tự (Postorder traversal) Chương 5 - Cây 54
  55. V.4. Các phương pháp duyệt cây ™ Thuật toán duyệt tiền tự void Preorder( cây thứ tự có gốc T); { r = gốc của T; Thăm r; for ( Mỗi cây con c của r từ trái sang phải ) { T(c) = Cây con với gốc c Preorder( T(c) ) } } Chương 5 - Cây 55
  56. V.4. Các phương pháp duyệt cây ™ Thuật toán duyệt trung tự void Inorder( cây thứ tự có gốc T) { r := gốc của T if (r là lá) Thăm r; else { s = con đầu tiên từ trái sang phải của r T(s) = Cây con với gốc s; Inorder( T(s) ); Thăm r for (Mỗi cây con c của r từ trái sang phải trừ s) T(c) = Cây con với gốc c Inorder( T(c) ) } } Chương 5 - Cây 56
  57. V.4. Các phương pháp duyệt cây ™ Thuật toán duyệt hậu tự Void Postorder( cây thứ tự có gốc T); { r = gốc của T for (Mỗi cây con c của r từ trái sang phải) { T(c) = Cây con với gốc c Postorder( T(c) ) } Thăm r } Chương 5 - Cây 57
  58. V.4. Các phương pháp duyệt cây ™ Ví dụ + Duyệt tiền tự: a, b, c, d, e, f, g, h, o, k, l, m, n, p, q, s, t + Duyệt trung tự: d, c, e, b, a, g, f, h, m, l, n, k, o, p, s, q, t + Duyệt hậu tự: d, e, c, b, g, h, f, m, n, l, k, p, s, t, q, o, a Chương 5 - Cây 58