C u trúc d li u 1 vá thu t gi iấ ữ ệ ậ ả
N I DUNGỘ
CÂY VÀ CÂY NH PHÂNỊ
C u trúc d li u 1 vá thu t gi iấ ữ ệ ậ ả
Đ 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, T2, …,Tn 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.ệ ườ ọ ệ
C u trúc d li u 1 vá thu t gi iấ ữ ệ ậ ả
M t s khái ni mộ ố ệ
•B c c a m t nút: là s cây con c a nút đó .ậ ủ ộ ố ủ
•B c c a m t cây: là b c l n nh t c a các nút ậ ủ ộ ậ ớ ấ ủ
trong cây
•Nút g c: là nút không có nút cha.ố
•Nút lá: là nút có b c b ng 0 .ậ ằ
•M c c a m t nút:ứ ủ ộ
–M c (g c (T) ) = 0.ứ ố
–G i T1, T2, T3, ... , Tn là các cây con c a T0 :ọ ủ
M c (T1) = M c (T2) = . . . = M c (Tn) = M c (T0) + ứ ứ ứ ứ
1.
•Đ dài đ ng đi t g c đ n nút x: là s nhánh ộ ườ ừ ố ế ố
c n đi qua k t g c đ n x.ầ ể ừ ố ế
C u trúc d li u 1 vá thu t gi iấ ữ ệ ậ ả
Ví d 1 t ch c d ng câyụ ổ ứ ạ
BB-Electronic Corp.
R&D Kinh doanh Taøi vuï Saûn xuaát
TV CD AmplierNoäi ñòa Quoác teá
Chaâu aâu Myõ Caùc
nöôùc
C u trúc d li u 1 vá thu t gi iấ ữ ệ ậ ả
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