1
CH NG 3- CÂYƯƠ
2
Ch ng 3: Câyươ
3.1 Các khái ni m c b nệ ơ ả
3.2 Cây nh phânị
3.2.1 Đ nh nghĩa và tính ch tị ấ
3.2.2 Bi u di n cây nh phânể ễ ị
3.2.3 Duy t cây nh phânệ ị
3
3.1 CÁC KHÁI NI M C Ệ Ơ
B NẢ
Khái ni m cây:ệ
–Cây g m m t t p h p h u h n các nút-ồ ộ ậ ợ ữ ạ
node
–Gi a các nút có m t quan h th t b ữ ộ ệ ứ ự ộ
ph n (cha-con).ậ
–Có m t nút đ c bi t, không là con c a b t ộ ặ ệ ủ ấ
c nút nào và là t tiên c a m i nút trong ứ ổ ủ ọ
cây, g i là nút g c (root).ọ ố
–Cây không có nút nào g i là cây r ng.ọ ỗ
4
3.1 CÁC KHÁI NI M C Ệ Ơ
B NẢ
B c – degree – c a m t nút là s con c a nó. ậ ủ ộ ố ủ
Nút lá (leaf) –terminal node – là nút không có
con, b c c a nút lá b ng 0.ậ ủ ằ
Ng c v i nút lá là các nút có con, g i là nút ượ ớ ọ
phân nhánh hay nút trung gian (branch node).
B c c a cây là b c cao nh t c a các nút ậ ủ ậ ấ ủ
trong cây.
Cây nh phân là cây b c 2. N u cây có b c ị ậ ế ậ
cao h n 2 ta g i là cây nhi u nhánh.ơ ọ ề
5
3.1 CÁC KHÁI NI M C Ệ Ơ
B NẢ
M c – level – là đ ng c p c a nút ứ ẳ ấ ủ
trong mô hình phân c p. Quy c nút ấ ướ
g c có m c 1, n u nút cha có m c i thì ố ứ ế ứ
nút con có m c i + 1.ứ
Chi u cao – height – hay con g i là ề ọ
chi u sâu – depth – là m c l n nh t ề ứ ớ ấ
c a nút trên cây.ủ
Đ ng đi – path – t nút p đ n nút q ườ ừ ế
trên m t cây là dãy nút p = nộ1,n2,…,nk =
q sao cho ni là cha c a nủi+1.