CẤU TRÚC DỮ LIỆU
VÀ GIẢI THUẬT
Lý thuyết


Phần 3 ((Chương
g 4))
Cây
„
„
„

Khái niệm
Một số ứng dụng
set và map

Vũ Anh Dũng - Khoa CNTT

2


Khái niệm
„

Định nghĩa
„
„
„
„

Cây là tập các nút

Mỗi nút, loại trừ nút gốc đều chỉ có 1 nút
cha

Cây
y
Vũ Anh Dũng - Khoa CNTT

5


Khái niệm
„
„

Nút lá(leaf) là nút không có con, ví dụ : P,Q
Các nút có cùng nút cha được gọi là các nút
anh-chị-em (sibling), ví dụ : K,L,M

Vũ Anh Dũng - Khoa CNTT

6


Khái niệm
„

„

„


Chiều sâu của nút gốc là 0
Chiề cao của
Chiều
ủ một
ột nút
út ni là chiều
hiề dài
đường đi dài nhất từ ni đến một nút lá
Do đó tất
ấ cả các nút lá có chiều
ề cao bằng
ằ 0
Chiều cao của cây
y là chiều cao của nút g
gốc
Vũ Anh Dũng - Khoa CNTT

8


Khái niệm
„

Ví dụ
„
„
„

Nút E có chiều sâu 1 và chiều cao 2
Chiều cao của cây là 3

g g
chiều hướng từ trái sang
phải mô tả nextSibling
ƒCác liên kết rỗng (null)
không được vẽ vì số
lượng của chúng rất nhiều

Vũ Anh Dũng - Khoa CNTT

10


Duyệt cây
„

Ví dụ về duyệt cây thư mục
„

Dấu * bên cạnh tên chỉ ra rằng đó là thư mục

Vũ Anh Dũng - Khoa CNTT

11


Duyệt cây
„

„


}

Vũ Anh Dũng - Khoa CNTT

13


Duyệt cây
int FileSystem::size( ) const
{
int totalSize = sizeOfThisFile( );
if ( isDirectory( ) )
for each file c in this directory
totalSize += c.size( );
return totalSize;
}

Vũ Anh Dũng - Khoa CNTT

14


Cây nhị phân
„

Cây nhị phân là cây mà mỗi nút có không
quá 2 con,
con hai cây con này có thể rỗng

Vũ Anh Dũng - Khoa CNTT


(a + (b * c)) + (((d * e) + f) * g)
Vũ Anh Dũng - Khoa CNTT

17


Duyệt cây nhị phân biểu thức
„

„

„

Duyệt theo thứ tự trước : toán tử, con trái,
con phải.
phải Ví dụ : ++a
++a*bc*+*defg
bc + defg
Duyệt theo thứ tự giữa : con trái, toán tử,
con phải.
phải
Duyệt theo thứ tự sau : con trái, con phải,
t á tử.
toán
tử Ví dụ
d : abc*+de*f+g*+
b *+d *f+ *+

Vũ Anh Dũng - Khoa CNTT

thế hai con trỏ trong ngăn xếp được lấy ra,
ra
một cây mới được tạo và con trỏ tới nó
được đNy vào ngăn xếp

Vũ Anh Dũng - Khoa CNTT

20


Xây dựng
cây nhị phân biểu thức
„

Tiếp theo c d e được đọc và ứng với mỗi
toán hạng ta tạo mội nút cây và đNy con trỏ
tương ứng của nó vào ngăn xếp

Vũ Anh Dũng - Khoa CNTT

21


Xây dựng
cây nhị phân biểu thức
„

Tiếp theo dấu + được đọc, vì thế hai cây
được kết hợp