›
›

Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 5: Cấu trúc cây - Nguyễn Thị Xuân Hương

pdf 55 trang huongle 1621
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 5: Cấu trúc cây - Nguyễn Thị Xuân Hươ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_cau_truc_du_lieu_va_giai_thuat_chuong_5_cau_truc_c.pdf

Nội dung text: Bài giảng Cấu trúc Dữ liệu và giải thuật - Chương 5: Cấu trúc cây - Nguyễn Thị Xuân Hương

  1. TRƯỜNG ĐẠI HỌC DÂN LẬP HẢI PHÒNG KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Ths. Nguyễn Thị Xuân Hương 1
  2. Chương 5: CẤU TRÚC CÂY 5.1. Định nghĩa và khái niệm 5.1.1 Định nghĩa: Cây một tập hữu hạn các nút (phần tử), giữa các nút có mối quan hệ phân cấp gọi là quan hệ “ cha – con”. Có một nút đặc biệt gọi là nút gốc ( root). Định nghĩa đệ quy: - Mỗi nút là một cây, nút đó cũng là nút gốc của cây ấy. - Nếu n là một nút và n1, n2, .,nk lần lượt là gốc của các cây C1,C2, Ck; các cây này từng đôi một không có nút chung. Nếu cho n là cha của các nút n1, n2, .,nk thì ta sẽ có một cây mới kí hiệu là cây C. Cây C có nút gốc là n và các cây C1,C2, Ck trỡ thành các cây con ( subtree) của cây C. - Một cây không có nút nào gọi là cây rỗng ( null tree). 2
  3. Chương 5: CẤU TRÚC CÂY 5.1. Định nghĩa và khái niệm Xét ví dụ trên hình sau: 3
  4. Chương 5: CẤU TRÚC CÂY 5.1. Định nghĩa và khái niệm 5.1.2. Một số khái niệm Cấp (degree) của một nút = số con của nút đó Cấp của cây = cấp cao nhất của nút trên cây Mức của cây: gốc: mức 1 nút cha I, thì con của nó có mức i+1 Độ cao (height) của cây: là số mức lớn nhất trên cây Cây có thứ tự (ordered tree): nếu ta quan tâm đến thứ tự các cây con của một nút, ngược lại là cây không có thứ tự (unordered tree). Rừng (forest): tập hữu hạn các cây phân biệt. 4
  5. Chương 5: CẤU TRÚC CÂY 5.2. Cây nhị phân (Binary tree) 5.2.1 Định nghĩa và một số khái niệm - Định nghĩa: Cây nhị phân là cây mà mọi nút của nó có tối đa hai cây con. Với mỗi nút xác định cây con trái và cây con phải. - Một số cây nhị phân 5
  6. Chương 5: CẤU TRÚC CÂY 5.2. Cây nhị phân (Binary tree) - Cây nhị phân hoàn chỉnh -Cây nhị phân đầy đủ 6
  7. Chương 5: CẤU TRÚC CÂY 5.2. Cây nhị phân (Binary tree) Thảo luận: Ngoài định nghĩa trên, ta có thể định nghĩa cây là gì? Các cây nhị phân có cùng số nút ->cây cao nhất, cây thấp nhất? Số lượng tối đa và tối thiểu các nút trên mức i là bao nhiêu? Số lượng tối đa, tối thiểu các nút trên cây nhị phân có chiều cao h là bao nhiêu? Cây nhị phân hoàn chỉnh có n nút thì chiều cao của nó là bao nhiêu? 7
  8. Chương 5: CẤU TRÚC CÂY 5.2.2 Biểu diễn cây nhị phân a) Biểu diễn bằng mảng Giả sử chỉ số cho các nút trên cây bắt đầu từ 1 1 1 2 3 4 5 6 7 A B E C D F G 2 3 •Nút có chỉ số i -> con trái có chỉ số: 2*i 4 5 6 7 -> con phải có chỉ số: 2*i+1 •Nút gốc: chỉ số 1 8
  9. Chương 5: CẤU TRÚC CÂY 5.2.2 Biểu diễn cây nhị phân a)Biểu diễn bằng mảng define MAXBT 100 typedef truct BTREE { int n; ElementType Ele[MAXBT]; }; BTREE T; 9
  10. Chương 5: CẤU TRÚC CÂY 5.2.2 Biểu diễn cây nhị phân b) Biểu diễn bằng con trỏ Mỗi nút tối thiểu có 3 trường: •Item: giá trị của nút left Item right •left: con trỏ trỏ đến cây con trái •right: con trỏ trỏ đến cây con phải •nút lá: trường left, right trỏ đến NULL 10
  11. Chương 5: CẤU TRÚC CÂY 5.2.2 Biểu diễn cây nhị phân b) Biểu diễn bằng con trỏ typedef struct BTREE { ElementType item; BTREE *left,*right; }; BTREE *root 11
  12. Chương 5: CẤU TRÚC CÂY 5.3. Các phép toán duyệt cây nhị phân: -Duyệt cây (traversal): thăm các nút trên cây, mỗi nút duy nhất một lần theo một trật tự nhất định. •Duyệt theo thứ tự trước ( PreOrder traversal) •Duyệt theo thứ tự giữa ( InOrder traversal) •Duyệt theo thứ tự sau ( PostOrder traversal) 12
  13. Chương 5: CẤU TRÚC CÂY 5.3. Các phép toán duyệt cây nhị phân: •Duyệt theo thứ tự trước ( PreOrder traversal) - Nếu cây khác rỗng - Thăm nút gốc (truy nhập giá trị của nút đó để xử lý) - Duyệt cây con trái theo thứ tự trước - Duyệt cây con phải theo thứ tự trước 13
  14. Chương 5: CẤU TRÚC CÂY 5.3. Các phép toán duyệt cây nhị phân: * Duyệt theo thứ tự trước A Ví dụ: A B C D E G Thủ tục: B E void preOder (BTREE *root) { if (root != NULL) C D G visit(root); preOder (root->left); preOder (root->right); } Độ phức tạp thủ tục: O(n) – với n là số nút trên cây. 14
  15. Chương 5: CẤU TRÚC CÂY 5.3. Các phép toán duyệt cây nhị phân: •Duyệt theo thứ tự giữa ( InOrder traversal) - Nếu cây khác rỗng - Duyệt cây con trái theo thứ tự giữa - Thăm nút gốc - Duyệt cây con phải theo thứ tự giữa 15
  16. Chương 5: CẤU TRÚC CÂY 5.3. Các phép toán duyệt cây nhị phân: • Duyệt theo thứ tự giữa A Ví dụ: C B D A E G Thủ tục: B E void inOder (BTREE *root) { if (root != NULL) C D G inOder (root->left); visit(root); inOder (root->right); } Độ phức tạp thủ tục: O(n) – với n là số nút trên cây. 16
  17. Chương 5: CẤU TRÚC CÂY 5.3. Các phép toán duyệt cây nhị phân: •Duyệt theo thứ tự sau ( PostOrder traversal) - Nếu cây khác rỗng - Duyệt cây con trái theo thứ tự sau - Duyệt cây con phải theo thứ tự sau - Thăm nút gốc 17
  18. Chương 5: CẤU TRÚC CÂY 5.3. Các phép toán duyệt cây nhị phân: * Duyệt theo thứ tự sau A Ví dụ: C D B G E A Thủ tục: B void postOder (BTREE *root) E { if (root != NULL) C D G visit(root); postOder (root->left); postOder (root->right); } Độ phức tạp thủ tục: O(n) – với n là số nút trên cây. 18
  19. Chương 5: CẤU TRÚC CÂY 5.4. Ứng dụng của cây nhị phân Cây biểu diễn biểu thức * (x+y)*( z) Cây nhị phân tìm kiếm: 10 + - - 7 15 x y z 6 9 16 19 19
  20. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm 10 5.5.1. Định nghĩa: là cây nhị phân, trong đó •Giá trị khóa của các nút của cây 7 15 con trái nhỏ hơn giá trị của nút gốc. •Giá trị của các nút của cây con phải lớn hơn giá trị của nút gốc. 6 9 16 •Cây con trái và cây con phải cũng là cây nhị phân tìm kiếm 19 20
  21. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm 10 5.5.2. Biểu diễn dữ liệu typedef truct BTREE 7 15 { int key 6 9 16 BTREE *left,*right; }; BTREE *root; 19 21
  22. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm •5.5.3.Các phép toán trên cây tìm kiếm nhị phân: Phép khởi tạo Phép chèn Phép tìm kiếm Phép xóa 22
  23. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm •5.5.3.Các phép toán trên cây tìm kiếm nhị phân:  Phép khởi tạo: Cây nhị phân là rỗng 10 void Init (BTREE *(&root)) { 7 15 root = NULL; } 6 9 16 19 23
  24. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm •5.5.3.Các phép toán trên cây tìm kiếm nhị phân:  Phép chèn ( insert) Giải thuật: chèn khóa x vào cây nhị phân tìm kiếm Nếu nút gốc rỗng -> chèn khóa x vào nút gốc Ngược lại: so sánh khóa x với khóa tại nút gốc: Nếu x chèn x vào cây con trái Nếu x > khóa ở nút gốc -> chèn x vào cây con phải Nếu x = khóa ở nút gốc -> kết thúc. Tại cây con trái và cây con phải thực hiện chèn như tại nút gốc 24
  25. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm •5.5.3.Các phép toán trên cây tìm kiếm nhị phân:  Phép chèn ( insert) 10 Chèn khóa x = 12 vào cây 7 15 12 6 9 12 16 19 25
  26. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm Phép chèn ( insert): Thủ tục: void Insert (BTREE *root, int x) { if (root == NULL) { tmp = new BTREE; tmp->key = x; tmp->left = NULL: tmp->right = NULL: root = tmp; } else if ( x key) Insert(root->left,x) else if ( x >root->key) Insert(root->right,x) } 26
  27. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm •5.5.3.Các phép toán trên cây tìm kiếm nhị phân:  Phép xóa một nút (delete) :xóa nút x trên cây Giải thuật: Nếu khác rỗng Ngược lại: tìm khóa x cần xóa trên cây Nếu x = khóa ở nút gốc -> xóa x Nếu x Xóa x ở cây con trái (bằng pp trên) Nếu x > khóa ở nút gốc -> Xóa x ở cây con phải (bằng pp trên) Tại cây con trái và cây con phải thực hiện xóa như tại nút gốc 27
  28. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm Để xóa một nút (delete) đã tìm thấy Trường hợp 1: nút cần xóa là lá 10 x = 9 -> xóa nút đó 7 15 6 99 16 19 28
  29. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm Để xóa một nút (delete) đã tìm thấy Trường hợp 2: nút cần xóa là nút có con trái = NULL 10 x = 15 -> Treo con phải thay cho nút đó 7 15 10 15 7 15 6 9 1616 6 9 19 19 29
  30. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm Để xóa một nút (delete) đã tìm thấy Trường hợp 3: nút cần xóa là nút có con phải = NULL 10 x = 6 -> Treo con trái thay cho nút đó 10 7 15 7 15 66 9 16 2 9 16 2 19 19 30
  31. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm Để xóa một nút (delete) đã tìm thấy Trường hợp 4: nút cần xóa có hai con != NULL C1:-> chọn nút phải cùng của cây con trái thay cho nút đó C2: -> chọn nút trái cùng của cây con phải thay cho nút đó 31
  32. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm Để xóa một nút (delete) đã tìm thấy: Trường hợp 4: chọn nút phải cùng của cây con trái: Nút cần xóa p (7) có hai con != NULL 10 Cây con trái có gốc là t (6) 7 p và không có con phải 15 Lấy gốc của con trái thay cho t nút cần xóa: 666 9 16 t-> right = p -> right 8 p = t 2 19 32
  33. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm Để xóa một nút (delete) đã tìm thấy Trường hợp 4: chọn nút phải cùng của cây con trái VD: xóa x = 10 10 p p:nút cần xóa t 7 s: Nút phải cùng của cây con trái 15 t: là cha của nút s Cho t->right = s.left 6 9 16 s (giữ lại con trái nút phải cùng) 8 s->left = p->left 2 19 s->right = p->right p = s 33
  34. Chương 5: CẤU TRÚC CÂY Giải thuật: Nếu cây khác rỗng tìm khóa x cần xóa trên cây Nếu x = khóa ở nút gốc -> xóa nút gốc - cho nút p = nút gốc cần xóa - Nếu p là lá: xóa p -Ngược lại, Nếu p có con trái = NULL ->Treo con phải của p thay cho nó - Ngược lại Nếu p có con phải = NULL ->Treo con trái của p thay cho nó - Ngược lại, nếu p có cả hai con: chọn nút phải cùng của cây con trái thay cho nó TH1: cây con trái không có con phải -> lấy nút gốc cây con trái thay cho nó. TH1: Lấy nút phải cùng của cây con trái thay cho nó Nếu x Xóa x ở cây con trái Nếu x > khóa ở nút gốc -> Xóa x ở cây con phải Tại cây con trái và cây con phải thực hiện xóa như tại nút gốc 34
  35. Chương 5: CẤU TRÚC CÂY Phép tìm kiếm ( searching) Giải thuật: Nếu cây = NULL -> không tìm thấy Ngược lại. so sánh x với khóa ở nút gốc Nếu x = khóa ở nút gốc -> tìm thấy -> Kết thúc Nếu x Tìm x ở cây con trái Nếu x > khóa ở nút gốc -> Tìm x ở cây con phải Tại cây con trái và cây con phải thực hiện tìm như tại nút gốc 35
  36. Chương 5: CẤU TRÚC CÂY 5.5. Cây nhị phân tìm kiếm •5.5.3.Các phép toán trên cây tìm kiếm nhị phân:  Phép tìm kiếm ( searching) 10 Tìm khóa x = 12 trên cây Nút gốc có khóa =10 7 15 x > 10 -> tìm root->right (key =15) x tìm root->left (key =12) 6 9 12 16 x = 12 -> tìm thấy 19 36
  37. Chương 5: CẤU TRÚC CÂY  Phép tìm kiếm ( searching) Tìm khóa x = 8 trên cây Nút gốc có khóa =10 10 x tìm root->left (key = 7) x > 7 -> tìm root->right (key = 9) 7 15 x tìm root->left (=NULL) -> không tìm thấy 6 9 12 16 NULL 19 37 Không tìm thấy x
  38. Chương 5: CẤU TRÚC CÂY Phép tìm kiếm ( searching) BTREE *searching(BTREE *root, int x) { if (root == NULL) return NULL; else if (root ->key == x) return root; else if ( x key) searching (root->left,x); else if ( x >root->key) searching(root->right,x) } Chú ý: hàm trả về địa chỉ của nút tìm thấy Độ phức tạp giải thuật: O(log2n) với n là số nút trên cây 38
  39. Chương 5: CẤU TRÚC CÂY 5.6. Cây tổng quát A 0 5.5.1 Biểu diễn dữ liệu: c1: Mảng các nút cha 1 B 3 2 C D Chỉ số item Parent 0 A -1 1 B 0 4 E F G H I 5 6 7 8 2 C 0 3 D 0 4 E 1 5 - F 1 Nút đầu tiên có chỉ số 0 là gốc 6 - G 1 -> khai báo kiểu dl? 7 H 3 8 I 3 39
  40. Chương 5: CẤU TRÚC CÂY 5.6. Cây tổng quát 5.5.1 Biểu diễn dữ liệu: Cây biểu diễn bằng mảng các nút cha: define MAXT 100 typedef struct NODE { char item; // thông tin của nút int parent; // chỉ số của nút cha } typedef truct TREE { int n; // số nút trên cây NODE Ele[MAXT]; // Mảng chứa các nút của cây }; TREE T; 40
  41. Chương 5: CẤU TRÚC CÂY 5.6. Cây tổng quát A 0 5.5.1 Biểu diễn dữ liệu: C2: Mảng con cả và các em liền kề 1 B 3 2 C D Chỉ số item Oldest Next Child Sibling 0 A 1 -1 4 E F G H I 5 6 7 8 1 B 4 2 2 C -1 3 3 D 7 -1 4 - E - 1 5 Nút đầu tiên có chỉ số 0 là gốc 5 - F - 1 6 -> khai báo kiểu dl? 6 G -1 -1 7 H -1 8 8 I -1 -1 41
  42. Chương 5: CẤU TRÚC CÂY 5.6. Cây tổng quát 5.5.1 Biểu diễn dữ liệu: C3: * Biểu diễn bằng cấu trúc tự trỏ (lưu trữ móc nối) -Tại mỗi nút của cây, ngoài trường dữ liệu của nút ta sử dụng một danh sách các con trỏ để trỏ tới con của nó 42
  43. Chương 5: CẤU TRÚC CÂY 5.6. Cây tổng quát 5.5.1 Biểu diễn dữ liệu: C3: * Biểu diễn bằng cấu trúc tự trỏ (lưu trữ móc nối) typedef KeyType ElementType; #define MNODE 3 typedef struct NODE { ElementType info; NODE *child[MNODE]; }; NODE *root; 43
  44. Chương 5: CẤU TRÚC CÂY 5.6. Cây tổng quát 5.5.2 Các phép toán trên cây tổng quát:  Khởi tạo  Tạo cây có n nút  Tìm các nút trên cây: Cha, con cả, em liền kề  Duyệt cây 44
  45. Chương 5: CẤU TRÚC CÂY 5.6. Cây tổng quát 5.5.2 Các phép toán trên cây tổng quát: Cây biểu diễn bằng mảng các nút cha: define MAXT 100 Typedef struct NODE { char item; // thông tin của nút int parent; // chỉ số của nút cha } typedef truct TREE { int n; // số nút trên cây NODE Ele[MAXT]; // Mảng chứa các nút của cây }; TREE T; 45
  46. Chương 5: CẤU TRÚC CÂY 5.6. Cây tổng quát 5.5.2 Các phép toán trên cây tổng quát: Khởi tạo: cây rỗng void Init (TREE &T) { T.n = 0; } 46
  47. Chương 5: CẤU TRÚC CÂY 5.6. Cây tổng quát 5.5.2 Các phép toán trên cây tổng quát: Tạo cây có n nút: Giải thuật: thêm n nút vào cây với mỗi nút có 2 thông tin: giá trị của nút (item) và chỉ số nút cha của nó (parent) void Create(TREE &T, int n) { int i; for( i =0; i >T.Ele[i].item; cout >T.Ele[i].parent; } 47 }
  48. Chương 5: CẤU TRÚC CÂY 5.6. Cây tổng quát 5.5.2 Các phép toán trên cây tổng quát:  Tìm các nút trên cây Tìm cha của một nút i: -Giải thuật: nếu cây rỗng -> trả về -1 -Ngược lại: trả về chỉ số nút cha của nút đó Int Parent(TREE &T, int i) { if(T.n == 0) return -1; else return T.Ele[i].parent; } 48
  49. Chương 5: CẤU TRÚC CÂY  Tìm các nút trên cây Tìm con cả của một nút i: -Giải thuật: nếu cây rỗng -> trả về -1, KT -Ngược lại: duyệt các nút có chỉ số j = i+1 đến hết Tìm nút j có trường parent của nó = i => KT, nếu không thấy: trả về -1; Int OldestChild(TREE &T, int i) { if(T.n == 0) return -1; else { j = i+1; while (j <T.n) { if (T.Ele[j].parent == i) return j; j++; } return -1; } 49 }
  50. Chương 5: CẤU TRÚC CÂY  Tìm các nút trên cây Tìm em liền kề của một nút i: -Giải thuật: nếu cây rỗng -> trả về -1, KT -Ngược lại: duyệt các nút có chỉ số j = i+1 đến hết Tìm nút j có parent của j = parent của i => KT, nếu không thấy trả về -1 Int NextSibling(TREE &T, int i) { if(T.n == 0) return -1; else { j = i+1; while (j <T.n) { if (T.Ele[j].parent == T.Ele[i].parent) return j; j++; } return -1; } 50 }
  51. Chương 5: CẤU TRÚC CÂY 5.6. Cây tổng quát 5.5.2 Các phép toán trên cây tổng quát: Duyệt cây: -Duyệt theo trật tự trước : Gốc – con cả - các em liền kề. -Duyệt theo trật tự giữa : con cả - Gốc – các em liền kề. -Duyệt theo trật tự sau: : con cả - các em liền kề - Gốc 51
  52. Chương 5: CẤU TRÚC CÂY Duyệt cây: -Duyệt theo thứ tự trước : Gốc – con cả - các em liền kề. -Giải thuật: A -Nếu cây khác rỗng -Thăm nút gốc B -Duyệt con cả theo thứ tự trước C D -Duyệt các em liền kề theo thứ tự trước E F G H I A B E F G C D H I 52
  53. Chương 5: CẤU TRÚC CÂY Duyệt cây: A -Duyệt theo thứ tự giữa: -Giải thuật: B C D -Nếu cây khác rỗng -Duyệt con cả theo thứ tự giữa E F G H I -Thăm nút gốc -Duyệt các em liền kề theo thứ tự giữa E B F G A C H D I 53
  54. Chương 5: CẤU TRÚC CÂY 5.6. Cây tổng quát 5.5.3. Ứng dụng của cây tổng quát: -Cây gia phả -Sơ đồ tổ chức -Cây quyết định - . 54
  55. Chương 5: CẤU TRÚC CÂY Bài tập về nhà: 1. Cài đặt chương trình với các thao tác trên cây nhị phân tìm kiếm, cây tổng quát. 2. Viết một ứng dụng cho cây nhị phân và cây tổng quát. 55