Bài giảng Cấu trúc dữ liệu và giải thuật (Data structures and Algorithms): Chương 1 - Ngô Công Thắng - Trường Đại học Công nghiệp Thực phẩm Tp. Hồ Chí Minh
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (567.89 KB, 10 trang )
<span class='text_page_counter'>(1)</span><div class='page_container' data-page=1>
CH
ƯƠ
NG 1: CÂY (TREE)
GV. Ngô Công Th
ắ
ng
B
ộ
môn Công ngh
ệ
ph
ầ
n m
ề
m
Khoa Công ngh
ệ
thông tin
Website: dse.hua.edu.vn/ncthang
Email:
Ch
ươ
ng 1: Cây (Tree)
1.
Đị
nh ngh
ĩ
a và khái ni
ệ
m
2. Cây nh
ị
phân
</div>
<span class='text_page_counter'>(2)</span><div class='page_container' data-page=2>
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 01
1.
Đị
nh ngh
ĩ
a và khái ni
ệ
m
1.1.
Đị
nh ngh
ĩ
a cây (tree)
l
Cây là m
ộ
t t
ậ
p h
ợ
p h
ữ
u h
ạ
n các nút, trong
đ
ó có m
ộ
t nút
đặ
c bi
ệ
t g
ọ
i là g
ố
c (root).
Gi
ữ
a các nút có m
ộ
t quan h
ệ
phân c
ấ
p g
ọ
i
là quan h
ệ
cha con.
l
M
ộ
t cây khơng có nút nào g
ọ
i là cây r
ỗ
ng
(null tree).
l
Các ví d
ụ
v
ề
cây
1.3
Ví d
ụ
1: M
ụ
c l
ụ
c c
ủ
a m
ộ
t ch
ươ
ng
đượ
c bi
ể
u di
ễ
n d
ạ
ng cây
Ch
ươ
ng 6
6.1
6.2
</div>
<span class='text_page_counter'>(3)</span><div class='page_container' data-page=3>
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 01
Ví d
ụ
2: Bi
ể
u th
ứ
c s
ố
h
ọ
c
đượ
c
bi
ể
u di
ễ
n d
ạ
ng cây
x+y*(z-t)+u/v
1.5
Ví d
ụ
3: Các t
ậ
p bao nhau
đượ
c
bi
ể
u di
ễ
n d
ạ
ng cây
</div>
<span class='text_page_counter'>(4)</span><div class='page_container' data-page=4>
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 01
1.2. Các khái ni
ệ
m
l
G
ố
c (Root): G
ố
c là nút
đặ
c bi
ệ
t khơng có
nút cha.
Ví d
ụ
3: A là g
ố
c. A là cha c
ủ
a B, E, F.
B, E, F là con c
ủ
a A.
B, E, F c
ũ
ng là g
ố
c c
ủ
a các cây con c
ủ
a A
l
C
ấ
p (Degree): S
ố
con c
ủ
a m
ộ
t nút g
ọ
i là
c
ấ
p c
ủ
a nút
đ
ó.
Ví d
ụ
3: A có c
ấ
p là 3. E, F có c
ấ
p là 0.
B có c
ấ
p là 2.
1.7
1.2. Các khái ni
ệ
m (
<i>ti</i>
<i>ế</i>
<i>p</i>
)
l
Lá (Leaf): Nút có c
ấ
p b
ằ
ng khơng g
ọ
i là lá hay
nút t
ậ
n cùng.
Ví d
ụ
3: C,D,E,F là lá.
</div>
<span class='text_page_counter'>(5)</span><div class='page_container' data-page=5>
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 01
1.2. Các khái ni
ệ
m (
<i>ti</i>
<i>ế</i>
<i>p</i>
)
l
Chi
ề
u cao c
ủ
a cây (Height) hay chi
ề
u sâu c
ủ
a
cây (Depth): Là s
ố
m
ứ
c l
ớ
n nh
ấ
t c
ủ
a nút có trên
cây.
Ví d
ụ
1: Cây có chi
ề
u cao là 3
Ví d
ụ
2: Cây có chi
ề
u cao là 5
Ví d
ụ
3: Cây có chi
ề
u cao là 3
l
Đườ
ng
đ
i (Path): N
ế
u n
<sub>1</sub>
, n
<sub>2</sub>
, ..., n
<sub>k</sub>
là các dãy nút
mà n
<sub>i</sub>
là cha c
ủ
a n
<sub>i+1</sub>
(1
≤
i<k) thì dãy
đ
ó g
ọ
i là
đườ
ng
đ
i t
ừ
n
<sub>1</sub>
đế
n n
<sub>k</sub>
.
Độ
dài c
ủ
a
đườ
ng
đ
i
b
ằ
ng s
ố
nút tr
ừ
đ
i 1. .
Ví d
ụ
3:
Đườ
ng
đ
i t
ừ
A
đế
n C c
ố
độ
dài là 3-1=2.
Đườ
ng
đ
i t
ừ
A
đế
n E c
ố
độ
dài là 2-1=1.
1.9
1.2. Các khái ni
ệ
m (
<i>ti</i>
<i>ế</i>
<i>p</i>
)
l
N
ế
u th
ứ
t
ự
các cây con c
ủ
a m
ộ
t nút
đượ
c coi
tr
ọ
ng thì cây
đ
ang xét là cây có th
ứ
t
ự
, ng
ượ
c l
ạ
i
là cây khơng có th
ứ
t
ự
.
l
Th
ườ
ng thì th
ứ
t
ự
các cây con c
ủ
a m
ộ
t nút
</div>
<span class='text_page_counter'>(6)</span><div class='page_container' data-page=6>
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 01
1.2. Các khái ni
ệ
m (
<i>ti</i>
<i>ế</i>
<i>p</i>
)
l
Đố
i v
ớ
i cây, ngoài quan h
ệ
cha con, ng
ườ
i
ta còn m
ở
r
ộ
ng ph
ỏ
ng theo quan h
ệ
trong
gia t
ộ
c.
l
R
ừ
ng (Forest): N
ế
u có m
ộ
t t
ậ
p h
ữ
u h
ạ
n
các cây phân bi
ệ
t thì ta g
ọ
i t
ậ
p
đ
ó là r
ừ
ng.
l
N
ế
u b
ỏ
nút g
ố
c c
ủ
a m
ộ
t cây thì ta s
ẽ
có
m
ộ
t r
ừ
ng.
1.11
2. Cây nh
ị
phân
2.1.
Đị
nh ngh
ĩ
a và tính ch
ấ
t
2.1.1.
Đị
nh ngh
ĩ
a cây nh
ị
phân
</div>
<span class='text_page_counter'>(7)</span><div class='page_container' data-page=7>
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 01
Ví d
ụ
1: Hai cây sau
đ
ây là khác nhau
1.13
Ví d
ụ
2: Cây nh
ị
phân suy bi
ế
n có
d
ạ
ng m
ộ
t danh sách tuy
ế
n tính
Cây l
ệ
ch trái
</div>
<span class='text_page_counter'>(8)</span><div class='page_container' data-page=8>
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 01
Ví d
ụ
2: Cây nh
ị
phân suy bi
ế
n có d
ạ
ng
m
ộ
t danh sách tuy
ế
n tính (
<i>ti</i>
<i>ế</i>
<i>p</i>
)
Cây zíc z
ắ
c
1.15
2.1.1.
Đị
nh ngh
ĩ
a cây nh
ị
phân (
<i>ti</i>
<i>ế</i>
<i>p</i>
)
</div>
<span class='text_page_counter'>(9)</span><div class='page_container' data-page=9>
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 01
2.1.1.
Đị
nh ngh
ĩ
a cây nh
ị
phân (
<i>ti</i>
<i>ế</i>
<i>p</i>
)
l
Cây nh
ị
phân
đầ
y
đủ
: Là cây nh
ị
phân mà các
nút
ở
m
ọ
i m
ứ
c c
ủ
a nút nhánh
đề
u có hai con.
Cây nh
ị
phân
đầ
y
đủ
là tr
ườ
ng h
ợ
p
đặ
c bi
ệ
t c
ủ
a
cây nh
ị
phân hồn ch
ỉ
nh.
1.17
2.1.2. Tính ch
ấ
t
l
S
ố
l
ượ
ng t
ố
i
đ
a các nút
ở
m
ứ
c i trên 1 cây
nh
ị
phân là 2
(i-1)
<sub>(i</sub>
≥
<sub>1).</sub>
</div>
<span class='text_page_counter'>(10)</span><div class='page_container' data-page=10>
Ngô Công Thắng Bài giảng Cấu trúc dữ liệu và giải thuật 2 - Chương 01
2.2. L
ư
u tr
ữ
cây nh
ị
phân
2.2.1. L
ư
u tr
ữ
k
ế
ti
ế
p
l
V
ớ
i cây nh
ị
phân
đầ
y
đủ
, ta
đ
ánh s
ố
các
nút t
ừ
1 tr
ở
đ
i, t
ừ
trái qua ph
ả
i, h
ế
t m
ứ
c
này
đế
n m
ứ
c khác.
l
Dùng véc t
ơ
V l
ư
u tr
ữ
cây nh
ị
phân, nút th
ứ
i c
ủ
a cây
đượ
c l
ư
u tr
ữ
ở
ô nh
ớ
V[i]. Ví d
ụ
:
1.19
2.2.1. L
ư
u tr
ữ
k
ế
ti
ế
p (
<i>ti</i>
<i>ế</i>
<i>p</i>
)
</div>
<!--links-->
