Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 1
Cấutrúcdữ liệuvàGiảithuật
Chương IV: Cấu trúc Cây
Đỗ Bích Diệp - Khoa CNTT
CấutrúcCây
z Nội dung
1. Các khái niệm
2. Cây tổng quát
1. ADT Cây
2. Biểudiễncâytổng quát
3. Duyệtcâytổng quát
3. Cây nhị phân
1. Định nghĩavàtínhchất
2. Duyệt cây nhị phân
3. Biểudiễn cây nhị phân
4. Ứng dụng củacấu trúc cây cho cây biểuthức
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 2
Đỗ Bích Diệp - Khoa CNTT
Định nghĩaCây
− Cây là mộtcấu trúc phi tuyến, thiếtlậptrênmột
tậphữuhạn các “nút”
– Tồntạimộtnútđặcbiệtgọilà“gốc” (root)
– Giữa các nút tồntạimột quan hệ phân cấp hay gọi
là quan hệ cha con
– Mộtnúttrừ nút gốcchỉ có mộtcha
– Mộtnútcóthể có từ 0 đếnn con
Đỗ Bích Diệp - Khoa CNTT
Định nghĩaCây
z Định nghĩa đệ quy về

T1
T2
Tn
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 3
Đỗ Bích Diệp - Khoa CNTT
Ví dụ Cây
Desktop
My
Documents
My Network
Places
My Compute r
CD Driver
(D:)
Window sXP
(C:)
Floppy(A:)
My Received
Files
My Pic t ure s
My Music
Cây thư mụctrongmáytính
Đỗ Bích Diệp - Khoa CNTT
Ví dụ Cây
Cây phân cấpchứcnăng hệ thống thông tin
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 4
Đỗ Bích Diệp - Khoa CNTT
Ví dụ Cây

là nút cha củan
i+1
( i =
1 k-1) là đường đitừ n
1
đếnn
k
A
JH
DCB
E F G I K
L M N
Path from A to M
Length = 3
P
Đỗ Bích Diệp - Khoa CNTT
Các thuậtngữ liên quan đến cây
z Độ sâu hay mức (Depth – Level ) củanút
– Độ dài đường đitừ gốc đếnnútđó+ 1
A
JH
DCB
E F G I K
L M N
Depth 1
Depth 2
Depth 3
Depth 4
P
Cấu trúc dữ liệu và Giải thuật

Đỗ Bích Diệp - Khoa CNTT
Các thuậtngữ liên quan đến cây
z Rừng là mộttậphợphữuhạn các cây phân biệt, không
giao nhau
JH
DCB
E F G I K
L M N
Đỗ Bích Diệp - Khoa CNTT
Các thao tác cơ bảntrênCây
– Cácthaotáctruynhậpcây
z root() : trả ra nút gốccủacây
z parent( Tree T, Node p): trả ra nút cha của nút p trong cây T
z children(Tree T, Node p): trả ra danh sách các nút con của nút p trong
cây T
z left_most_child(Tree T, Node p) : trả ra nút con cựctráicủa nút p
z right_most_child(Tree T, Node p) : trả ra nút con cựcphảicủa nút p
z left_sibling (Tree T, Node p) : trả ra nút anh em kề cận bên trái của nút
p
z right_sibling(Tree T, Node p) : trả ra nút anh em kề cận bên phảicủa
nút p
– Các thao tác khác
z height (Tree T)
z size(Tree T)
z isRoot (Tree T, Node p); isLeaf (Tree T, Node p);
isInternal (Tree T, Node p);
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 8
Đỗ Bích Diệp - Khoa CNTT
Biểudiễn cây tổng quát

Đỗ Bích Diệp - Khoa CNTT
Biểudiễn cây tổng quát
– Dựa trên danh sách các nút con
A
H
D
CB
E G
L N
1
2
3
4
56 7
89
NULL
NULL
NULL
98
NULL
NULL
76
5
432
A[1]
A[2]
A[3]
A[4]
A[5]
A[6]

