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 - Đỗ Tuấn Anh

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 - Đỗ Tuấn Anh

1. Cấu trúc dữ liệu và giải thuật Đỗ Tuấn Anh anhdt@it-hut.edu.vn
2. Nội dung z Chương 1 – Thiết kế và phân tích (5 tiết) z Chương 2 – Giải thuật đệ quy (10 tiết) z Chương 3 – Mảng và danh sách (5 tiết) z Chương 4 – Ngăn xếp và hàng đợi (10 tiết) z Chương 5 – Cấu trúc cây (10 tiết) z Chương 8 – Tìm kiếm (5 tiết) z Chương 7 – Sắp xếp (10 tiết) z Chương 6 – Đồ thị (5 tiết)
3. Chương 5 – Cấu trúc cây 1. Định nghĩa và khái niệm 2. Cây nhị phân { Định nghĩa và Tính chất { Lưu trữ { Duyệt cây 3. Cây tổng quát { Biểu diễn cây tổng quát { Duyệt cây tổng quát (nói qua) 4. Ứng dụng của cấu trúc cây • Cây biểu diễn biểu thức (tính giá trị, tính đạo hàm) • Cây quyết định
4. 1. Định nghĩa và khái niệm z Danh sách chỉ thể hiện được các mối quan hệ tuyến tính. z Thông tin còn có thể có quan hệ dạng phi tuyến, ví dụ: {Các thư mục file {Các bước di chuyển của các quân cờ {Sơ đồ nhân sự của tổ chức {Cây phả hệ z Sử dụng cây cho phép tìm kiếm thông tin nhanh
5. Cây là gì? đỉnh cạnh #cạnh = #đỉnh – 1 Kết nối tối thiểu T là không liên thông nếu xóa đi bất kỳ cạnh nào. Không có chu trình T sẽ chứa chu trình nếu thêm bất kỳ cạnh nào.
6. Cây là gì? zTập các nút (đỉnh), trong đó: {Hoặc là rỗng {Hoặc có một nút gốc và các cây con kết nối với nút gốc bằng một cạnh
7. Ví dụ: Cây thư mục
8. Ví dụ: Cây biểu thức
9. Các khái niệm nút gốc a nút giữa/nhánh nút cha b d c nút anh em nút e f nút lá g h nút con nút con i j e, i, k, g, h k là các nút lá
10. Cây con nút gốc Một nút và tất cả các nút con cháu. a b d c e f g h i j k
11. Đường đi Tồn tại một đường đi duy nhất từ một nút bất kỳ đến nút con Từ nút cha đến các nút cháu của nó. con cháu của nó. a b d Đường c Đường đi 2 đi 1 f h e g i j Đường đi 1: { a, b, f, j } Đường đi 2: { d, i }
12. Độ sâu và độ cao Chiều cao = 4 7 Độ sâu 0 3 10 4 Độ sâu 1 Nút có chiều cao = 2 8 12 11 2 Độ sâu 2 6 5 1 Độ sâu 3 Độ sâu 4 9
13. Cấp (degree) Số con của nút x được gọi Cấp= 3 là cấp của x. 7 3 10 4 8 12 Cấp= 1 11 2 Cấp= 0 6 5 1 9
14. 2. Cây nhị phân 2.1. Định nghĩa và tính chất Mỗi nút có nhiều nhất 2 nút con. Con trái và Con phải Một tập các nút T được gọi là cây nhị phân nếu a) Nó là cây rỗng, hoặc b) Gồm 3 tập con không trùng nhau: 1) một nút gốc r 2) Cây nhị phân con trái 3) Cây nhị phân con phải a e b c f d cây con phải cây con trái
15. Cây nhị phân đầy đủ và Cây nhị phân hoàn chỉnh Cây nhị phân đầy đủ: Cây nhị phân hoàn chỉnh: Các nút hoặc là nút lá Tất cả nút lá đều có cùng hoặc có cấp = 2. độ sâu và tất cả nút giữa có cấp = 2. 7 73 3 10 3 10 2 8 12 8 12 11
16. Một số dạng cây nhị phân
17. Một số tính chất zSố nút tối đa có độ sâu i : 2i zSố nút tối đa (với cây nhị phân độ cao H) là: 2H+1 - 1 zĐộ cao (với cây nhị phân gồm N nút): H {Tối đa= N {Tốithiểu = [log2(N+1)] - 1
18. 2.2 Lưu trữ cây nhị phân zLưu trữ kế tiếp: {Sử dụng mảng
19. Lưu trữ móc nối a left a right b c left b right left c right e f NULL left e right left f right g left g right
20. Xây dựng cấu trúc cây nhị phân zMỗi nút chứa: {Dữ liệu {2 con trỏ trỏđến 2 nút con củanó Data Nút con Nút con trái phải
21. Cấu trúc cây nhị phân typedef struct tree_node { int data ; struct tree_node *left ; struct tree_node *right ; } TREE_NODE;
22. Tạo cây nhị phân TREE_NODE *root, *leftChild, *rightChild; // Tạo nút con trái leftChild = (TREE_NODE*)malloc(sizeof(TREE_NODE)); leftChild->data = 20; leftChild->left = leftChild->right = NULL; // Tạo nút con phải rightChild = (TREE_NODE*)malloc(sizeof(TREE_NODE)); rightChild->data = 30; rightChild->left = rightChild->right = NULL; // Tạo nút gốc 1050 root = (TREE_NODE*)malloc(sizeof(TREE_NODE)); root->data = 10; root->left = leftChild; 20 30 root->right = rightChild; root -> data = 50; // gán 50 cho root
23. 2.3. Duyệt cây nhị phân z Duyệt cây: lần lượt duyệt toàn bộ nút trên cây z Có 3 cách duyệtcây: { Duyệt theo thứ tự trước { Duyệt theo thứ tự giữa { Duyệt theo thứ tự sau z Định nghĩaduyệt cây nhị phân là những định nghĩa đệ quy.
24. Duyệt theo thứ tự trước 1. Thăm nút. 2. Duyệt cây con trái theo thứ tự trước. 3. Duyệt cây con phải theo thứ tự trước. a Traversal order: abdce b c d e
25. Duyệt theo thứ tự sau 1. Duyệt cây con trái theo thứ tự sau. 2. Duyệt cây con phải theo thứ tự sau. 3. Thăm nút. a Thứ tự duyệt: dbeca b c d e
26. Duyệt theo thứ tự giữa 1. Duyệt cây con trái theo thứ tự giữa 2. Thăm nút. 3. Duyệt cây con phải theo thứ tự giữa. a Thứ tự duyệt: bdaec b c d e
27. Ví dụ 15 6 18 3 7 13 17 20 2 4 9 Thứ tự trước: 15, 6, 3, 2, 4, 7, 13, 9, 18, 17, 20 Thứ tự giữa: 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20 Thứ tự sau: 2, 4, 3, 9, 13, 7, 6, 17, 20, 18, 15
28. Duyệttheothứ tự trước–Đệ quy void Preorder(TREE_NODE* root) { if (root!=NULL) { // tham aNode printf("%d ", root->data); // duyet cay con trai Preorder(root->left); // duyet cay con phai Preorder(root->right); } }
29. zBài tập: Viết giải thuật đệ quy của {Duyệt theo thứ tự giữa {Duyệt theo thứ tự sau
30. Duyệttheothứ tự trước – Vòng lặp void Preorder_iter(TREE_NODE* treeRoot) { TREE_NODE* curr = treeRoot; STACK* stack = createStack(MAX); // khởi tạo stack while (curr!=NULL || !IsEmpty(stack)) { printf("%d ", curr->data); // thăm curr // nếu có cây con phải, đẩy cây con phải vào stack if (curr->right!=NULL) pushStack(stack, curr->right); if (curr->left!=NULL) curr = curr->left; // duyệt cây con trái else popStack(stack, &curr);// duyệt cây con phải } destroyStack(&stack); // giải phóng stack }
31. Duyệttheothứ tự giữa void Inorder_iter(TREE_NODE* root){ TREE_NODE* curr = root; STACK* stack = createStack(MAX);// ktạo stack while (curr!=NULL || !IsEmpty(stack)) { if (curr==NULL){ popStack(stack, &curr); printf(“%d”, curr->data); curr = curr->right; } else { pushStack(stack, curr); curr = curr->left; // duyệt cây con trái } } destroyStack(stack);// giải phóng stack }
32. Duyệttheothứ tự cuối void Postorder_iter(TREE_NODE* treeRoot) { TREE_NODE* curr = treeRoot; STACK* stack = createStack(MAX);// ktạomột stack while(curr != NULL || !IsEmpty(stack)) { if (curr == NULL) { while(!IsEmpty(stack) && curr==Top(stack)->right){ PopStack(stack, &curr); printf(“%d”, curr->data); } curr = isEmpty(stack)? NULL: Top(stack)->right; } else { PushStack(stack, curr); curr = curr->left; } } destroyStack(&stack); // giải phóng stack }
33. Một vài ứng dụng của phương pháp duyệt cây 1. Tính độ cao của cây 2. Đếm số nút lá trong cây 3. Tính kích thước của cây (số nút) 4. Sao chép cây 5. Xóa cây 6.
34. Tính độ cao của cây 2 0 1 0 -1 int Height(TREE_NODE *tree) -1 { int heightLeft, heightRight, heightval; if ( tree == NULL ) heightval = -1; else { // Sử dụng phương pháp duyệt theo thứ tự sau heightLeft = Height (tree->left); heightRight = Height (tree->right); heightval = 1 + max(heightLeft, heightRight); } return heightval; }
35. Đếm số nút lá 3 1 int CountLeaf(TREE_NODE *tree) { 2 if (tree == NULL) return 0; int count = 0; thứ tự đếm // Đếm theo thứ tự sau count += CountLeaf(tree->left); // Đếm trái count += CountLeaf(tree->right); // Đếm phải // nếu nút tree là nút lá, tăng count if (tree->left == NULL && tree->right == NULL) count++; return count; }
36. Kích thước của cây int TreeSize(TREE_NODE *tree) { if (tree == NULL) return 0; else return ( TreeSize(tree->left) + TreeSize(tree->right) + 1 ); } t
37. Sao chép cây A B B C D D D E (1) (2) A B C B C D E D E (4) (3)
38. Sao chép cây TREE_NODE* CopyTree(TREE_NODE *tree) { // Dừng đệ quy khi cây rỗng if (tree == NULL) return NULL; TREE_NODE *leftsub, *rightsub, *newnode; leftsub = CopyTree(tree->left); rightsub = CopyTree(tree->right); // tạo cây mới newnode = malloc(sizeof(TREE_NODE)); newnode->data = tree->data; newnode->left = leftsub; newnode->right = rightsub; return newnode; }
39. Xóa cây void DeleteTree(TREE_NODE *tree) { // xóa theo thứ tự sau if (tree != NULL) { DeleteTree(tree -> left); DeleteTree(tree -> right); free (tree); } }
40. 3. Cây tổng quát 3.1. Biểu diễn cây tổng quát zBiểu diễn giống như cây nhị phân? {Mỗi nút sẽ chứagiátrị và các con trỏ trỏđến các nút con của nó? {Bao nhiêu con trỏ cho một nút? – Không hợplý zMỗi nút sẽ chứa giá trị và một con trỏ trỏ đếnmột“tập” các nút con {Xây dựng “tập” như thế nào?
41. Biểu diễn cây tổng quát zSử dụng con trỏ nhưng mở rộng hơn: {Mỗi nút sẽ có 2 con trỏ: một con trỏ trỏđến nút con đầutiêncủa nó, con trỏ kia trỏđến nút anh em kề vớinó {Cách này cho phép quảnlýsố lượng tùy ý của các nút con Data Nút con Nút anh trái nhất em kề
42. 3.2. Duyệt cây tổng quát 1. Thứ tự trước: 1. Thăm gốc 2. Duyệt cây con thứ nhất theo thứ tự trước 3. Duyệt các cây con còn lại theo thứ tự trước 2. Thứ tự giữa 1. Duyệt cây con thứ nhất theo thứ tự giữa 2. Thăm gốc 3. Duyệt các cây con còn lại theo thứ tự giữa 3. Thứ tự sau: 1. Duyệt cây con thứ nhất theo thứ tự sau 2. Duyệt các cây con còn lại theo thứ tự sau 3. Thăm gốc
43. 4. Ứng dụng của cây nhị phân zCây biểu diễn biểu thức {Tính giá trị biểu thức {Tính đạo hàm zCây quyết định
44. Cây biểu diễn biểu thức là . . . Một loại cây nhị phân đặc biệt, trong đó: 1. Mỗi nút lá chứa một toán hạng 2. Mỗi nút giữa chứa một toán tử 3. Cây con trái và phải của một nút toán tử thể hiện các biểu thức con cần được đánh giá trước khi thực hiện toán tử tại nút gốc 45
45. Biểu thức nhị phân ‘*’ ‘-’ ‘/’ ‘8’ ‘5’ ‘+’ ‘3’ ‘4’ ‘2’ 46
46. Các mức chỉ ra thứ tự ưu tiên Các mức(độ sâu) của các nút chỉ ra thứ tự ưu tiên tương đối của chúng trong biểu thức (không cần dùng ngoặc để thể hiện thứ tự ưu tiên). Các phép toán tại mức cao hơn sẽ được tính sau các các phép toán có mức thấp. Phép toán tại gốc luôn được thực hiện cuối cùng. 47
47. Cây biểu diễn biểu thức ‘*’ ‘+’ ‘3’ ‘4’ ‘2’ Giá trị kết quả? ( 4 + 2 ) * 3 = 18 48
48. Dễ dàng để tạo ra các biểu thức tiền tố, trung tố, hậu tố ‘*’ ‘-’ ‘/’ ‘8’ ‘5’ ‘+’ ‘3’ ‘4’ ‘2’ Trung tố: ( ( 8 - 5 ) * ( ( 4 + 2 ) / 3 ) ) Tiền tố: * - 8 5 / + 4 2 3 Hậu tố: 8 5 - 4 2 + 3 / * 49
49. Duyệt theo thứ tự giữa (A + H) / (M - Y) cây ‘/’ ‘+’ ‘-’ ‘A’ ‘H’ ‘M’ ‘Y’ 50
50. Duyệt theo thứ tự trước /+ A H -M Y cây ‘/’ ‘+’ ‘-’ ‘A’ ‘H’ ‘M’ ‘Y’ 51
51. Duyệt theo thứ tự sau AH + M Y -/ tree ‘/’ ‘+’ ‘-’ ‘A’ ‘H’ ‘M’ ‘Y’ 52
52. Mỗi nút có 2 con trỏ struct TreeNode { InfoNode info ; // Dữ liệu TreeNode* left ; // Trỏ tới nút con trái TreeNode* right ; // Trỏ tới nút con phải }; NULL OPERAND 7 6000 . whichType . operand left info right . . . 53
53. InfoNode có 2 dạng enum OpType { OPERATOR, OPERAND } ; struct InfoNode { OpType whichType; union // ANONYMOUS union { char operator ; int operand ; } }; OPERATOR ‘+’ OPERAND 7 . whichType . operation . whichType . operand 54
54. int Eval (TreeNode* ptr) { switch ( ptr->info.whichType ) { case OPERAND : return ptr->info.operand ; case OPERATOR : switch ( tree->info.operation ) { case ‘+’ : return ( Eval ( ptr->left ) + Eval ( ptr->right ) ) ; case ‘-’ : return ( Eval ( ptr->left ) - Eval ( ptr->right ) ) ; case ‘*’ : return ( Eval ( ptr->left ) * Eval ( ptr->right ) ) ; case ‘/’ : return ( Eval ( ptr->left ) / Eval ( ptr->right ) ) ; } } } 55
55. Cây quyết định zDùng để biểu diễn lời giải của bài toán cần quyết định lựa chọn zBài toán 8 đồng tiền vàng: {Có 8 đồng tiền vàng a, b, c, d, e, f, g, h {Có một đồng có trọng lượng không chuẩn {Sử dụng một cân Roberval (2 đĩa) {Output: zĐồng tiền k chuẩn là nặng hơn hay nhẹ hơn zSố phép cân là ít nhất
56. a+b+c ? d+e+f = a+d ? b+e g ? h a+d ? b+e > = = = > = > = > = > = > = >>= = a e c f b d g h h g b d c f a e
57. void EightCoins(a, b, c, d, e, f, g, h) { if (a+b+c == d+e+f) { if (g > h) Compare(g, h, a); else Compare(h, g, a); } else if (a+b+c > d+e+f){ if (a+d == b+e) Compare(c, f, a); else if (a+d > b+e) Compare(a, e, b); else Compare(b, d, a); } else{ if (a+d == b+e) Compare(f,c,a); else if (a+d > b+e) Compare(d, b, a); else Compare(e, a, b); } } // so sánh x với đồng tiền chuẩnz void Compare(x,y,z){ if(x>y) printf(“x nặng”); else printf(“y nhẹ”); }