1
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 1
! Cây và các ứng dụng của
cây
! Một số dạng cây thường
dùng: cây nhị phân, cây nhị
phân tìm kiếm, cây cân
bằng (AVL)
! Các thuật toán trên cây
! Đánh giá thuật toán
Cấu trúc cây -Trees
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 2
Nội dung trình bày
! Các khái niệm và thuật ngữ cơ bản
! Tổng quan về cây nhị phân (Binary Tree)
! Cây nhị phân tìm kiếm (BST –Binary
Search Tree)
! Cây nhị phân tìm kiếm cân bằng (AVL
Tree)
2
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 3
Các khái niệm và thuật ngữ cơ bản
! Các ví dụ
! Định nghĩa cấu trúc cây
! Các thuật ngữ liên quan
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 4
Các khái niệm và thuật ngữ cơ bản
Các ví dụ
! Ví dụ 1: bài toán đưa thư
! Trên thế giới hiện có 6 tỉ người
! Tuấn, khoa CNTT, ĐH KHTN, Tp.HCM,

4
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 7
Các khái niệm và thuật ngữ cơ bản
Các ví dụ
! Cây là 1 cấu trúc dữ liệu quan trọng để
biểu diễn tính “kế thừa”
! Các cây mô tả tính kế thừa:
! Cây gia phả (trong các dòng họ)
! Cây phân cấp các loài (trong sinh vật)
! …
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 8
Các khái niệm và thuật ngữ cơ bản
Định nghĩa cấu trúc cây
! Một cây <T> (Tree) là:
! Một tập các phần tử, gọi là các nút (Node)
p
1
,p
2
,…,p
N
! Nếu N=0, cây <T> gọi là cây rỗng (NULL)
! Nếu N>0:
! Tồn tại duy nhất 1 nút p
k
gọi là gốc của cây
! Các nút còn lại được chia thành m tập không giao
nhau: T
1
, T

>
Cây con <T
3
>
Cây con <T
4
>
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 10
Các khái niệm và thuật ngữ cơ bản
Định nghĩa cấu trúc cây
a
c
k
d
b
i h
j
g
e
f
Cây con <T
1
>
Cây con <T
2
>
Cây con <T
3
>
Cây con <T

! 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
7
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 13
Các khái niệm và thuật ngữ cơ bản
Các thuật ngữ liên quan
! Nút (Node): là 1 phần tử trong cây. Mỗi nút có
thể chứa 1 dữ liệu bất kỳ
! Nhánh (Branch): là đoạn nối giữa 2 nút
! Nút cha (Parent node)
! Nút con (Child node)
! Nút anh em (sibling nodes): là những nút có cùng
nút cha
! Bậc của 1 nút p
i
: là số nút con của p
i
! Bậc (a) = 4; Bậc (j) = 3; Bậc (g) = 2;
! Bậc (k) = 1; Bậc (c) = 0
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 14
Các khái niệm và thuật ngữ cơ bản
Các thuật ngữ liên quan
! Nút gốc (Root node): nút không có nút cha
! Nút lá (Leaf node, haynút ngoài –External
node): nút có bậc = 0 (không có nút con)
! Nút nội (Internal node): là nút có nút cha
và có nút con
! Cây con (Subtree)
! Trắc nghiệm: có bao nhiêu cây con trong cây

dài nhất từ nút gốc đến nút lá
! h
T
= max {Path(root, p
i
) / p
i
là nút lá ∈ <T>}
! h
T
?
9
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 17
Các khái niệm và thuật ngữ cơ bản
Các thuật ngữ liên quan
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 18
Các khái niệm và thuật ngữ cơ bản
Các thuật ngữ liên quan
! Cây hoàn chỉnh (Complete tree) với h mức: là 1
cây thoả các điều kiện
! Những nút từ mức 0 đến mức h-1 đều đầy đủ
! Những nút ở mức h được thêm vào cây từ trái sang
phải
10
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 19
Các khái niệm và thuật ngữ cơ bản
Các thuật ngữ liên quan
Cây hoàn chỉnh ?
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 20
Các khái niệm và thuật ngữ cơ bản

! h mức đầu tiên của cây đầy đủ bậc d có số nút
là:
! 1 + d + d
2
+ d
3
+ … + d
h-1
= (d
h
-1)/(d –1)
! 3 mức đầu tiên của cây bậc 3 có bao nhiêu nút ?
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 26
Tổng quan về cây nhị phân
! Định nghĩa
! Cách thức lưu trữ cây
! Các phương pháp duyệt cây
14
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 27
Tổng quan về cây nhị phân
Định nghĩa
! Cây nhị phân là cây có bậc = 2
*
0
/
a
b
c
d
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 28

a
b
c
d
-1-1d6
-1-1c5
-1-1b4
-1-1a3
65/2
43-1
21*0
Con phảiCon tráiNút#
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 32
Tổng quan về cây nhị phân
Cách thức lưu trữ cây, sử dụng mảng
// Định nghĩa các cấu trúc dữ liệu
typedef struct tagBT_NODE {
intData;
intLeft;// chỉ số nút con trái
intRight;// chỉ số nút con phải
} BT_NODE;// binary tree node
BT_NODE tree[N];// cây nhị phân có N nút
17
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 33
Tổng quan về cây nhị phân
Cách thức lưu trữ cây, sử dụng con trỏ
Nút gốc của
cây con trái
Data
pLeft pRight

Các phương pháp duyệt cây
! Có 3 cách duyệt cây:
! Duyệt gốc trước (Pre-Order) NLR
! Duyệt gốc giữa (In-Order) LNR
! Duyệt gốc sau (Post-Order) LRN
19
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 37
Tổng quan về cây nhị phân
Các phương pháp duyệt cây
void NLR(const BT_NODE
*pCurr)
{
if (pCurr==NULL) return;
“Xử lý nút gốc pCurr”
NLR(pCurr->pLeft);
NLR(pCurr->pRight);
}
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 38
Tổng quan về cây nhị phân
Các phương pháp duyệt cây
Minh họa cách
duyệt “gốc trước”
20
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 39
Tổng quan về cây nhị phân
Các phương pháp duyệt cây
void LNR(const BT_NODE
*pCurr)
{
if (pCurr==NULL) return;

cây theo mức ?
22
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 43
Cây nhị phân tìm kiếm
(BST –Binary Search Tree)
! Ý nghĩa của cây BST
! Định nghĩa
! Ví dụ
! Mô tả cấu trúc dữ liệu
! Xây dựng các thao tác cơ bản trên cây
! Các đánh giá
! Trắc nghiệm
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 44
Cây nhị phân tìm kiếm
Ý nghĩa của cây BST
! Điểm yếu và điểm mạnh của việc sử dụng
mảng ?
! Điểm yếu và điểm mạnh của việc sử dụng
danh sách liên kết ?
! Cần có 1 cấu trúc tổng hợp được điểm
mạnh của cả mảng và danh sách liên kết.
! Trong cây nhị phân, chi phí để tìm kiếm 1
phần tử ?
23
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 45
Cây nhị phân tìm kiếm
Định nghĩa
! Cây nhị phân tìm kiếm là:
! Một cây nhị phân
! Mỗi nút p của cây đều thỏa:

Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 50
Cây nhị phân tìm kiếm
Xây dựng các thao tác cơ bản trên cây
! Tạo lập cây rỗng:
void BSTCreate(BIN_TREE &t)
{
t.Count = 0; // Số nút trong cây
t.pRoot = NULL; // Con trỏ đến nút gốc
}