C
G D
H
I
K
Đỗ Bích Diệp - Khoa CNTT
Duyệt cây theo thứ tự trước
z Duyệtcâylàthăm các nút trên cây
theo mộtthứ tự nhất định, mỗi nút
thăm1 lần
z Khi duyệt theo thứ tự trước, một nút
sẽ đượcthămtrướccáchậuduệ
củanó
z Ứng dụng: In ra các mụclụccủa
mộttàiliệu
I. A
1. B 3.D2. C
2.1 G 2.2 H1.1 E 1.2 F
2.3 I
1
3
5
4
678
9
Algorithm preOrder(v)
visit(v)
for each child w of v
preOrder(w)
2

z Duyệtcâylàthăm các nút trên cây
theo mộtthứ tự nhất định, mỗi nút
thăm1 lần
z Khi duyệt theo thứ tự trước, một nút
sẽ đượcthămtrướccáchậuduệ
củanó
z Ứng dụng: In ra các mụclụccủa
mộttàiliệu
Algorithm preOrder(v)
visit(v)
for each child w of v
preOrder(w)
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 12
Đỗ Bích Diệp - Khoa CNTT
Duyệt cây theo thứ tự trước
⇒
z Duyệtcâylàthăm các nút trên cây
theo mộtthứ tự nhất định, mỗi nút
thăm1 lần
z Khi duyệt theo thứ tự trước, một nút
sẽ đượcthămtrướccáchậuduệ
củanó
z Ứng dụng: In ra các mụclụccủa
mộttàiliệu
Algorithm preOrder(v)
visit(v)
for each child w of v
preOrder(w)
I. A

⇒
z Duyệtcâylàthăm các nút trên cây
theo mộtthứ tự nhất định, mỗi nút
thăm1 lần
z Khi duyệt theo thứ tự trước, một nút
sẽ đượcthămtrướccáchậuduệ
củanó
z Ứng dụng: In ra các mụclụccủa
mộttàiliệu
Algorithm preOrder(v)
visit(v)
for each child w of v
preOrder(w)
I. A
1. B 3. D2. C
2.1 G 2.2 H1.1 E 1.2 F
2.3 I
1
2
3
Đỗ Bích Diệp - Khoa CNTT
Duyệt cây theo thứ tự trước
Thăm nút con
tiếptheo
z Duyệtcâylàthăm các nút trên cây
theo mộtthứ tự nhất định, mỗi nút
thăm1 lần
z Khi duyệt theo thứ tự trước, một nút
sẽ đượcthămtrướccáchậuduệ
củanó

I. A
1. B 3. D2. C
2.1 G 2.2 H1.1 E 1.2 F
2.3 I
1
2
3
Đỗ Bích Diệp - Khoa CNTT
Duyệt cây theo thứ tự trước
⇒
z Duyệtcâylàthăm các nút trên cây
theo mộtthứ tự nhất định, mỗi nút
thăm1 lần
z Khi duyệt theo thứ tự trước, một nút
sẽ đượcthămtrướccáchậuduệ
củanó
z Ứng dụng: In ra các mụclụccủa
mộttàiliệu
Algorithm preOrder(v)
visit(v)
for each child w of v
preOrder(w)
I. A
1. B 3. D2. C
2.1 G 2.2 H1.1 E 1.2 F
2.3 I
1
2
3
4

thăm1 lần
z Khi duyệt theo thứ tự trước, một nút
sẽ đượcthămtrướccáchậuduệ
củanó
z Ứng dụng: In ra các mụclụccủa
mộttàiliệu
Algorithm preOrder(v)
visit(v)
for each child w of v
preOrder(w)
I. A
1. B 3. D2. C
2.1 G 2.2 H1.1 E 1.2 F
2.3 I
1
2
3
4
Thăm nút con
tiếptheocủagốc
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 16
Đỗ Bích Diệp - Khoa CNTT
Duyệt cây theo thứ tự trước
z Duyệtcâylàthăm các nút trên cây
theo mộtthứ tự nhất định, mỗi nút
thăm1 lần
z Khi duyệt theo thứ tự trước, một nút
sẽ đượcthămtrướccáchậuduệ
củanó

1. B 3. D2. C
2.1 G 2.2 H1.1 E 1.2 F
2.3 I
1
2
3
4
⇒
5
Và tiếptụcnhư vậy….
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 17
Đỗ Bích Diệp - Khoa CNTT
Duyệt cây theo thứ tự sau
z Duyệt theo thứ tự sau thì một nút
sẽ đượcthămsaucáchậuduệ
củanó
z Ứng dụng: Xác định kích thước
củacáctệp trong mộtthư mụcvà
các thư mục con của
Algorithm postOrder(v)
for each child w of v
postOrder(w)
visit(v)
cs16/
homeworks/
todo.txt
1K
programs/
DDR.java

