CHƯƠNG I: TỔNG QUAN VỀ CẤU TRÚC CÂY I. CẤU TRÚC CÂY: 1. ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM VỀ CÂY: - Cây là một đồ thị liên thông và không có chu trình đơn. - Cây đã được dùng từ năm 1857, khi nhà toán học Anh tên Arthur Cayley dùng cây để xác định những dạng khác nhau của hợp chất hóa học.
Từ đó, cây đã được dùng để giải nhiều bài toán trong nhiều lĩnh vực khác nhau trong đó cây rất hay sử dụng trong Tin học. - Cây là một tập hợp T các phần tử (gọi là nút của cây) trong đó có một nút đặc biệt gọi là nút gốc (root), các nút còn lại được chia thành những tập rời nhau T1, T2, …, Tn theo quan hệ phân cấp trong đó Ti cũng được gọi là một cây. Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i +1. Quan hệ này người ta còn gọi là quan hệ cha - con.
- Gốc của cây là một đỉnh đặc biệt, thông thường là đỉnh trên cùng. Mức của đỉnh là độ dài đường đi từ gốc đến đỉnh đó. Chiều cao của cây là số mức lớn nhất của nút có trên cây đó. * Ví dụ : Đồ thị sau là cây V 1 V V 2 3 V V V V 4 5 6 7 + Ta chọn V1 là gốc có mức 0 thì V2, V3 là những đỉnh mức 1, các đỉnhV4, V5, V6, V7 có mức 2, và chiều cao của cây là 2.
- Rừng là đồ thị mà mỗi thành phần liên thông là cây. Luan van - Một nút là một cây. Nút đó cũng gọi là gốc của cây ấy. - Bậc của một nút là số cây con của nút đó.
- Bậc của một cây là bậc lớn nhất của các nút trong cây (số cây con tối đa của một nút thuộc cây). - Cây có bậc n thì gọi là cây n-phân. Cây n-phân là cây mà mọi đỉnh có tối đa n con và có ít nhất một đỉnh có n con. - Cây n-phân đầy đủ là cây mà mọi đỉnh trong có đúng n con.
- Cây cân bằng là cây mà mọi đỉnh lá có mức là h hay h-1, trong đó h là chiều cao của cây. - Đỉnh lá là đỉnh có bậc 1 còn được gọi là lá. Thường dùng cho cây có gốc, khi đó lá là đỉnh không có con. - Nút gốc là nút không có nút cha.
- Các nút không có nút con được gọi là nút lá. - Nút nhánh là nút có bậc khác 0 và không phải là gốc. - Ta quy ước: Một cây không có nút nào được gọi là cây rỗng (null tree). - Độ dài đường đi từ gốc đến nút x: Px = số cạnh cần đi qua kể từ gốc đến x.
SƠ ĐỒ CẤU TRÚC CÂY: Luan van A Gốc Cạnh Nút C B G H D E F Lá 3. ỨNG DỤNG CẤU TRÚC CÂY: - Xây dựng các thuật toán rất có hiệu quả để định vị các phần tử trong một danh sách. - Xây dựng các mạng máy tính với chi phí rẻ nhất cho các đường điện thoại nối các máy phân tán. - Cây cũng được dùng để tạo ra các mã có hiệu quả để lưu trữ và truyền dữ liệu.
- Cấu trúc cây được ứng dụng trong các giải thuật tìm kiếm, giải thuật sắp xếp và nhiều bài toán khác. - Cây dùng để biểu diễn bài toán quyết định (cây quyết định), biểu diễn quá trình tính toán các biểu thức đại số. MỘT SỐ VÍ DỤ VỀ ĐỐI TƯỢNG CÁC CẤU TRÚC DẠNG CÂY: 4. Sơ đồ tổ chức của một công ty: Luan van BB-Electronic Corp R&D Kinh Tài Sản doanh vụ xuất Nội Quốc TV CD Amplie địa tế r Châu Mỹ Các Âu nước 4.
Mục lục một quyển sách: Student Guide Giới Điể Môi Chương trình thiệu m trường mẫu Bài Thực Thi tập hành 4. Biểu diễn biểu thức số học dưới dạng cây: x + y * (z - t) + u / v. NHẬN XÉT: - Trong cấu trúc cây không tồn tại chu trình. - Tổ chức một cấu trúc cây cho phép truy cập nhanh đến các phần tử của nó.
TÌM HIỂU CÂY NHỊ PHÂN : 1. ĐỊNH NGHĨA : - Cây nhị phân là một dạng cấu trúc cây quan trọng, mỗi nút của nó chỉ có tối đa hai nút con. - Với mỗi nút trên cây nhị phân, cây con xuất phát từ nút con trái gọi là cây con trái và cây con xuất phát từ nút con phải gọi là cây con phải của nó. Như vậy, cây nhị phân là cây có thứ tự.
MỘT SỐ DẠNG ĐẶC BIỆT CỦA CÂY NHỊ PHÂN : A A A A B B B B C C C C D D D D Luan van A A B C B C D E F G D E F G H I J A f) e) B C G D E F J g) I H - Các cây a), b), c), d) được gọi là cây nhị phân suy biến. + Cây a) được gọi là cây lệnh trái. + Cây b) được gọi là cây lệnh phải. + Cây c), d) được gọi là cây zic-zắc.
- Cây e) được gọi là cây nhị phân hoàn chỉnh. Như vậy, cây nhị phân hoàn chỉnh là cây nhị phân đầy đủ mà tất cả các lá có cùng một mức. - Cây f) có các nút tối đa ở cả mọi mức nên gọi là cây nhị phân đầy đủ cân bằng. Đó là trường hợp đặc biệt của cây nhị phân hoàn chỉnh.
Luan van - Cây g) gọi là cây gần đầy, khác với cây e) ở chỗ các nút ở mức cuối không đạt về phía trái. TÍNH CHẤT : - Trong các cây nhị phân cùng có số lượng nút như nhau thì cây nhị phân suy biến có chiều cao lớn nhất, cây nhị phân hoàn chỉnh hoặc cây nhị phân gần đầy có chiều cao nhỏ nhất, loại cây này cũng là cây có dạng cân đối nhất. - Số lượng tối đa các nút mức k (k≥1) trên cây nhị phân là 2k-1. - Số lượng tối đa các nút trên cây nhị phân độ cao h là 2h-1 (h≥1).
Chứng minh : 2) Chứng minh bằng quy nạp : Ta biết : - Ở mức 1 : k=1, cây nhị phân có tối đa 1=20 nút. - Ở mức 2 : k=2, cây nhị phân có tối đa 2=21 nút. Giả sử kết quả đúng với mức k-1, nghĩa là ở mức này cây nhị phân có tối đa là 2k-2 nút. Mỗi nút ở mức k-1 sẽ có tối đa hai con, do đó 2k-2 nút ở mức k-1 sẽ cho : 2k-2 * 2=2k-1 nút tối đa ở mức k (Tính chất 2 được chứng minh).
3) Ta biết rằng chiều cao của cây là số mức lớn nhất có trên cây. Theo 2) ta suy ra số nút tối đa có trên cây nhị phân với chiều cao h là : 20 + 21 + 22 +. Luan van CHƯƠNG II: CÂY NHỊ PHÂN TÌM KIẾM I. MỘT SỐ KHÁI NIỆM: - Cây nhị phân tìm kiếm (Binary Search Tree) là một cấu trúc dữ liệu rất thuận lợi cho bài toán tìm kiếm.
- Cây nhị phân tìm kiếm là cây nhị phân trong đó dữ liệu được gán với các nút và dữ liệu được sắp xếp theo khóa sao cho khóa tại mỗi nút của cây lớn hơn khóa của các nút cây con bên trái và nhỏ hơn hoặc bằng khóa của các nút cây con bên phải. - Nếu số nút trên cây là N thì chi phí tìm kiếm trung bình chỉ khoảng log2N. - Cây tìm kiếm ứng với n khóa k1, k2, …, kn là cây nhị phân mà mỗi nút đều được gán một khóa sao cho với mỗi nút k: + Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút k. + Mọi khóa trên cây con phải đều lớn hơn khóa trên nút k.
- Cây nhị phân tìm kiếm là một cấu trúc dữ liệu cơ bản được sử dụng để xây dựng các cấu trúc dữ liệu trừu tượng hơn như các tập hợp, đa tập hợp, các dãy kết hợp. SƠ ĐỒ CÂY NHỊ PHÂN TÌM KIẾM: 44 Cây con Cây con trái phải 18 88 13 37 59 10 8 15 23 40 55 71 Luan van III. CẤU TRÚC DỮ LIỆU: Typedef struct NODE { int data; NODE* left; NODE* right; }; Typedef struct NODE* TREE; TREE root; IV. CÁC THAO TÁC TRÊN CÂY NHỊ PHÂN TÌM KIẾM: 1.
Khởi tạo cây Binary Search Tree: 1. Khởi tạo cây Binary Search Tree: Cho con trỏ quản lý địa chỉ nút gốc về con trỏ NULL. void init (Node &root) { root = NULL; } 1. Tạo Node: Node* GetNode (int x) { p = new Node; if (p!= NULL) { p→ left = NULL; Luan van p→ right = NULL; p→ data = x; } return (p); } 1.
Tạo cây nhị phân tìm kiếm: - Ta có thể tạo cây nhị phân tìm kiếm bằng cách lặp lại quá trình thêm một phần tử vào một cây rỗng. void creatTree (Tree &root) { int x, n; cout << “ nhap n= ”; cin>> n; for (int i=1; i<=n; i++) { cout << “ nhap gia tri: ”; cin>> x; insertTree (root.x); } } - Ví dụ về tạo cây nhị phân tìm kiếm: 25 37 10 18 29 50 3 1 6 5 12 20 35 13 32 41 25 10 37 Luan van 2. Duyệt cây nhị phân tìm kiếm: - Khi một cây nhị phân tìm kiếm được tạo ra, tất cả các nút có thể được duyệt theo thứ tự giữa nhờ duyệt đệ quy cây con bên trái, in nút đang duyệt, rồi duyệt đệ quy cây con bên phải, tiếp tục làm như vậy với mỗi nút của cây trong quá trình đệ quy. Với mọi cây nhị phân, cây có thể được duyệt theo thứ tự trước hoặc theo thứ tự sau, cả hai cách đều hữu dụng với cây nhị phân tìm kiếm.
- Phép duyệt có độ phức tạp là Ω(n), vì nó phải duyệt qua tất cả các nút. Độ phức tạp trên cũng là O(n). - Khi duyệt theo thứ tự giữa, trình tự các nút duyệt qua sẽ cho ta một dãy các nút theo thứ tự tăng dần của khóa. Duyệt theo thứ tự trước (Node - Left - Right): Duyệt nút gốc, duyệt cây con bên trái, duyệt cây con bên phải.
Duyệt theo thứ tự giữa (Left - Node - Right): Duyệt cây con bên trái, duyệt nút gốc, duyệt cây con bên phải. Duyệt theo thứ tự sau (Left - Right - Node): Duyệt cây con bên trái, duyệt cây con bên phải, duyệt nút gốc. void LRN (TREE root) { if (root!=NULL) { LRN (root→ left); LRN (root→ right); cout << root→ data<< “ “; } Luan van } 3. Tìm một phần tử x trong cây: Giải thuật tìm kiếm: + Đầu vào: Cây nhị phân tìm kiếm T và khóa K.