Xem mẫu
- Chương 4 : CÂY NHỊ PHÂN
Giảng viên : Nguyễn Minh Thành
Email : thanhnm.itc@itc.edu.vn
- Nội Dung
I. Cấu Trúc Cây
1. Khái việm và ví dụ
2. Định nghĩa
3. Các tính chất
4. Các thuật ngữ liên quan
II. Cây Nhị Phân
1. Định nghĩa
2. Cách thức lưu trữ cây
III. Cây Nhị Phân Tìm Kiếm
1. Ý nghĩa
2. Định nghĩa
3. Ví dụ
4. Cài đặt
2
- I. Cấu Trúc Cây
1. Khái việm và ví dụ
2. Định nghĩa
3. Các tính chất
4. Các thuật ngữ liên quan
3
- I.1 Khái Niệm và Ví Dụ
Ví dụ 1: bài toán đưa thư
Trên thế giới hơn có ~ 10 tỉ người
Thành, khoa CNTT, CĐ CNTT, TpHCM, Việt Nam.
Cách tìm ra “Thành” nhanh nhất ?
Sử dụng mảng ?
Sứ dụng danh sách liên kết (linked list) ?
4
- I.1 Khái Niệm và Ví Dụ
Ví dụ 1: bài toán đưa thư
5
- I.1 Khái Niệm và Ví Dụ
Cây là một cấu trúc dữ liệu quan trọng để biểu diễn và lưu trữ dữ
liệu trong bộ nhớ chính và mang tính “kế thừa”
Tính kế thừa :
Các node con phải liên quan đến node cha
Các cây mang tính kế thừa :
Cây gia phả
Cây phân cấp các loài (sinh vật)
6
- I.2 Định Nghĩa
Một cây (Tree) là
Một tập hợp các phần tử, gọi là các node p1,p2,…,pN
Nếu N=0, cây gọi là cây rỗng (NULL)
Nếu N>0 :
Tồn tại duy nhất một node pk duy nhất gọi là gốc cây
Các nút còn lại được chia thành m tập không giao nhau :
T1, T2, … TM
Mỗi Ti cây con của cây
7
- I.2 Định Nghĩa
8
- I.2 Định Nghĩa
9
- I.2 Định Nghĩa
10
- I.3 Các Tính Chất Của Cây
Nút gốc không có nút cha
Mỗi nút khác chỉ có 1 nút cha
Mỗi nút có thể có nhiều nút con
Không có chu trình
11
- I.4 Các Thuật Ngữ Liên Quan
Node : là 1 phần tử trong cây. Mỗi node chứa 1 dữ liệu bất kỳ
Nhánh : là đoạn nối giữa 2 nút
Node cha
Node con
Nút anh em : là những node có cùng nút cha
Bậc của 1 node pi : là số node con của pi
Tìm bậc của các node trên cây T trong ví dụ trên ?
Node gốc : node không có node cha
Node lá (node ngoài) : node có bậc = 0 (không có node con)
Node trong (node nhánh) : là node có node con và node cha
Cây con
Trong cây T có bao nhiêu cây con ?
12
- I.4 Các Thuật Ngữ Liên Quan
Bậc của cây : là bậc lớn nhất của các node trong cây
Bậc () = max { bậc(pi) / pi }
Tìm bậc của cây T ?
Đường đi (path) giữa node pi và pj : là dảy các nút liên tiếp từ pi
đến pj sao cho giữa 2 node kề nhau đều có nhánh.
Độ dài đường đi từ node pi và pj : là số nhánh cần đi qua từ pi đến
pj .
13
- I.4 Các Thuật Ngữ Liên Quan
Mức (level)
Mức (p)=0 nếu p là gốc
Mức (p) = mức (cha(p)) +1 nếu p không phải gốc
Chiều cao của cây (hT): đường đi dài nhất từ node gốc đến node
lá
hT = max { path (gốc, pi) / pi là node lá }
Tính chiều cao của cây T trong ví dụ trên
14
- I.4 Các Thuật Ngữ Liên Quan
Mức (level)
Mức (p)=0 nếu p là gốc
Mức (p) = mức (cha(p)) +1 nếu p không phải gốc
Chiều cao của cây (hT): đường đi dài nhất từ node gốc đến node
lá
hT = max { path (gốc, pi) / pi là node lá }
Tính chiều cao của cây T trong ví dụ trên
15
- II. Cây Nhị Phân
1. Định nghĩa
2. Cách thức lưu trữ cây
16
- II.1 Định Nghĩa
Cây Nhị Phân là cây có bậc = 2
Bậc của các nút trong
- II.1 Định Nghĩa
Độ cao của cây nhị phân có N node:
hT(max) = N
hT(min) = [log2N] + 1
18
- II.2 Lưu Trữ Cây
Có 2 cách tổ chức cây nhị phân :
Lưu trữ bằng mảng
Lưu trữ bằng con trỏ cấu trúc
Chi tiết ở phần Cây Nhị Phân Tìm Kiếm
19
- III. Cây Nhị Phân Tìm Kiếm
1. Định nghĩa
2. Ý nghĩa
3. Cài đặt
20
nguon tai.lieu . vn
