Chương 5
Cấutrúcdữliệucây
Cấu
trúc
dữ
liệu
cây
5.1. Định nghĩa
Câ
là
ột
ấ
tú
t
đó
ồ
á
út
đượ
Câ
y
là
m
ột
c
ấ
u
t
r
ú
c
t
rong
đó
ao g
ồ
mc
á
cn
út
đượ
c
liên kếtvới nhau theo hệthống phân cấp, trong đónút
có cấp cao nhấtđượcgọilànútgốcvànútcócấpthấp
nhất
được
gọi
là
các
nút
lá
nhất
được
gọi
là
các
nút
lá
.
19/12/2008 2Cấu trúc dữ liệu 1
5.1. Định nghĩa
19/12/2008 3Cấu trúc dữ liệu 1
5.1. Định nghĩa
•
Thuật
ngữ
:
•
Thuật
ngữ
:
- Nút cha (parents node) củamột node là nút có cấp
cao
hơn
nó
một
bậc
cao
hơn
nó
một
bậc
.
- Nút con (child node) củamộtnodelànútcócấpnhỏ
hơn
nó
một
bậc
hơn
nó
một
bậc
.
-Nútgốc (root) là nút không có nút cha.
- Nút lá (leaf – leaves) là nút không có nút con.
-C
ấp
của1nút
(
level of
a
node
)
l
à
các liên k
ế
tđ
ể
đi
p
(
)
từnút gốcđến nút đó.
19/12/2008 4Cấu trúc dữ liệu 1
5.2. Cây nhịphân
5
2
1
Khái
niệm
về
cây
nhị
phân
5
.
2
.
1
.
Khái
niệm
về
cây
nhị
phân
ỗ
Cây nhị
p
hân là mộtcâymàm
ỗ
i nút có không quá 2 nút
con
19/12/2008 5Cấu trúc dữ liệu 1