Tài liệu Cấu trúc dữ liệu di động chuong 4

ĐẠI HỌC QUỐC GIA TPHCM TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT CHƯƠNG IV CẤU TRÚC CÂY Nguyễn Trọng Chỉnh 1 [email protected] CẤU TRÚC CÂY ❖GIỚI THIỆU ❖CÂY NHỊ PHÂN ❖CÂY NHỊ PHÂN TÌM KIẾM ❖CÂY NHỊ PHÂN CÂN BẰNG 2 GIỚI THIỆU ❖ĐỊNH NGHĨA CÂY - - Cây là một tập hợp các phần tử, gọi là node, liên kết với nhau bằng các cạnh có hướng. Trong đó: Có một node đặc biệt được gọi là gốc (root) Hướng của cạnh đi từ node A đến node B biểu diễn quan hệ A là cha (parent) của B hay B là con (child) của A. Các node có cùng node cha được gọi là các node anh em (sibling) Ngoài node gốc, cây có thể có nhiều node con khác. Mỗi node con là một cây con (subtree). 3 GIỚI THIỆU ❖ĐỊNH NGHĨA CÂY Ví dụ: - A là gốc của cây T - A là cha của B, G, H - B, G, H là các anh em - B, H, .. là gốc của mỗi cây con của T - G là gốc của một cây con chỉ gồm 1 node gốc. T A G B C D F H E I J K 4 GIỚI THIỆU ❖MỘT SỐ KHÁI NIỆM - Bậc của một nút: là số cây con của nút đó. Ví dụ: Bậc của B là 4, bậc của G là 0. - Bậc của một cây: là bậc lớn nhất của các node trong cây - Node gốc: là node không có node cha - Node lá: là node không có node con, hay có bậc bằng 0. Ví dụ: node G, node I. - Node trung gian (node trong): là node không phải node lá. 5 GIỚI THIỆU ❖MỘT SỐ KHÁI NIỆM - Mức của một node: ▪ Mức của node gốc là 1 ▪ Giả sử node X có mức là i, nếu Y là con của X thì mức của Y là i+1. - Độ dài đường đi từ gốc đến node X: là số cạnh cần đi từ gốc đến X. - Nếu có đường đi từ X đến Y thì X được gọi là tiền bối (ancestor) của Y hay Y là hậu duệ (descendant) của X 6 GIỚI THIỆU ❖MỘT SỐ KHÁI NIỆM - Chiều cao của node X (hX) là số node trên đường đi dài nhất từ X đến các node lá của nó. - Chiều cao của cây (h) là chiều cao của node gốc. - Độ sâu của một node X (dX) là độ dài đường đi từ node gốc đến X cộng thêm 1 7 GIỚI THIỆU ❖MỘT SỐ KHÁI NIỆM T h=4 mức 1 A mức 2 G H E I mức 3 mức 4 B C D F h=3 J K 8 GIỚI THIỆU ❖BIỂU DIỄN CÂY Dùng mảng (danh sách đặc): - Đánh số thứ tự các node trên cây. - Nếu node thứ i là cha của node thứ j thì giá trị của phần tử thứ j trong mảng sẽ bằng i. - Nếu node thứ i là node gốc, giá trị của phần tử thứ i trong mảng sẽ bằng -1. 9 GIỚI THIỆU ❖BIỂU DIỄN CÂY Dùng mảng (danh sách đặc): Ví dụ: cho cây 0 A 6 1 G B 2 C 3 D 7 H 4 5 8 9 F E I J 10 K Biểu diễn bằng mảng là: -1 0 1 1 1 1 0 0 7 7 9 10 GIỚI THIỆU ❖BIỂU DIỄN CÂY Dùng danh sách liên kết: - Mỗi node sẽ có một danh sách chứa địa chỉ của các node con của nó. A A … B G B C D F H E I G ……………….. J H ……………….. K 11 GIỚI THIỆU ❖DUYỆT CÂY THEO THỨ TỰ Duyệt theo thứ tự trước (pre-order): Giả sử node gốc R có n node con T1,.., Tn, thực hiện: - Xử lý node gốc R - Duyệt theo thứ tự trước cho node T1 - Duyệt theo thứ tự trước cho node T2 - … - Duyệt theo thứ tự trước cho node Tn 12 GIỚI THIỆU ❖DUYỆT CÂY THEO THỨ TỰ Duyệt theo thứ tự sau (post-order): Giả sử node gốc R có n node con T1,.., Tn, thực hiện: - Duyệt theo thứ tự sau cho node T1 - Duyệt theo thứ tự sau cho node T2 - … - Duyệt theo thứ tự sau cho node Tn - Xử lý node gốc R 13 GIỚI THIỆU ❖DUYỆT CÂY THEO THỨ TỰ Duyệt theo thứ tự giữa (in-order): Giả sử node gốc R có n node con T1,.., Tn, thực hiện: - Duyệt theo thứ tự giữa cho node T1 - Xử lý node gốc R - Duyệt theo thứ tự giữa cho node T2 - … - Duyệt theo thứ tự giữa cho node Tn 14 CÂY NHỊ PHÂN ❖ĐỊNH NGHĨA Cây nhị phân là cây mà mỗi node có tối đa hai cây con. Hai cây con này được đặt tên lần lượt là cây con trái và cây con phải. A B C D E F 15 CÂY NHỊ PHÂN ❖ĐỊNH NGHĨA Cây nhị phân đầy đủ là cây nhị phân có các node lá có cùng mức và mỗi node trung gian có đúng 2 node con A B D C E F G 16 CÂY NHỊ PHÂN ❖ĐỊNH NGHĨA Cây nhị phân hoàn chỉnh có chiều cao n là cây nhị đầy đủ với chiều cao n – 1 và các nút lá lệch trái nhất tại mức n A B C D H E I F G J 17 CÂY NHỊ PHÂN ❖TÍNH CHẤT - Số node tại mức i không quá 2i-1 - Số node của cây T không quá 2h-1 với h là chiều cao của cây T. - Gọi n là số node của cây T, h là chiều cao của cây T, có h  log2(n + 1) 18 CÂY NHỊ PHÂN ❖TỔ CHỨC DỮ LIỆU struct TenDulieu { // dữ liệu quản lý }; struct Node { TenDulieu key; Node *pLeft, *pRight; }; typedef Node * TREE; ..... ..... 19 CÂY NHỊ PHÂN ❖CÁC THAO TÁC CƠ BẢN - Tạo cây rỗng Tạo một node có khóa x Duyệt cây Tạo cây từ kết quả duyệt. 20