Cấu trúc dữ liệu và giải thuật
Đỗ Tuấn Anh
[email protected]
Nội dung
z Chương 1 – Thiết kế và phân tích (5 tiết)
z Chương 2 – Giải thuật đệ quy (10 tiết)
z Chương 3 – Mảng và danh sách (5 tiết)
z Chương 4 – Ngăn xếp và hàng đợi (10 tiết)
z Chương 5 – Cấu trúc cây (10 tiết)
z Chương 8 – Tìm kiếm (5 tiết)
z Chương 7 – Sắp xếp (10 tiết)
z Chương 6 – Đồ thị (5 tiết)
Chương 5 – Cấu trúc cây
1. Định nghĩa và khái niệm
2. Cây nhị phân
{ Định nghĩa và Tính chất
{ Lưu trữ
{ Duyệt cây
3. Cây tổng quát
{ Biểu diễn cây tổng quát
{ Duyệt cây tổng quát (nói qua)
4. Ứng dụng của cấu trúc cây
• Cây biểu diễn biểu thức (tính giá trị, tính đạo hàm)
• Cây quyết định
1. Định nghĩa và khái niệm
z Danh sách chỉ thể hiện được các mối quan hệ
tuyến tính.
z Thông tin còn có thể có quan hệ dạng phi tuyến,
ví dụ:
{Các thư mục file
{Các bước di chuyển của các quân cờ

nút con
nút lá
nút giữa/nhánh
nút gốc
e, i, k, g, h
là các nút lá
nút anh em
Cây con
a
b
d
e
f
i j
g
h
c
k
nút gốc
Một nút và tất cả
các nút con cháu.
Đường đi
a
c
b
e
f
d
g
j

7
3 10
8
4
12
1
6 5
211
9
Số con của nút x được gọi
là
cấp của x.
Cấp= 3
Cấp= 1 Cấp= 0
2. Cây nhị phân
2.1. Định nghĩa và tính chất
Mỗi nút có nhiều nhất 2 nút con.
r
a) Nó là cây rỗng, hoặc
Một tập các nút T được gọi là cây nhị phân nếu
a
d
b
c
f
e
cây con trái
cây con phải
b) Gồm 3 tập con không trùng nhau:
1) một nút gốc

- 1
z Độ cao (với cây nhị phân gồm N nút): H
{ Tối đa= N
{ Tốithiểu = [log
2
(N+1)] - 1
2.2 Lưu trữ cây nhị phân
z Lưu trữ kế tiếp:
{Sử dụng mảng
Lưu trữ móc nối
a
b
f
e
c
a
rightleft
rightleft
b
g
NULL
left right
left right
right
g
e
c
left
left right
f

root->right = rightChild;
10
20
30
root -> data = 50; // gán 50 cho root
50
2.3. Duyệt cây nhị phân
z Duyệt cây: lần lượt duyệt toàn bộ nút trên cây
z Có 3 cách duyệtcây:
{ Duyệt theo thứ tự trước
{ Duyệt theo thứ tự giữa
{ Duyệt theo thứ tự sau
z Định nghĩaduyệt cây nhị phân là những định
nghĩa đệ quy.
Duyệt theo thứ tự trước
1. Thăm nút.
2. Duyệt cây con trái theo thứ tự trước.
3. Duyệt cây con phải theo thứ tự trước.
a
b
c
d
e
Traversal order: abdce
e
c
d
b
a
Duyệt theo thứ tự sau