Bài giảng Cấu trúc dữ liệu và thuật toán - Chương 4: Cây - 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
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
2
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
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
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
3
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
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ả.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
4
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Cấu trúc đệ qui của cây
r
r2
rk
r1
Tk
T2
T1
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
5
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
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
• ...
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
6
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
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
Pháp
Pháp
Tây ban nha
Brazin
Anh
Brazin
Đức
Italia
Đức
Ucrain
Italia
Ahentina
Italia
Italia
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
7
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
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
Nikolaus II
1695-1726
Daniel
1700-1782
Johan II
1710-1790
Nikolaus I
1687-1759
Johan III
1746-1807
Jacob II
1759-1789
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
8
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Cây phân cấp quản lý hành chính
Ban Giám đốc
Phò ng
Tổ chức
Phò ng
Tài vụ
Phò ng
Kinh doanh
Phò ng
Kế hoạch
Phò ng
Hành chí nh
TP
Văn thư
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
9
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Cây thư mục
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
10
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Cây mục lục sách
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
11
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Cây gia phả ngược (Ancestor Tree)
Cây phả hệ ngược: mỗi người đều có bố mẹ. Cây
này là cây nhị phân (binary tree).
Thùy Hương
Quang Dũng
Thúy Cải
Trung Kiên
Hoàng Cúc Quang Thái
Bích Liên
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
12
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Cây biểu thức (Expression Tree)
1/3 + 6*7 / 4
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
13
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Cây phân hoạch tập hợp
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Tập con các số lẻ:
Tập con các số chẵn:
{1, 3, 5, 7, 9}
{ 2, 4, 6, 8, 10}
Tập con các số nguyên tố:
Tập con số hoàn hảo:
{1, 9}
{ 2, 4, 8, 10}
{ 3, 5, 7 }
{ 6 }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
14
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
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
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
15
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
4.1.2. Các thuật ngữ chính
• 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 - hight
• Chiều sâu - depth
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
16
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Các thuật ngữ chính
•
Nếu n1, n2, . . . , nk là dãy nút trên cây sao cho ni là cha của ni+1 với 1 i < k, thì dãy
này được gọi là đường đi (path) từ nút n1 tới nút nk. Độ dài (length) của đường đi là
bằng số lượng nút trên đường đi trừ bớt 1. Như vậy đường đi độ dài 0 là đường đi từ
một nút đến chính nó.
•
•
Nếu có đường đi từ nút a tới nút b, thì a được gọi là tổ tiên (ancestor) của b, còn b
được gọi là hậu duệ (descendant) của a.
Tổ tiên (hậu duệ) của một nút khác với chính nó được gọi là tổ tiên (hậu duệ) chính
thường (proper). Trong cây, gốc là nút không có tổ tiên chính thường và mọi nút khác
trên cây đều là hậu duệ chính thường của nó.
•
•
•
•
Một nút không có hậu duệ chính thường được gọi lá lá (leaf).
Các nút có cùng cha được gọi là anh em (sibling).
Cây con (subtree) của một cây là một nút cùng với tất cả các hậu duệ của nó.
Chiều cao (height) của nút trên cây là bằng độ dài của đường đi dài nhất từ nút đó
đến lá cộng 1. Chiều cao của cây (height of a tree) là chiều cao của gốc. Độ sâu/mức
(depth/level) của nút là bằng 1 cộng với độ dài của đường đi duy nhất từ gốc đến nó.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
17
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Thuật ngữ
nút
nodes
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
18
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Thuật ngữ
Nút cha
parent node
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
19
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Thuật ngữ
cha
con
child
parent
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
20
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Thuật ngữ
con
cha
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
21
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Thuật ngữ
lá - leaf
gốc - root
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
22
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Thuật ngữ
câ y con - subtree
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
23
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Thuật ngữ
câ y con
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
24
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Thuật ngữ
câ y con
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
25
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Các thuật ngữ với cây có gốc
root, ancestor
a
internal node
(không là lá)
parent
d
h
b
nút
c
sibling
e
f
leaf (không có con)
g
child
child
j
i
e, i, k, g, h
là lá (leaves)
descendent
k
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
26
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Đường đi trên cây
Có duy nhất 1 đường đi từ
một nút đến một nút là
hậu duệ của nó.
Từ cha đến con và đến
các nút hậu duệ.
a
d
b
c
Path 1
Path 2
f
e
h
g
i
Path 1: { a, b, f, j }
Path 2: { d, i }
j
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
27
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Độ cao (height) và độ sâu/mức (depth/level)
độ sâu 1
độ cao h = 5
7
độ cao = 4
độ sâu 2
độ sâu 3
3
10
4
độ cao = 3
8
12
11
2
độ sâu 4
1
h = 2
6
5
Độ cao của cây là 5
độ sâu 5
9
độ cao h=1
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
28
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
How We View a Tree
Nature Lovers View
Computer Scientists View
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
29
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Bậc (Degree)
Số lượng con của nút
x được gọi là
degree = 3
7
bậc (degree) của x.
3
10
4
degree = 1
degree = 0
8
9
12
11
2
1
6
5
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
30
1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
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
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
31
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
4.1.3. Cây có thứ tự - Ordered Tree
• Thứ tự của các nút
• Các con của một nút thường được xếp thứ tự từ trái sang phải. Như
vậy hai cây trong hình sau đây là khác nhau, bởi vì hai con của nút
a xuất hiện trong hai cây theo thứ tự khác nhau:
a
a
c
b
• Cây với các nút được xếp thứ tự được gọi là cây có thứ tự. Ta sẽ xét
chủ yếu là cây có thứ tự. Vì vậy, tiếp theo thuật ngữ cây là để chỉ
cây có thứ tự. Khi muốn khẳng định là không quan tâm đến thứ tự,
ta sẽ phải nói rõ là cây không có thứ tự.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
32
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Xếp thứ tự các nút
• Ta có thể xếp thứ tự các nút của cây theo nhiều cách. Có ba
thứ tự quan trọng nhất, đó là Thứ tự trước, Thứ tự sau và
Thứ tự giữa (Preorder, Postorder, và Inorder)
• Các thứ tự này được định nghĩa một cách đệ qui như sau
– Nếu cây T là rỗng, thì danh sách rỗng là danh sách theo thứ
tự trước, thứ tự sau và thứ tự giữa của cây T.
– Nếu cây T có một nút, thì nút đó chính là danh sách theo
thứ tự trước, thứ tự sau và thứ tự giữa của cây T.
– Trái lại, giả sử T là cây có gốc r với các cây con là T1, T2,...,
Tk.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
33
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Duyệt theo thứ tự trước - Preorder Traversal
r
r2
rk
r1
Tk
T2
T1
• Thứ tự trước (hay duyệt theo thứ tự trước - preorder
traversal) của các nút của T là:
– Gốc r của T,
– tiếp đến là các nút của T1 theo thứ tự trước,
– tiếp đến là các nút của T2 theo thứ tự trước,
– ...
– và cuối cùng là các nút của Tk theo thứ tự trước.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
34
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Duyệt theo thứ tự sau - Postorder Traversal
r
r2
rk
r1
Tk
T2
T1
• Thứ tự sau của các nút của cây T là:
– Các nút của T1 theo thứ tự sau,
– tiếp đến là các nút của T2 theo thứ tự sau,
– ...
– các nút của Tk theo thứ tự sau,
– sau cùng là nút gốc r.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
35
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Duyệt theo thứ tự giữa - Inorder Traversal
r
r2
rk
r1
Tk
T2
T1
• Thứ tự giữa của các nút của cây T là:
– Các nút của T1 theo thứ tự giữa,
– tiếp đến là nút gốc r,
– tiếp theo là các nút của T2, . . . , Tk, mỗi nhóm nút được xếp theo thứ tự
giữa.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
36
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Thuật toán duyệt theo thứ tự trước - Preorder Traversal
void PREORDER ( nodeT r )
{
(1) Đưa ra r;
(2) for (mỗi con c của r, nếu có, theo thứ tự từ trái sang) do
PREORDER(c);
a
}
c
d
e
h
j
• Ví dụ: Thứ tự trước của các đỉnh của cây trên hình vẽ là
a, b, c, e, h, i, f, j, d, g
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
37
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Thuật toán duyệt theo thứ tự sau - Postorder Traversal
• Thuật toán duyệt theo thứ tự sau thu được bằng cách đảo ngược hai thao
tác (1) và (2) trong PREORDER:
void POSTORDER ( nodeT r )
{
for (mỗi con c của r, nếu có, theo thứ tự từ trái sang) do
POSTORDER(c)
a
Đưa ra r;
}
c
d
e
h
j
• Ví dụ: Dãy các đỉnh được liệt kê theo thứ tự sau của cây trong hình vẽ là:
b, h, i, e, j, f, c, g, d, a
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
38
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Thuật toán duyệt theo thứ tự giữa - Inorder Traversal
a
void INORDER (nodeT r )
{
if ( r là lá ) Đưa ra r;
c
d
else
e
{
INORDER(con trái nhất của r);
Đưa ra r;
h
j
for (mỗi con c của r, ngoại trừ con trái nhất, theo thứ tự từ trái sang) do
INORDER(c);
}
}
• Ví dụ: Dãy các đỉnh của cây trong hình vẽ được liệt kê theo thứ tự giữa:
b, a, h, e, i, c, j, f, g, d
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
39
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Xếp thứ tự các nút
a
• Để nhớ cách đưa ra các nút theo ba thứ tự
vừa trình bày hãy hình dung là ta đi vòng
c
d
quanh bên ngoài cây bắt đầu từ gốc, ngược
chiều kim đồng hồ và sát theo cây nhất.
Chẳng hạn, đường đi đó đối với cây trong
các ví dụ đã xét trên là như sau:
e
h
j
• Đối với thứ tự trước, ta đưa ra nút mỗi khi đi qua nó.
• Đối với thứ tự sau, ta đưa ra nút khi qua nó ở lần cuối trước khi
quay về cha của nó.
• Đối với thứ tự giữa, ta đưa ra lá ngay khi đi qua nó, còn những nút
trong được đưa ra khi lần thứ hai được đi qua.
• Chú ý rằng các lá được xếp thứ tự từ trái sang phải như nhau trong cả
ba cách sắp xếp.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
1/28/2013
40
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Tải về để xem bản đầy đủ
65 trang
17300
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 Đức Nghĩa", để 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
