Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 9: Cây (Tree) - Lê Sỹ Vinh

Nội dung text: Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 9: Cây (Tree) - Lê Sỹ Vinh

1. Cây (Tree) Lê S Vinh B mơn Khoa Hc Máy Tính – Khoa CNTT ði Hc Cơng Ngh ðHQGHN Email: vinhioi@yahoo.com
2. Khái nim cây • Cây là mt đ th đnh hưng tha mãn các tính cht sau: • Cĩ mt đnh đc bit đưc gi là gc cây • Mi đnh C bt kỳ khơng phi là gc, tn ti duy nht mt đnh P cĩ cung đi t P đn C. ðnh P đưc gi là cha ca đnh C, và C là con ca P • Cĩ đưng đi duy nht t gc ti mi đnh ca cây. Gc ðnh trong Lá
3. Cài đt cây bng mng 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 bng hai con tr template root class Node { A Item data; Node * firstChild; Node* nextSibling; B C D }; Node * root; E F G
5. Duyt cây
6. Duyt cây theo th t trưc • Thăm gc r. • Duyt ln lưt các cây con T 1, , T k theo th t trưc A B E F C D G
7. Duyt cây theo th t trưc Template Preorder (Node* root) { visit (root); for each child r do Preorder ( r); }
8. Duyt cây theo th t sau • Duyt ln lưt các cây con T 1, , T k theo th t sau • Thăm gc r. E F B C G D A
9. Duyt cây theo th t sau Template Postorder (Node* root) { for each child r do Postorder ( r); visit (root); }
10. Cây nh phân template Class Node { Item data; // D liu cha trong mi đnh Node* left; Node* right; };
11. Các kiu cây nh phân Cây nh phân đy đ Cây nh phân cân bng: ð cao cây con bn trái và bên phi chênh nhau khơng quá mt
12. Problem Bài tốn: Cho mt danh sách các đi tưng, hãy t chc cu trúc d liu đ thc hin các phép tốn dưi đây mt cách hiu qu: • Tìm kim (search) • Thêm vào (insert) • Xĩa đi (delete) ðáp án: Dùng cu trúc cây tìm kim nh phân
13. Cây tìm kim nh phân • Cây nh phân rng là cây tìm kim nh phân • Cây nh phân khơng rng T là cây tìm kim nh phân nu: – Khĩa ca gc ln hơn khĩa ca tt c các đnh cây con trái T L và nh hơn khĩa ca tt c các đnh cây con phi TR – Cây con trái T L và cây con phi T R là các cây tìm kim nh phân.
14. Phép tốn tìm kim (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 tốn tìm kim phn t nh nht ln nht //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 tố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 tốn thêm vào (insert) Thêm phn t 6 Thêm phn t 11
18. Phép tốn xĩa (delete)
19. Phép tố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 tốn xĩa (delete) Delete (root, deleteData) { if (deleteData root.data) Delete (root.right, deleteData); // Loi cây con phi else if (root.left != NULL && root.right != NULL) { min ← Min (root.right); root ← min; Delete min; } else if (root.left == NULL) root = root.right else root = root.left }