Mô tả:
slide_bài giảng cấu trúc giữ liệu và gỉai thuật 3
Giảng viên:
Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến
2
Khái niệm
Phép duyệt cây và Biểu diễn cây
Cây nhị phân và Cây nhị phân tìm kiếm
Cây AVL
Cây AA
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
3
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
4
Tree
Search tree
Binary search tree
Balanced tree
AVL tree
AA tree
Red-Black tree
…
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
5
a
b
d
i
e
j
o
c
f
k
p
q
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
g
l
h
m
n
6
Sơ đồ tổ chức
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
Cây thư mục
7
Cây (cây có gốc) được xác định đệ quy như
sau:
Tập hợp gồm 1 đỉnh là một cây. Cây này có gốc là
đỉnh duy nhất của nó.
2. Gọi T1, T2, … Tk (k ≥ 1) là các cây không cắt nhau có
gốc tương ứng r1, r2, … rk.
Giả sử r là một đỉnh mới không thuộc các cây Ti. Khi đó,
tập hợp T gồm đỉnh r và các cây Ti tạo thành một cây
mới với gốc r. Các cây T1, T2, … Tk được gọi là cây
con của gốc r.
1.
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
8
Nút gốc
r1
r2
rk
T1
T2
Tk
Cây con
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
9
Đỉnh (nút): node
Gốc: root
Node lá: leaf
Node trong: inner node/internal node
Node cha: parent
Node con: child
Đường đi: path
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
10
Nút gốc
r1
r2
rk
k1
T1
T2
k2
Tk
k3
k4
k5
Cây con
Nút lá
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
Đường đi
k6
11
Bậc: degree/order
Bậc
của node: Số con của node
Bậc của cây: bậc lớn nhất trong số các node của cây
Mức (Độ sâu): depth/level
Mức
(độ sâu) của node: Chiều dài của đường đi từ
node gốc đến node đó cộng thêm 1.
Chiều cao: height
Chiều
cao cây:
Cây
rỗng: 0
Cây khác rỗng: Mức lớn nhất giữa các node của cây
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
12
Bậc = k
Nút gốc
Bậc = 2
Độ cao = 4
r1
r2
rk
k1
T1
T2
k2
Tk
k3
k4
k5
Cây con
Nút lá
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
Đường đi
k6
13
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
14
Đảm bảo đến mỗi node trên cây chính xác một lần
một cách có hệ thống.
Nhiều thao tác xử lý trên cây cần phải sử dụng đến
phép duyệt cây.
Các phép cơ bản:
Duyệt trước (Pre-order)
Duyệt giữa (In-order)
Duyệt sau (Post-order)
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
15
Parent(a)?
Tìm cha một đỉnh.
Parent(b) = a
EldestChild(c) = g
• Parent(x)
Tìm đỉnh con trái nhất.
b
c
• EldestChild(x)
Tìm đỉnh kề phải.
d
e
• NextSibling(x)
f
g
NextSibling(g) = h
i
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
NextSibling(h)?
h
16
Duyệt theo chiều sâu
Duyệt trước
• abdeijcfgkh
Duyệt giữa
b
c
• dbiejafckgh
d
e
f
g
Duyệt sau
• dijebfkghca
i
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
j
k
h
17
Pre-order
Post-order
void Preorder(NODE A)
void Postorder(NODE A)
{
NODE B;
{
NODE B;
Visit(A);
B = EldestChild(A);
while (B != ) {
Postorder(B);
B = NextSibling(B);
}
Visit(A);
B = EldestChild(A);
while (B != ) {
Preorder(B);
B = NextSibling(B);
}
}
}
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
18
In-Order
void Inorder(NODE A)
{
NODE B;
B = EldestChild(A);
if (B != ) {
Inorder(B);
B = NextSibling(B);
}
Visit(A);
while (B != ) {
Inorder(B);
B = NextSibling(B);
}
}
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
19
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
20
info
child
id
next
1
a
2
3
2
b
4
5
3
c
6
7
4
d
5
e
9
10
6
f
7
g
8
h
9
i
10
j
11
k
8
b
c
11
d
e
i
Cấu trúc dữ liệu và giải thuật - HCMUS 2013
f
j
g
k
h
- Xem thêm -