diepvinhcuong
New Member
Download miễn phí Bài giảng Cấu trúc dữ liệu và giải thuật 1 - Cây và cây nhị phân
Duyệt Cây Nhị Phân
-Có 3 trình tự thăm gốc :
Duyệt trước
Duyệt giữa
Duyệt sau
-Độ phức tạp O (log2(h))
Trongđó h là chiều cao cây
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
Cấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
1
NỘI DUNG
CÂY VÀ CÂY NHỊ PHÂN
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
2
Định Nghĩa Cây
Cây là một tập hợp T các phần tử (gọi là nút
của cây), trong đó có một nút đặc biệt gọi là
nút gốc, các nút còn lại được chia thành
những tập rời nhau T1, T2, …,Tn theo quan hệ
phân cấp, trong đó Ti cũng là 1 cây. Mỗi nút ở
cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ
này người ta gọi là quan hệ cha – con.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
3
Một Số Khái Niệm
• Bậc của một nút: là số cây con của nút đó .
• Bậc của một cây: là bậc lớn nhất của các nút
trong cây
• Nút gốc: là nút không có nút cha.
• Nút lá: là nút có bậc bằng 0 .
• Mức của một nút:
– Mức (gốc (T) ) = 0.
– Gọi T1, T2, T3, ... , Tn là các cây con của T0 :
Mức (T1) = Mức (T2) = . . . = Mức (Tn) = Mức (T0)
+ 1.
• Độ dài đường đi từ gốc đến nút x: là số nhánh
cần đi qua kể từ gốc đến x.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
4
Ví Dụ 1 Tổ Chức Dạng Cây
BB-Electronic Corp.
R&D Kinh doanh Taøi vuï Saûn xuaát
TV CD AmplierNoäi ñòa Quoác teá
Chaâu
aâu
Myõ Caùc
nöôùc
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
5
Cây Nhị Phân
• Mỗi nút có tối đa 2 cây con
Caây
con
traùi
Caây
con
phaûi
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
6
Một Số Tính Chất Của Cây Nhị Phân
• Số nút nằm ở mức i
2i.
• Số nút lá 2h-1, với h
là chiều cao của cây.
• Chiều cao của cây h
log2(N)
– N = số nút trong cây
• Số nút trong cây 2h-
1.
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
7
Cấu Trúc Dữ Liệu Củ Cây Nhị Phân
typedef struct tagTNode
{
Data Key;
struct tagTNode *pLeft;
struct tagTNode *pRight;
}TNode;
typedef TNode *TREE;
Key
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
8
Ví Dụ Cây Được Tổ Chức Trong Bộ Nhớ
Trong
3f62f
1f
N97f
3f
5f4N
2f
N5N
5f
N8N
7f
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
9
Duyệt Cây Nhị Phân
Có 3 trình tự thăm gốc :
Duyệt trước
Duyệt giữa
Duyệt sau
Độ phức tạp O (log2(h))
Trong đó h là chiều cao cây
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
10
Ví Dụ Kết Quả Của Phép Duyệ Cây
• NLR: 9, 2, 6, 1, 10, 8, 5, 3, 7, 12, 4.
• LNR: 6, 2, 10, 1, 9, 3, 5, 8, 12, 7, 4.
• Kết quả của phép duyệt : LRN, NRL,LRN, LNR?
9
82
16
10
5
3
7
412
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
11
Duyệt Trước
void NLR(TREE Root)
{
if (Root != NULL)
{
; //Xử lý tương ứng theo nhu cầu
NLR(Root->pLeft);
NLR(Root->pRight);
}
}
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
12
Duyệt Giữa
void LNR(TREE Root)
{
if (Root != NULL)
{
LNR(Root->pLeft);
; // Xử lý tương ứng theo nhu
cầu
LNR(Root->pRight);
}
}
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
13
Duyệt Sau
void LRN(TREE Root)
{
if (Root != NULL)
{
LRN(Root->pLeft);
LRN(Root->pRight);
; // Xử lý tương ứng theo nhu
cầu
}
}
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
C
ấ
u
tr
ú
c
d
ữ
li
ệ
u
1
v
á
th
u
ậ
t
g
iả
i
C
Ấ
U
T
R
Ú
C
D
Ữ
L
IỆ
U
V
À
G
IẢ
I
T
H
U
Ậ
T
1
Click To Edit Master Title Style
14
Biểu Diễn Cây Tổng Quát Bằng Cây Nhị Phân
A
B C D
E F G H I J
A
B
C
D
E
F
G
H
I
J
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
...