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

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à...
Nội dung trích xuất từ tài liệu:
Khoa học máy tính - Cây (Tree) Cây (Tree) Nguyễn Phương TháiBộ 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 trTemplate rootclass Node { Item data; List children; A} B C DNode* 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 trtemplate rootclassNode{ A Itemdata; Node*firstChild; Node*nextSibling; B C D};Node* root; E F GDuy câyDuyệ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 trTemplatePreorder(Node*root){ visit(root); foreachchildr 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 sauTemplatePostorder (Node*root){ foreachchildr ofroot do Postorder (r); visit(root);} Cây nhị phântemplate 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ânCâ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 ProblemBà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 != NULLMin (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ử 11Phé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 52 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 ...