Cấu trúc dữ liệu 1 vá thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬ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á thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬ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 T
1
, T
2
, …,T
n
theo quan hệ
phân cấp, trong đó T
i
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á thuật giải

Mỹ Các
nước
Generated by Foxit PDF Creator © Foxit Software
For evaluation only.
Cấu trúc dữ liệu 1 vá thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬ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á thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬ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

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á thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬ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 :

Click To Edit Master Title Style
11
Duyệt Trước
void NLR(TREE Root)
{
if (Root != NULL)
{
<X
ử lý
Root>; //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á thuật giải
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬ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ý Root>; //
X
ử lý tương ứng theo nhu

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.