inOrder(w)
cs16/
homeworks/
todo.txt
1K
programs/
DDR.java
10K
Stocks.java
25K
h1c.doc
3K
h1nc.doc
2K
Robot.java
20K
4
2
1
6
3
57 8
9
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 18
Đỗ Bích Diệp - Khoa CNTT
Cây nhị phân ( Binary Tree)
– Là cây mà mọi nút trên cây chỉ có tối đalà2 con.
z Cây con củamộtnútcũng cầnphải đượcphânbiệtrõ
ràng thành cây con trái (left subtree) và cây con phải

Đỗ Bích Diệp - Khoa CNTT
Ví dụ cây nhị phân
– Kếtquả thi đấumộtmônthể thao theo cặptạinhiều
vòng
H
A H
H
F
A
E
C
EA D B H G F
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 20
Đỗ Bích Diệp - Khoa CNTT
Các dạng đặcbiệtcủa cây nhị phân
z Cây suy biến (degenerate binary tree)
– Mỗi nút trong củacâycóđúng 1 nút con
A
C
F
G
A
C
F
G
A
C
F
G

Đỗ Bích Diệp - Khoa CNTT
Các dạng đặcbiệtcủa cây nhị phân
z Cây nhị phân hoàn chỉnh
– Là cây nhị phân gần đầy
– Tấtcả các nút ở mứccuối cùng đềulệch về bên trái nhấtcóthể
z Cây nhị phân cân đối
z Cây con trái và cây con phảilệch nhau không quá 1 đơnvị
A
B C
F G
D E
IH JL K
Đỗ Bích Diệp - Khoa CNTT
Tính chấtcủaCâynhị phân
1. Số lượng tối đacủa các nút ở mứci trênmộtcây
nhị phân là 2
i-1
(i >= 1)
2. Số lượng tối đa các nút trên một cây nhị phân có
chiều cao là h là 2
h
– 1 (h >= 1)
3. Một cây nhị phân có n nút có chiềucaotốithiểulà
4. Một cây nhị phân đầy đủ có độ sâu n thì có 2
n
-1
nút
5. Một cây nhị phân hoàn chỉnh có chiều cao h có số
lượng nút nằm trong khoảng 2
h-1

– Ví dụ
– Cây cho ở trên đượclưutrữ trên vector lưutrữ V như sau
A
B
C
D E F G
I K
1
23
4567
89
V[9]V[8]V[7]V[6]V[5]V[4]V[3]V[2]V[1]
KIGFEDCBA
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 23
Đỗ Bích Diệp - Khoa CNTT
Biểudiễn cây nhị phân
z Cách lưutrữ kế tiếp phù hợp để lưutrữ cây nhị phân gần
đầyhoặc đầy đủ
z Vớicácdạng khác có thể dẫn đến lãng phí bộ nhớ
A
C
G
F
1
2
4
8
V[8]V[7]V[6]V[5]V[4]V[3]V[2]V[1]
8

struct Tnode * lptr;
struct Tnode * rptr;
} ;
typedef struct Tnode TREENODE;
typedef TREENODE *TREENODEPTR;
Cấu trúc dữ liệu và Giải thuật
Đỗ Bích Diệp - Khoa CNTT - ĐHBKHN 25
Đỗ Bích Diệp - Khoa CNTT
Duyệt cây nhị phân
– Phép duyệt cây nhị phân
z Phép duyệtmột cây là phép “thăm” lầnlượt các nút trên
cây đósaochomỗi nút chỉđượcthămmộtlần
z Tồntại 3 phép duyệt khác nhau đốivới1 câynhị phân
– Duyệt cây theo thứ tự trước
– Duyệt cây theo thứ tự giữa
– Duyệt cây theo thứ tự sau:
Đỗ Bích Diệp - Khoa CNTT
Duyệt cây nhị phân
– Ví dụ: Thựchiện duyệtcây
z Duyệttheothứ tự trước
A B D H E I J C F G K
z Duyệttheothứ tự giữa
H D B I E J A F C K G
z Duyệttheothứ tự sau
H D I J E B F K G C A
A
B C
F
G
D