CẤU TRÚC CÂY (TREE)
Bmôn Công nghphn mm
Khoa Công nghthông tin & Truyn thông
Đi hc Cn Thơ
CÁC THUẬT NGỮ CƠ BẢN (1)
Đnh nghĩa
Cây (tree): mt tp hp hu hn các phn t
gi là các nút (nodes) và tp hp hu hn các
cnh ni các cp nút li vi nhau mà không
to thành chu trình. Nói cách khác, cây là 1 đ
thkhông có chu trình.
Ví d:
A
B C
D E F
CÁC THUẬT NGỮ CƠ BẢN (2)
Ta có th đnh nghĩa cây 1 cách đ qui
nhưsau:
M
t nút
đơ
n
đ
c là 1 cây, nút này c
ũ
ng là nút g
c
c
a cây.
Nút n là nút
đơ
n
đ
c và k cây riêng l
T1, T2, ...Tk
có các nút g
c l
n l
ư
t là n1, n2,...nk. Khi
đ
ó ta có
đư
c 1 cây m
i có nút g
c là nút n và các cây con
c
a nó là T1, T2, ... Tk.
Mô hình:
n
nuït gäúc
Cáy con
T
1
T
2
T
k
.......
n1
n1
nk
Nút gc
Cây con
CÁC THUẬT NGỮ CƠ BẢN (3)
Ví d
CÁC THUẬT NGỮ CƠ BẢN (4)
Nút cha con: nút A là cha c
a nút B khi nút A
m
c i
và nút B
m
c i+1,
đ
ng th
i gi
a A và B có c
nh
n
i.
VD:
cây trên, nút B là cha c
a G và H. Nút I là
con c
a D.
B
c c
a nút là s
cây con c
a nút
đ
ó, b
c nút lá =0.
VD: A có b
c 5, C có b
c 0, O có b
c 1
B
c c
a cây là b
c l
n nh
t c
a các nút trên cây.
VD: cây trên có b
c 5.
Cây n-phân là cây có b
c n.
VD: B
c c
a cây là 5 hay cây ng
ũ
phân