Khoa học máy tính - Cây (Tree)

Chia sẻ: Nguyen Van Dai | Ngày: | Loại File: PDF | Số trang:21

Thêm vào BST

Báo xấu

288
lượt xem 74
download

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

Trong khoa học máy tính, cây là một cấu trúc dữ liệu được sử dụng rộng rãi gồm một tập hợp các nút (tiếng Anh: node) được liên kết với nhau theo quan hệ cha-con. Cây trong cấu trúc dữ liệu đầu tiên là mô phỏng (hay nói cách khác là sự sao chép) của cây (có gốc) trong lý thuyết đồ thị. Hầu như mọi khái niệm trong cây của lý thuyết đồ thị đều được thể hiện trong cấu trúc dữ liệu. Tuy nhiên cây trong cấu trúc dữ liệu đã tìm được ứng dụng phong phú và...

Chủ đề:

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

Lưu

Nội dung Text: Khoa học máy tính - Cây (Tree)

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
Khái ni cây 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 đặ cây Cài đặt cây bằng mảng con trỏ con tr Template root class Node { Item data; List children; A } B C D Node* root; root; (Xem hình vẽ) hình E F G
Cài đặ cây Cài đặt cây bằng hai con trỏ hai con tr template root class Node { A Item data; Node* firstChild; Node* nextSibling; B C D }; Node* root; E F G
Duy cây Duyệt cây
Duy cây theo th Duyệt cây theo thứ tự trước tr • Thăm gốc r. • Duyệt lần lượt các cây con T1,..., Tk theo thứ tự trước ABEFCDG
Duy cây theo th Duyệt cây theo thứ tự trước tr Template Preorder (Node* root) { visit (root); for each child r do Preorder (r); }
Duy cây theo th Duyệt cây theo thứ tự sau 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 cây theo th Duyệt cây theo thứ tự sau sau Template Postorder (Node* root) { for each child r of root 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 cây nh phân 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 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 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 (search) 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 ph Phép toán tìm kiếm phần tử nhỏ nhất - lớn nhất nh nh nh //Root != NULL Min (Node* root) { if (Root .left == NULL) return root 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) 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) 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)
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