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
đó
b
ồ
á
út
đượ
Câ
y
là
m
ột
c
ấ

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

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

chất
sau
đây
“
Giá
của
nó
được
tổ
chức
để
luôn
thỏa
tính
chất
sau
đây
Giá
trị của nút cha luôn lớnhơn giá trị tấtcả nút con bên
trái và nhỏ hơn giá trị củatấtcả nút con bên phải”.
19/12/2008 6Cấu trúc dữ liệu 1
5
2
2
Cây
nhị
phân
tìm
kiếm
5.2. Cây nhị phân

tìm
kiếm
Biểu
diễn
cây
nhị
phân
tìm
kiếm
Biểu
diễn
cây
nhị
phân
tìm
kiếm
struct Node
{
int key;
Node * left, * right;
}
;
}
;
typedef Node *pNode;
tt
T
s
t
ruc

trên
cây
nhị
phân
tìm
kiếm
Các
thao
tác
trên
cây
nhị
phân
tìm
kiếm
Khởitạocây
id
iti l
(
t)
vo
id
In
iti
a
l
(
Tree
&t)
{

tìm
kiếm
5.2. Cây nhị phân
5
.
2
.
2
.
Cây
nhị
phân
tìm
kiếm
Các
thao
tác
trên
cây
nhị
phân
tìm
kiếm
Các
thao
tác
trên
cây
nhị
phân

trái
,
lớn
hơn
thì sang phải.
-Sosánhvớinútgốccủa cây con bên trái (phải) và lặp
lại
quá
trình
trên
cho
đến
khi
tìm
được
vị
trí
thích
hợp
.
19/12/2008 10Cấu trúc dữ liệu 1
lại
quá
trình
trên
cho
đến
khi
tìm
được

â
Thê
mm
ột
n
út
v
à
oc
ây
int Ins (pNode &r, int k)
{
//
if (!r)
//
r==NULL
{
pNode p = new Node;
p
>
key
=
k
;
p
-
>
key
=
k

k
)
;
19/12/2008 11Cấu trúc dữ liệu 1
(
y
)
(
,)
else return Ins (r->right,k);
}
5.2. Cây nhị phân
5
2
2
Cây
nhị
phân
tìm
kiếm
5
.
2
.
2
.
Cây
nhị
phân
tìm

t
(
Tree
&t
,
i
n
t
k)
{
return
I
nsert
(
t
.
r
oot,k)
;
}
19/12/2008 12Cấu trúc dữ liệu 1
5.2. Cây nhị phân
5
2
2
Cây
nhị
phân
tìm
kiếm

it
t
(
t
it
k)
i
n
t
Inser
t
(
Tree
&t
,
i
n
t
k)
{
return
I
ns
(
t
.
r
oot,k);
}
19/12/2008 13Cấu trúc dữ liệu 1

if
(Insert(t k))
if
(Insert(t
,
k))
cout<<"Thanh cong"<<endl;
else
cout
<<
"
Nut
da
co
trong
cay
"
<<endl
;
19/12/2008 14Cấu trúc dữ liệu 1
cout
<< Nut
da
co
trong
cay <<endl
;
}while (k!=-1);
}
5.2. Cây nhị phân

2
2
Cây
nhị
phân
tìm
kiếm
5
.
2
.
2
.
Cây
nhị
phân
tìm
kiếm
Các thao tác trên cây nhị phân tìm kiếm
Duyệtcây
void LNR (pNode r)
{
{
if (!r)
return;
lnr(r
-
>left)
;
lnr(r

2
.
Cây
nhị
phân
tìm
kiếm
Các thao tác trên cây nhị phân tìm kiếm
Tìm khóa k có trong cây hay không
int Search(pNode r,int k)
{
{
if (!r) return 0;
if (r->key == k) return 1;
if (r->key
>
k
)
return Search(r->left,k);
else
return Search(r->right,k);
}
int Search(Tree t,int k)
{
19/12/2008 17Cấu trúc dữ liệu 1
{
return Search(t.root,k);
}
5.2. Cây nhị phân
5

n
à
o
khá
c.
19/12/2008 18Cấu trúc dữ liệu 1
5.2. Cây nhị phân
5
2
2
Cây
nhị
phân
tìm
kiếm
5
.
2
.
2
.
Cây
nhị
phân
tìm
kiếm
Các thao tác trên cây nhị phân tìm kiếm
Xóa một nút X
- Xchỉ có1nútcon:trướckhihủyXtamócnốichacủa
ới

phân
tìm
kiếm
Các thao tác trên cây nhị phân tìm kiếm
Xóa một nút X
-Xcóđủ cả 2con: không thể hủytrựctiếpdoXcóđủ 2
ế
ầ
con ⇒ hủygiánti
ế
p. Thay vì hủyX,tasẽ tìm một
p
h
ầ
n
tử thế mạng Y. Phầntử nàycótối đamột con. Thông tin
l
t i
Y
ẽ
đ
h ể
lê
l
t i
X
S
đó
út
bị

là
phải
chọn
Y
sao
cho
khi
lưu
Y
vào
vị
trí
của
X
cây
là
phải
chọn
Y
sao
cho
khi
lưu
Y
vào
vị
trí
của
X
,

+Phầntử lớnnhất(phảinhất) trên cây con trái.
5.2. Cây nhị phân
5
2
2
Cây
nhị
phân
tìm
kiếm
5
.
2
.
2
.
Cây
nhị
phân
tìm
kiếm
Có thể dùng 15
để thế mạng
19/12/2008 21Cấu trúc dữ liệu 1
để

thế

mạng
5.2. Cây nhị phân

3
Cây
nhị
phân
cân
bằng
5
.
2
.
3
.
Cây
nhị
phân
cân
bằng
Định nghĩa
Cây cân bằng hoàn toàn là cây nhị phân tìm kiếmmà
tạimỗi nút củanó,số nút của cây con trái chênh lệch
kh
á
ới
ố
ú
h i
kh
ông qu
á
một so v

.
Cây
nhị
phân
cân
bằng
Nhậnxét
• Mộtcâyrất khó đạt đượctrạng thái cân bằng hoàn toàn và cũng
rấtdễ mấtcânbằng vì khi thêm hay hủy các nút trên cây có thể
ấ
ằ
ấ
ấ
ằ
làm cây m
ấ
tcânb
ằ
ng (xác su
ấ
tr
ấ
tlớn), chi
p
hí cân b
ằ
ng lại cây
lớnvìphải thao tác trên toàn bộ cây.
•
Trong

(n
là số nút trên cây).
•
Do
CCBHT
là
một
cấu
trúc
kém
ổn
định
nên
trong
thực
tế
không
Do
CCBHT
là
một
cấu
trúc
kém
ổn
định
nên
trong
thực
tế

ạ
imỗinútcủanóđ
ộ
cao của câ
y
con trái v
à
củ
a
câ
y
con
ạ
ộ
y
y
phải chênh lệch không quá một.
Cây AVL
19/12/2008 25Cấu trúc dữ liệu 1
Cây nhị phân tìm kiếm cân bằng AVL