Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 4: Cây - Nguyễn Khánh Phương
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Cấu trúc dữ liệu và thuật toán
Nguyễn Khánh Phương
Computer Science department
School of Information and Communication technology
E-mail: [email protected].vn
Nội dung khóa học
Chương 1. Các khái niệm cơ bản
Chương 2. Các sơ đồ thuật toán
Chương 3. Các cấu trúc dữ liệu cơ bản
Chương 4. Cây
Chương 5. Sắp xếp
Chương 6. Tìm kiếm
Chương 7. Đồ thị
2
TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI
VIỆN CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG
Chương 4. Cây
Nguyễn Khánh Phương
Computer Science department
School of Information and Communication technology
E-mail: [email protected].vn
Nội dung
1. Định nghĩa và các khái niệm
2. Biểu diễn cây
3. Duyệt cây
4. Cây nhị phân
Become Rich
Force Others
to be Poor
Stock
Fraud
Rob
Banks
4
Nội dung
1. Định nghĩa và các khái niệm
2. Biểu diễn cây
3. Duyệt cây
4. Cây nhị phân
Become Rich
Force Others
to be Poor
Stock
Fraud
Rob
Banks
5
1. Định nghĩa và các khái niệm
1.1. Định nghĩa
1.2. Các thuật ngữ
1.3. Cây có thứ tự (Ordered tree)
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
6
1. Định nghĩa và các khái niệm
1.1. Định nghĩa
1.2. Các thuật ngữ
1.3. Cây có thứ tự (Ordered tree)
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
7
1.1. Định nghĩa
Cây gồm một tập các nút, có 1 nút đặc biệt gọi là gốc (root) và các
cạnh nối các nút.
Nút gốc
Dusty
nút
Honey B ear
B randy
B runhilde
T erry
Coyote
Nugget
Gill
T ansey
T weed
Zoe
Crocus
Primrose
Nous
B elle
nút
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
8
Cây: Định nghĩa đệ quy
• Bước cơ sở:
– Cây rỗng: cây không có nút nào
– Cây có 1 nút r : nút r được gọi là gốc của cây
• Bước đệ quy:
– Giả sử T1,T2,...,Tk là các cây với gốc tương ứng là r1,r2,...,rk
– Ta có thể xây dựng cây mới bằng cách đặt nút r làm cha (parent) của các nút
r1,r2,....,rk :
• Trong cây mới này: r là gốc; 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.
Gốc (Root)
r
r2
rk
r1
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
T1
T2
Tk
9
Các ứng dụng của cây
• Lịch thi đấu
• Cây gia phả
• Cây thư mục
• Cấu trúc của 1 quyển sách
• Cây biểu thức
• Sơ đồ phân cấp của 1 cơ quan
• ….
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
Các ứng dụng của cây: Biểu đồ lịch thi đấu
• Trong đời thường, cây thường được sử dụng để mô tả lịch
thi đấu của các giải thể thao theo thể thức đầu loại trực tếp
France
France
Spain
Brazil
France
Italia
Brazil
Italia
UK
Germany
Italia
Germany
Ukraine
Italia
Argentina
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
Các ứng dụng của cây: Cây gia phả
• Cây gia phả của các nhà toán học dòng họ Bernoulli
Nikolaus
1623-1708
Johan I
1667-1748
Nikolaus
1662-1716
Jacob I
1654-1705
Nikolaus II
1695-1726
Daniel
1700-1782
Johan II
1710-1790
Nikolaus I
1687-1759
Johan III
1746-1807
Jacob II
1759-1789
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
Các ứng dụng của cây: Cây thư mục
• Cây thư mục
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
Các ứng dụng của cây: Mục lục 1 quyển sách
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
Các ứng dụng của cây: Cây gia phả ngược (Ancestor Tree)
• Mỗi người đều có bố mẹ:
Ví dụ: Chiến có cha mẹ là: Thanh và Mai
Chiến
Thanh
Mai
Minh
Thành
Giang
Lan Anh
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
Các ứng dụng của cây: Cây biểu thức
1/3 + 6*7 / 4
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
Các ứng dụng của cây: Sơ đồ tổ chức của cơ quan
Công ty máy tính MU
Bộ phận sản xuất
Laptops
Nghiên cứu và phát triên (R&D)
Bộ phận bán hàng
Mỹ
Quốc tế
Châu Á
Desktops
Châu Âu
Canada
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
1. Định nghĩa và các khái niệm
1.1. Định nghĩa
1.2. Các thuật ngữ
1.3. Cây có thứ tự (Ordered tree)
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
18
1.2. Các thuật ngữ
• Nút (node)
• Gốc (Root)
• Lá (leaf)
• Con (child)
• Cha (Parent)
• Tổ tiên (Ancestors)
• Hậu duệ (Descendants)
• Anh em (Sibling)
• Nút trong (Internal node)
• Chiều cao (Height)
• Chiều sâu (Depth)
NGUYỄN KHÁNH PHƯƠNG
Bộ môn KHMT – ĐHBK HN
1.2. Các thuật ngữ
• Gốc: nút không có cha (ví dụ: nút A)
• Anh em: nút có cùng cha (ví dụ: B, C, D là anh em; I, J, K là anh em; E và F là anh
em; G và H là anh em)
• Nút trong: nút có ít nhất 1 con (ví dụ: các nút màu xanh dương: A, B, C, F)
• Nút ngoài (lá ): nút không có con (ví dụ: các nút xanh lá: E, I, J, K, G, H, D)
• Tổ tiên của 1 nút: là các nút cha / ông bà / cụ.. của nút đó.
• Hậu duệ của 1 nút: là các nút con/cháu/chắt… của nút đó
• Cây con của 1 nút: là cây có gốc là con của nút đó
Ví dụ:
A
Con của B: E, F
Cha của E: B
Tổ tiên của F: B, A
Hậu duệ của B: E, F, I, J, K
B
C
D
E
F
J
G
H
Cây con của nút A
I
K
Tải về để xem bản đầy đủ
182 trang
16860
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 4: Cây - Nguyễn Khánh Phương", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_thuat_toan_chuong_4_cay_nguyen.pdf
