Chương 4 CÂY Bài giảng của PGS.TS. NGUYỄN ĐỨC NGHĨA Khoa học Máy tính Đại học Bách khoa Hà nội Nội dung 4.1. Định nghĩa và các khái niệm 4.2. Cây nhị phân 4.3. Các ứng dụng 10/13/2020 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN KHMT - DHBKHN 3 4.1. Định nghĩa và khái niệm 4.1.1. Định nghĩa 4.1.2. Các thuật ngữ 4.1.3. Cây có thứ tự 4.1.4. Cây có nhãn 4.1.5. ADT cây 10/13/2020 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN KHMT - DHBKHN 4 4.1.1. Đị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ả. 10/13/2020 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN KHMT - DHBKHN 5 Cấu trúc đệ qui của cây 10/13/2020 rk Tk T2 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN KHMT - DHBKHN 6 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 ... 10/13/2020 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN KHMT - DHBKHN 7 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 Tây ban nha Brazin Anh Đức Ucrain Italia Ahentina 10/13/2020 Pháp Pháp Brazin Italia Đức Italia CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN KHMT - DHBKHN Italia 8 Cây gia phả Cây gia phả của các nhà toán dòng họ Bernoulli Nikolaus 1623-1708 Johan I 1667-1748 Nikolaus II 1695-1726 Daniel 1700-1782 Nikolaus 1662-1716 Johan II 1710-1790 Johan III 1746-1807 10/13/2020 Jacob I 1654-1705