Bài giảng Khoa học Máy tính - Bài 10: Cây (Tree) - Nguyễn Phương Thái

Nội dung text: Bài giảng Khoa học Máy tính - Bài 10: Cây (Tree) - Nguyễn Phương Thái

1. Cây (Tree) Nguyễn Phương Thái Bộ môn Khoa Học Máy Tính – Khoa CNTT Đại Học Công Nghệ - ĐHQGHN Email: thainp@vnu.edu.vn
2. Khái ni ệm cây • Cây là một đồ thị định hướng thỏa mãn các tính chất sau: • Có một đỉnh đặc biệt được gọi là gốc cây • Mỗi đỉnh C bất kỳ không phải là gốc, tồn tại duy nhất một đỉnh P có cung đi từ P đến C. Đỉnh P được gọi là cha của đỉnh C, và C là con của P • Có đường đi duy nhất từ gốc tới mỗi đỉnh của cây. Gốc Đỉnh trong Lá
3. Cài đặt cây b ằng m ảng con tr ỏ Template root class Node { Item data; List children; A } B C D Node * root; (Xem hình v ẽ) E F G
4. Cài đặt cây b ằng hai con trỏ template root class Node { A Item data; Node* firstChild; Node* nextSibling; B C D }; Node * root; E F G
5. Duyệt cây
6. Duyệt cây theo th ứ tự trước • Thăm gốc r. • Duyệt lần lượt các cây con T1, , Tk theo thứ tự trước ABEFCDGA B E F C D G
7. Duyệt cây theo th ứ tự trước Template Preorder (Node* root) { viiisit ()(root); for each child r do Preorder (r); }
8. Duyệt cây theo th ứ tự sau • Duyệt lần lượt các cây con T1, , Tk theo thứ tự sau • Thăm gốc r. EFBCGDAE F B C G D A
9. Duyệt cây theo th ứ tự sau Template Postorder (Node* root) { for each child r of root do Postorder (r); visit (root); }
10. Cây nhị phân template Class Node { Item data; // Dữ liệu chứa trong mỗi đỉnh Node* left; Node* right; };
11. Các ki ểu cây nh ị phân Cây nhị phân đầy đủ Cây nhị phân cân bằng: Độ cao cây con bến trái và bên phải chênh nhau không quá một
12. Problem Bài toán: Cho một danh sách các đối tượng, hãy tổ chức cấu trúc dữ liệu để thực hiện các phép toán dưới đây một cách hiệu quả: • Tìm kiếm (()search) • Thêm vào (insert) • Xóa đi (delete) Đáp án: Dùng cấu trúc cây tìm kiếm nhị phân
13. Cây tìm ki ếmnhm nhị phân • Cây nhị phân rỗng là cây tìm kiếm nhị phân • Cây nhị ppghân không rỗnggy T là cây tìm kiếm nhị phân nếu: – Khóa của gốc lớn hơn khóa của tất cả các đỉnh ở cây con trái TL và nhỏ hơn khóa của tất cả các đỉnh ở cây con phải TR – Cây con trái TL và cây con phải TR là các cây tìm kiếm nhị phân.
14. Phép toán tìm ki ếm (search) binarySearchTree (Node* root, lookingData) { if (Root == NULL) return NULL; else if (root.data == lookingData) return root else if (root.data < lookingData) return binarySearchTree (root.right, lookingData) else return binarySearchTree (root.left, lookingData) }
15. Phép toán tìm ki ếmmph phầnnt tử nhỏ nhất - lớnnhn nhất //Root != NULL Min (Node* root) { if (Root .left == NULL) return root else return Min (root.left) } Max (Node* root) { if (Root .right == NULL) return root else return Max (root.right) }
16. Phép toán thêm vào (insert) insert (Node* root, insertData) { if (Root == NULL) Root insertData else if insertData Root.data ) insert (root.left, insertData) else insert (root.right, insertData) }
17. Phép toán thêm vào (insert) Thêm phần tử 6 Thêm phần tử 11
18. Phép toán xóa (delete)
19. Phép toán xóa (delete) 5 5 2 7 7 3 3 6 11 11 6 8 12 12 (b) 8 (a) 9 9 Xóa đỉnh 2 5 2 8 3 6 11 (c) 9 12 Xóa đỉnh 7
20. Phép toán xóa (delete) Delete (root, deleteData) { if (deleteData root.data) Delete (root.right, deleteData); // Loại ở cây con phải else if (root.left != NULL && root.right != NULL) { min Min ((g)root.right); root min; Delete min; } else if (()root.left == NULL) root = root.right else root = roo t. le ft }