Bài giảng Cấu trúc dữ liệu & thuật toán: Chương 4 - Nguyễn Đức Nghĩa

Chương 4 CÂY 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 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mônKHMT 2 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 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mônKHMT 3 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ả. 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 4 NGUYỄN ĐƯC NGHĨA - Bộ mônKHMT Cấu trúc đệ qui của cây r r1 r2 rk T1 T2 Tk 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 5 NGUYỄN ĐƯC NGHĨA - Bộ mônKHMT 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 • ... 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mônKHMT 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 Tây ban nha Brazin Anh Đức Ucrain Italia Ahentina Pháp Pháp Brazin Italia Đức Italia Italia 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 7 NGUYỄN ĐƯC NGHĨA - Bộ mônKHMT 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 1662-1716 Jacob I 1654-1705 NikolausII 1695-1726 Daniel 1700-1782 Johan II 1710-1790 NikolausI 1687-1759 Johan III 1746-1807 Jacob II 1759-1789 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 8 NGUYỄN ĐƯC NGHĨA - Bộ mônKHMT Cây phân cấp quản lý hành chính Ban Giám đốc Phòng Phòng Hành chính Tổ chức Phòng Phòng Tài vụ Kinh doanh Phòng Kế hoạch TP Văn thư 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mônKHMT 9 Cây thư mục 1/28/2013 CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA - Bộ mônKHMT 10 ... - tailieumienphi.vn