Khái niệm Cây

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

Thêm vào BST

Báo xấu

121
lượt xem 13
download

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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

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

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
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á
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
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
Duy t cây
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
Duy t cây theo th t trư c Template Preorder (Node* root) { visit (root); for each child r do Preorder (r); }
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
Duy t cây theo th t sau Template Postorder (Node* root) { for each child r do Postorder (r); visit (root); }
Cây nh phân template Class Node { Item data; // D li u ch a trong m i ñ nh Node* left; Node* right; };
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
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
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.
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) }
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) }
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) }
Phép toán thêm vào (insert) Thêm ph n t 6 Thêm ph n t 11
Phép toán xóa (delete)
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
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 }