Xem mẫu
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
nguon tai.lieu . vn