Bài giảng "Cấu trúc dữ liệu và thuật toán - Chương 4: Cây" cung cáp cho người học các kiến thức: Định nghĩa và các khái niệm, cây nhị phân, các ứng dụng. Đây là một tài liệu hữu ích dành cho các bạn sinh viên ngành Công nghệ thông tin và những ai quan tâm dùng làm tài liệu học tập và nghiên cứu. | Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 4 - Nguyễn Đức Nghĩa Chương 4 CÂY Nội dung . Định nghĩa và các khái niệm . Cây nhị phân . Các ứng dụng CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 2 . Định nghĩa và khái niệm . Định nghĩa . Các thuật ngữ . Cây có thứ tự . Cây có nhãn . ADT cây CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 3 . Định nghĩa cây Cây bao gồm các nút, có một nút đặc biệt được gọi là gốc (root) và các cạnh nối các nút. Cây được định nghĩa đệ qui như sau: Định nghĩa cây: Basic Step: Một nút r là cây và r được gọi là gốc của cây này. Recursive Step: Giả sử T1,T2,.,Tk là các cây với gốc là r1,r2,.,rk. Ta có thể xây dựng cây mới bằng cách đặt r làm cha (parent) của các nút r1,r2,., rk . Trong cây này r là gốc và T1, T2, . . . , Tk là các cây con của gốc r. Các nút r1, r2, . . . , rk được gọi là con (children) của nút r. Chú ý: Nhiều khi để phù hợp ta cần định nghĩa cây rỗng (null tree) là cây không có nút nào cả. CẤU TRÚC DỮ VÀ THUẬT TOÁN 4 1/28/2013 NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT Cấu trúc đệ qui của cây r r1 r2 rk T1 T2 Tk CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 5 1/28/2013 NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT Cây trong thực tế ứng dụng • Biểu đồ lịch thi đấu • Cây gia phả • Biểu đồ phân cấp quản lý hành chính. • Cây thư mục • Cấu trúc của một quyển sách • Cây biểu thức • Cây phân hoạch tập hợp • . CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 6 Cây lịch thi đấu Trong đời thường cây rất hay được sử dụng để diễn tả lịch thi đấu của các giải thể thao theo thể thức đấu loại trực tiếp, chẳng hạn vòng 2 của World Cub Pháp Pháp Tây ban nha Pháp Brazin Brazin Anh Italia Đức Đức Ucrain Italia Italia Italia Ahentina CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 7 1/28/2013
