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,
Việt nam
! Cách tìm ra “Tuấn” nhanh nhất ?
! Sử dụng mảng (array) ?
! Sử dụng danh sách liên kết (linked list) ?
3
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 5
Các khái niệm và thuật ngữ cơ bản
Các ví dụ
China
... ...
... ...
Korea Vietnam
Trái đất
Tp.HCM Hà nội
ĐH.KHTN ĐH.BK
Khoa CNTT Khoa Toán
“Tuấn”
... ...
... ...

,…,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
2
, …, T
m
! Mỗi <T
i
> là 1 cây con của cây <T>
5
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 9
Các khái niệm và thuật ngữ cơ bản
Định nghĩa cấu trúc cây
a
b
k
i
g
c
h
e
f

f
Cây con <T
1
>
Cây con <T
2
>
Cây con <T
3
>
Cây con <T
4
>
Cây <T>
6
Spring 2004Data Structure & Algorithm -Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 11
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
dbi h
j
g
ef
Cây con <T
1
> Cây con <T
2
> Cây con <T