tailieunhanh - Khái niệm cây - Bài 9 Cây ôn thi

• 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 cung đi từ P đến C. Đỉnh P được gọi là cha của đỉnh C, và C là con P • Có đường đi duy nhất từ gốc tới mỗi đỉnh của cây. | Cây (Tree) 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 class Node { Item data; List children; } Node* root; (Xem hình vẽ) A B D C E F G root Cài đặt cây bằng hai con trỏ template class Node { Item data; Node* firstChild; Node* nextSibling; }; Node* root; A B C D G F E root 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 A B E F C 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. E F B C G D A 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 | Cây (Tree) 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 class Node { Item data; List children; } Node* root; (Xem hình vẽ) A B D C E F G root Cài đặt cây bằng hai con trỏ template class Node { Item data; Node* firstChild; Node* nextSibling; }; Node* root; A B C D G F E root 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 A B E F C 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. E F B C G D A Duyệt cây theo