Cấu trúc dữ liệu và giải thuật - Chapter 5

CẤU TRÚC CÂY (TREE)I. ĐỊNH NGHĨA VÀ MỘT SỐ KHÁI NIỆM Cây là 1 cấu trúc phi tuyến, thiết lập trên 1 tập hữu hạn các phần tử mà ta gọi là “nút”, trong đó có 1 nút đặt biệt được gọi là (noot), liên kết bởi 1 quan hệ phân cấp, gọi là quan hệ cha – con. Cây có thể được định nghĩa 1 cách đệ qui như sau : 1. Một nút là 1 cây. Nút đó cũng là gốc của cây ấy. 2. Nếu T1, T2,…,Tk là các cây với n1, n2 ,…,nk lần lượt...
Nội dung trích xuất từ tài liệu:
Cấu trúc dữ liệu và giải thuật - Chapter 5 Giáo trình Cấu trúc dữ liệu Trường THCN Công - Kỹ Nghệ Ðông ÁChương V. CẤU TRÚC CÂY (TREE)I. ĐỊNH NGHĨA VÀ MỘT SỐ KHÁI NIỆM Cây là 1 cấu trúc phi tuyến, thiết lập trên 1 tập hữu hạn các phần tử mà ta gọilà “nút”, trong đó có 1 nút đặt biệt được gọi là (noot), liên kết bởi 1 quan hệ phâncấp, gọi là quan hệ cha – con. Cây có thể được định nghĩa 1 cách đệ qui như sau : 1. Một nút là 1 cây. Nút đó cũng là gốc của cây ấy. 2. Nếu T1, T2,…,Tk là các cây với n1, n2 ,…,nk lần lượt là các gốc ; n là 1 nútvà n có quan hệ cha – con với n1, n2 ,…,nk thì lúc đó 1cây mới T sẽ được tạo lậpvới n là gốc của nó. Nút được gọi là cha của n1, n2 ,…,nk ; ngược lại n1, n2 ,…,nkđược gọi là con của n. Các cây T1, T2,…,Tk được gọi là cây con (subtrees) của n. Người ta quy ước : 1 cây không có nút nào được gọi là cây rỗng. Trên hình vẽ, người ta biểu diễn cây với nút gốc ở trên và quan hệ cha – conđược thể hiện bởi 1 đoạn thẳng (giữa nút cha và nút con). Ví dụ : Chương 1 của giáo trình có cấu trúc cây. 1. Giải thuật 1.1. Cấu trúc dữ liệu và giải thuật 1.2. Ngôn ngữ diễn đạt giải thuật 1.3. Thiết kế giải thuật 1.4. Đánh giá giải thuật 1.4.1. Đặt vấn đề 1.4.2. Thời gian thực hiện trung bình 1.5. Giải thuật đệ quy 1.5.1. Ví dụ về thủ tục đệ quy 1.5.2. Chú ý Cây này có thể biển diễn như hình 5.1 Chương1 1. 1. 1. 1. 1. 1.5. 1.5. 1.5. 1.4. 1.4. Hình 5.1 Trang 1 Giáo trình Cấu trúc dữ liệu Trường THCN Công - Kỹ Nghệ Ðông Á Sau đây là 1 số khái niệm : a) Số các con của 1 nút được Agọi làcấp (degree) của 1 nút đó. Nút có cấp B C Dbằng 0 gọi là lá (leaf) hay nút tậncùng (termina node). Nút không phảilà lá được gọi là nút nhánh (branch E F G H I Jnode).Cấp cao nhất của nút trên cây đượcgọi là cấp của cây đó. Ví dụ : với cây K L Fở hình 5.2 (ở đây các chữ A, B,C,…tựơng trưng cho phần thông tin Hình 5.2(dữ liệu) ứng với mỗi nút). A là gốc ; B, C, D là con của A ; D là cha của G, H, I, J ; A có cấp bằng 3,D có cấp bằng 4. Các nút như E, F, C, G, K,…là lá. Các nút như B, D, H…là cácnút nhánh. Cây trên có cấp bằng 4. b) Gốc của cây có mức (level) bằng 1. Nếu nút cha có mức là i thì nút con có mức là i + 1. Như ở cây trên : A có mức là 1 ; B, C, D có mức là 2 ; E, F, G, I, J có mức là 3 ; K, L, M có mức là 4. c) Chiều cao (height) hay chiều sâu (depth) của 1 cây là số mức lớn nhấtcủa nút có trên cây đó. Cây ở hình 5.1 có chiều cao là 3 Cây ở hình 5.2 có chiều cao là 4 d) Nếu n1, n2 ,…,nk là dãy các nút mà ni là cha của ni+1 với 1≤ i ≤ k thì dãyđó được gọi là đường đi (path) từ n1 đến nk.Độ dài của đuờng đi (path length)bằng số nút trên đường đi đó trừ đi 1. Ví dụ với cây ở hình 5.2 : độ dài đường đitừ A đến L bằng 3, độ dài đường đi từ D tới M. e) Nếu thứ tự các cây con của 1 nút được coi trọng thì cây đang xét là câycó thứ tự (ordered tree), ngược lại là cây không có thứ tự (unordered tree). f) Đối với nút trên cây ngoài khái niệm cha, con, người ta còn có thể mởsang các khái niệm khác theo quan hệ như trong gia tộc. Ví dụ như trong hình5.2 . A, D, H … được gọi là tiền bối của L ; còn E, G, K… được gọi là hậu sinhcủa A…; các nút G, H, I, J là các nút anh em v.v… Trang 2 Giáo trình Cấu trúc dữ liệu Trường THCN Công - Kỹ Nghệ Ðông Á Chú ý. Đôi lúc, để cho tiện, hình vẽ minh hoạ của cây sẽ được thể hiện đơngiản : nút trên cây chỉ tượng trưng bằng chữ hoặc số. Ví dụ như cây ở hình 5.2, có thể minh hoạ bởi 5.3. Hoặc cây mà mỗi nútđều chứa 1 số như hình 5.4. A 14 B C D 17 21 E Ì GH I J 44 9 53 KLM ...