Gi¸o ¸n:
C©y nhÞ ph©n t×m kiÕm
Häc viªn thùc hiÖn: §ång ThÞ Thu
Cao häc: K15
Cao häc K15
M«n: øng dông CNTT trong d¹y häc
  

Néi dung chÝnh cña bµi
I. §Þnh nghÜa c©y nhÞ ph©n
II. BiÓu diÔn c©y nhÞ ph©n
III. C¸c phÐp to¸n duyÖt c©y nhÞ ph©n
iV. Mét sè thao t¸c trªn c©y nhÞ ph©n
Bµi tËp

I.ĐỊNH NGHĨA
Cây nhị phân là cây có các nút đã được
khoá hóa và được sắp xếp theo một thứ tự phản
ánh vị trí của nút ở trong cây.
Đặc điểm của cây nhị phân:

Mọi nút trên cây chỉ có tối đa 2 con.

Với mỗi một nút:+ Toàn bộ những nút ở cây
con bên trái của nó đều có khoá nhỏ hơn khoá
của nó.
+ Toàn bộ những nút ở cây
con bên phải của nó đều có khoá lớn hơn khoá
của nó.


b) Cây nhị phân
lệch phải
b
A
C
B
D
E
D
A
B
C
E
d
c
c, d) Cây nhị phân
Cây zic- zắc

Một số dạng đặc biệt của cây nhị phân
(tiếp)
Cây nhị phân gần đầy
A
C
G
H
B
E
J
D
F

.
7
A
C
G
B
E
D
F
4 5
2
1
3
6

1. Lưu trữ kế tiếp (tiếp).
Qui luật:
- Con của nút thứ i là các nút 2i và 2i + 1
- Cha của nút thứ j là [j/2]
Ta lưu trữ cây nhị phân đầy đủ bằng một
vectơ V theo nguyên tắc: nút thứ i của cây được
lưu trữ ở V[1]. Đó là cách lưu trữ kế tiếp, biết
được địa chỉ nút cha sẽ tính được địa chỉ nút
con và ngược lại.
Vậy với cây trên ta sẽ có
A B C D E F G
V[1] V[2] V[3] V[4] V[5] V[6] V[7]

1. Lưu trữ kế tiếp (tiếp).
Nhận xét:

E
D
F
G
I
H
A
B
D
C
F
E
H I
G
T

Khai báo cây (Dùng danh sách móc nối)
Type
Item_Type=Record
Key: Key_Type;
Infor:Data;
End;
Search_Type = ^ Node;
Node= Record
Item:Item_Type;
Left,Right: Search_Type;
End;