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