Đang chuẩn bị liên kết để tải về tài liệu:
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. | Q 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ọ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 là các gốc n là 1 nút và n có quan hệ cha - con với n1 n2 . nk thì lúc đó 1cây mới T sẽ được tạo lập vớ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ú ý Hình 5.1 Trang 1 Q 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 gọi là cấp degree của 1 nút đó. Nút có cấp bằng 0 gọi là lá leaf hay nút tận cùng termina node . Nút không phải là lá được gọi là nút nhánh branch node . Cấp cao nhất của nút trên cây được gọi là cấp của cây đó. Ví dụ với cây ở hình 5.2 ở đây các chữ A B C .tự0 ng trưng cho phần thông tin 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ác nú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à