Khái niệm Cây

Chia sẻ: Le Quang Duan Duan | Ngày: | Loại File: PDF | Số trang:20

0
79
lượt xem
13
download

Khái niệm Cây

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo khái niệm cây - môn Khoa học máy tính

Chủ đề:
Lưu

Nội dung Text: Khái niệm Cây

  1. Cây (Tree) Lê S Vinh B môn Khoa H c Máy Tính – Khoa CNTT ð i H c Công Ngh - ðHQGHN Email: vinhioi@yahoo.com
  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 ABEFC D G
  7. Duy t cây theo th t trư c Template Preorder (Node* root) { visit (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. EFBCGDA
  9. Duy t 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 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 m nh phân • Cây nh phân r ng là cây tìm ki m nh phân • Cây nh phân không r ng 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 m ph n t nh nh t - l n 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.left, deleteData); //Lo i cây con trái else 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 (root.right); root ← min; Delete min; } else if (root.left == NULL) root = root.right else root = root.left }
Đồng bộ tài khoản