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 . Cấu trúc dữ liệu và giải thuật . Ngôn ngữ diễn đạt giải thuật . Thiết kế giải thuật . Đánh giá giải thuật . Đặt vấn đề . Thời gian thực hiện trung bình . Giải thuật đệ quy . Ví dụ về thủ tục đệ quy . Chú ý Hình 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 ở đâ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 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à
