Giáo trình Toán rời rạc - Chương 6: Cây

 nhị phân, các thuật toán đó khác nhau chủ yếu ở 
thứ tự thăm các đỉnh. 
 Cây nhị phân T có gốc r được ký hiệu là T(r). Giả sử r có con bên trái là u, con 
bên phải là v. Cây có gốc u và các đỉnh khác là mọi dòng dõi của u trong T gọi là cây 
 95 
con bên trái của T, ký hiệu T(u). Tương tự, ta có cây con bên phải T(v) của T. Một cây 
T(r) có thể không có cây con bên trái hay bên phải. 
 Sau đây là ba trong các thuật toán duyệt cây nhị phân T(r). Các thuật toán đều 
được trình bày đệ quy. Chú ý rằng khi cây T(x) chỉ là môt đỉnh x thì “duyệt T(x)” có 
nghĩa là “thăm đỉnh x”. 
Thí dụ 5: 
6.4.2. Các thuật toán duyệt cây nhị phân: 
1) Thuật toán tiền thứ tự: 
1. Thăm gốc r. 
2. Duyệt cây con bên trái của T(r) theo tiền thứ tự. 
3. Duyệt cây con bên phải của T(r) theo tiền thứ tự. 
 Duyệt cây nhị phân T(a) trong hình trên theo tiền thứ tự: 
1. Thăm a 
2. Duyệt T(b) 
 2.1. Thăm b 
 2.2. Duyệt T(d) 
 2.2.1. Thăm d 
2.2.2. Duyệt T(g) 
 2.2.2.1. Thăm g 
 2.2.2.3. Duyệt T(l): Thăm l 
2.2.3. Duyệt T(h): Thăm h 
 2.3. Duyệt T(e) 
 2.3.1. Thăm e 
 2.3.2. Duyệt T(i) 
 2.3.2.1. Thăm i 
 2.3.2.2. Duyệt T(m): Thăm m 
 2.3.2.3. Duyệt T(n): Thăm n 
3. Duyệt T(c) 
a 
b c 
d e f 
g h i j k 
q s l m n o p 
 96 
 3.1. Thăm c 
 3.3. Duyệt T(f) 
 3.3.1.Thăm f 
 3.3.2. Duyệt T(j) 
 3.3.2.1. Thăm j 
 3.3.2.2. Duyệt T(o): Thăm o 
 3.3.2.3. Duyệt T(p): Thăm p 
 3.3.3. Duyệt T(k) 
 3.3.3.1. Thăm k 
 3.3.3.2. Duyệt T(q): Thăm q 
 3.3.3.3. Duyệt T(s): Thăm s 
 Kết quả duyệt cây T(a) theo tiền thứ tự là: 
a, b, d, g, l, h, e, i, m, n, c, f, j, o, p, k, q, s. 
2) Thuật toán trung thứ tự: 
1. Duyệt cây con bên trái của T(r) theo trung thứ tự. 
2. Thăm gốc r. 
3. Duyệt cây con bên phải của T(r) theo trung thứ tự. 
Duyệt cây nhị phân T(a) trong hình trên theo trung thứ tự: 
1. Duyệt T(b) 
 1.1. Duyệt T(d) 
 1.1.1. Duyệt T(g) 
 1.1.1.2. Thăm g 
 1.1.1.3. Duyệt T(l): thăm l 
 1.1.2. Thăm d 
 1.1.3. Duyệt T(h): Thăm h 
 1.2. Thăm b 
 1.3. Duyệt T(e) 
 1.3.1. Duyệt T(i) 
 1.3.1.1. Duyệt T(m): Thăm m 
 1.3.1.2. Thăm i 
 1.3.1.3. Duyệt T(n): Thăm n 
 1.3.2. Thăm e 
2. Thăm a 
3. Duyệt T(c) 
 3.2. Thăm c 
 3.3. Duyệt T(f) 
 3.3.1. Duyệt T(j) 
 97 
 3.3.1.1. Duyệt T(o): Thăm o 
 3.3.1.2. Thăm j 
 3.3.1.3. Duyệt T(p): Thăm p 
 3.3.2. Thăm f 
 3.3.3. Duyệt T(k) 
 3.3.3.1. Duyệt T(q): Thăm q 
 3.3.3.2. Thăm k 
 3.3.3.3. Duyệt T(s): Thăm s 
 Kết quả duyệt cây T(a) theo trung thứ tự là: 
g, l, d, h, b, m, i, n, e, a, c, o, j, p, f, q, k, s. 
3) Thuật toán hậu thứ tự: 
1. Duyệt cây con bên trái của T(r) theo hậu thứ tự. 
2. Duyệt cây con bên phải của T(r) theo hậu thứ tự. 
3. Thăm gốc r. 
Duyệt cây nhị phân T(a) trong hình trên theo hậu thứ tự: 
1. Duyệt T(b) 
 1.1. Duyệt T(d) 
 1.1.1. Duyệt T(g) 
 1.1.1.2. Duyệt T(l): thăm l 
 1.1.1.3. Thăm g 
 1.1.2. Duyệt T(h): thăm h 
 1.1.3. Thăm d 
 1.2. Duyệt T(e) 
 1.2.1. Duyệt T(i) 
 1.2.1.1. Duyệt T(m): Thăm m 
 1.2.1.2. Duyệt T(n): Thăm n 
 1.2.1.3. Thăm i 
 1.2.3. Thăm e 
 1.3. Thăm b 
2. Duyệt T(c) 
 2.2. Duyệt T(f) 
 2.2.1. Duyệt T(j) 
 2.2.1.1. Duyệt T(o): Thăm o 
 2.2.1.2. Duyệt T(p): Thăm p 
 2.2.1.3. Thăm j 
 2.2.2. Duyệt T(k) 
 2.2.2.1. Duyệt T(q): Thăm q 
 98 
 2.2.2.2. Duyệt T(s): Thăm s 
 2.2.2.3. Thăm k 
 2.2.3. Thăm f 
 2.3. Thăm c 
3. Thăm a 
 Kết quả duyệt cây T(a) theo trung thứ tự là: 
l, g, h, d, m, n, i, e, b, o, p, j, q, s, k, f, c, a. 
6.4.3. Ký pháp Ba Lan: 
 Xét biểu thức đại số sau đây: 
(a+b)(c
2
d
) (1) 
 Ta vẽ một cây nhị phân như hình dưới đây, trong đó mỗi đỉnh trong mang dấu 
của một phép tính trong (1), gốc của cây mang phép tính sau cùng trong (1), ở đây là 
dấu nhân, ký hiệu là  , mỗi lá mang một số hoặc một chữ đại diện cho số. 
Duyệt cây nhị phân trong hình trên theo trung thứ tự là: 
a + b  c  d / 2 (2) 
và đây là biểu thức (1) đã bỏ đi các dấu ngoặc. 
 Ta nói rằng biểu thức (1) được biểu diễn bằng cây nhị phân T() trong hình trên, 
hay cây nhị phân T() này tương ứng với biểu thức (1). Ta cũng nói: cách viết (ký pháp) 
quen thuộc trong đại số học như cách viết biểu thức (1) là ký pháp trung thứ tự kèm theo 
các dấu ngoặc. 
 Ta biết rằng các dấu ngoặc trong (1) là rất cần thiết, vì (2) có thể hiểu theo nhiều 
cách khác (1), chẳng hạn là 
 (a + b  c)  d / 2 (3) 
hoặc là a + (b  c  d) / 2 (4) 
 Các biểu thức (3) và (4) có thể biểu diễn bằng cây nhị phân trong các hình sau. 
Hai cây nhị phân tương ứng là khác nhau, nhưng đều được duyệt theo trung thứ tự là 
(2). 

+  
a b c / 
2 d 
 99 
 Đối với cây trong hình thứ nhất, nếu duyệt theo tiền thứ tự, ta có 
 + a b  c / d 2 (5) 
và nếu duyệt theo hậu thứ tự, ta có: 
a b + c d 2 /   (6) 
 Có thể chứng minh được rằng (5) hoặc (6) xác định duy nhất cây nhị phân trong 
hình thứ nhất, do đó xác định duy nhất biểu thức (1) mà không cần dấu ngoặc. Chẳng 
hạn cây nhị phân trên hình thứ hai được duyệt theo tiền thứ tự là 
 + a  b c / d 2 khác với (5). 
và được duyệt theo hậu thứ tự là 
a b c  + d 2 /  khác với (6). 
 Vì vậy, nếu ta viết các biểu thức trong đại số, trong lôgic bằng cách duyệt cây 
tương ứng theo tiền thứ tự hoặc hậu thứ tự thì ta không cần dùng các dấu ngoặc mà 
không sợ hiểu nhầm. 
 Người ta gọi cách viết biểu thức theo tiền thứ tự là ký pháp Ba Lan, còn cách viết 
theo hậu thứ tự là ký pháp Ba Lan đảo, để ghi nhớ đóng góp của nhà toán học và lôgic 
học Ba Lan Lukasiewicz (1878-1956) trong vấn đề này. 
+ / 
a 
d 2 
c b 
 
a / 
d 
 2 
c 
b 
+ 
 100 
 Việc chuyển một biểu thức viết theo ký pháp quen thuộc (có dấu ngoặc) sang 
dạng ký pháp Ba Lan hay ký pháp Ba Lan đảo hoặc ngược lại, có thể thực hiện bằng 
cách vẽ cây nhị phân tương ứng, như đã làm đối với biểu thức (1). Nhưng thay vì vẽ cây 
nhị phân, ta có thể xem xét để xác định dần các công thức bộ phận của công thức đã 
cho. Chẳng hạn cho biểu thức viết theo ký pháp Ba Lan là 
   /   a b  5 c 2 3   c d 2    a c d /   b  3 d 3 5 
 Trước hết, chú ý rằng các phép toán +, , *, /,  đều là các phép toán hai ngôi, vì 
vậy trong cây nhị phân tương ứng, các đỉnh mang dấu các phép toán đều là đỉnh trong 
và có hai con. Các chữ và số đều đặt ở lá. Theo ký pháp Ba Lan (t.ư. Ba Lan đảo) thì 
T a b (t.ư. a b T) có nghĩa là a T b, với T là một trong các phép toán +, , *, /, . 
  533*/*2325*/*
35 dcadccba
dbdcadccba 


53)3(/)(*2)(325)(/*
3)(5 2

dbdcadccba
dbdcadccba

 
53)3(/)(*)(32)5(/*
3)3(
2
2
5
  
dbcba
dbdcadccba

 


5
)3(
32
2
5
3
3
5)3(/)(*)(3
2
5
*
db
cba
dbdcadc
cba






 


 
    
5
)3(
)(
3
)(
2
5
2
3
3
2
3
5
)3(
)(*)(
2
5
*
db
dcadc
cba
db
dcadc
cba






 






 
 
5
)3(
)()(
2
5 32
3
db
dcadc
cba 





 
 101 
BÀI TẬP CHƯƠNG VI: 
1. Vẽ tất cả các cây (không đẳng cấu) có: 
a) 4 đỉnh b) 5 đỉnh c) 6 đỉnh 
2. Một cây có n2 đỉnh bậc 2, n3 đỉnh bậc 3, …, nk đỉnh bậc k. Hỏi có bao nhiêu đỉnh bậc 
1? 
3. Tìm số tối đa các đỉnh của một cây m-phân có chiều cao h. 
4. Có thể tìm được một cây có 8 đỉnh và thoả điều kiện dưới đây hay không? Nếu có, vẽ 
cây đó ra, nếu không, giải thích tại sao: 
 a) Mọi đỉnh đều có bậc 1. 
 b) Mọi đỉnh đều có bậc 2. 
 c) Có 6 đỉnh bậc 2 và 2 đỉnh bậc 1. 
 d) Có đỉnh bậc 7 và 7 đỉnh bậc 1. 
5. Chứng minh hoặc bác bỏ các mệnh đề sau đây. 
 a) Trong một cây, đỉnh nào cũng là đỉnh cắt. 
 b) Một cây có số đỉnh không nhỏ hơn 3 thì có nhiều đỉnh cắt hơn là cầu. 
6. Có bốn đội bóng đá A, B, C, D lọt vào vòng bán kết trong giải các đội mạnh khu vực. 
Có mấy dự đoán xếp hạng như sau: 
 a) Đội B vô địch, đội D nhì. 
 b) Đội B nhì, đội C ba. 
 c) Đọi A nhì, đội C tư. 
 Biết rằng mỗi dự đoán trên đúng về một đội. Hãy cho biết kết quả xếp hạng của 
các đội. 
7. Cây Fibonacci có gốc Tn đuợc dịnh nghĩa bằng hồi quy như sau. T1 và T2 đều là cây 
có gốc chỉ gồm một đỉnh và với n=3,4, … cây có gốc Tn được xây dựng từ gốc với Tn-1 
như là cây con bên trái và Tn-2 như là cây con bên phải. 
 a) Hãy vẽ 7 cây Fibonacci có gốc đầu tiên. 
b) Cây Fibonacci Tn có bao nhiêu đỉnh, lá và bao nhiêu đỉnh trong. Chiều cao 
của nó bằng bao nhiêu? 
8. Hãy tìm cây khung của đồ thị sau bằng cách xoá đi các cạnh trong các chu trình đơn. 
 a) 
a b c 
d e f g 
h i j 
 102 
 b) 
9. Hãy tìm cây khung cho mỗi đồ thị sau. 
 a) K5 b) K4,4 c) K1,6 
 d) Q3 e) C5 f) W5. 
10. Đồ thị Kn với n=3, 4, 5 có bao nhiêu cây khung không đẳng cấu? 
11. Tìm cây khung nhỏ nhất của đồ thị sau theo thuật toán Kruskal và Prim. 
12. Tìm cây khung nhỏ nhất bằng thuật toán Prim của đồ thị gồm các đỉnh A, B, C, D, 
E, F, H, I được cho bởi ma trận trọng số sau. 


































18142112191120
18172321201932
14173430212018
21233422292419
12213022133323
19202129131315
11192024331316
20321819231516
. 
Yêu cầu viết các kết quả trung gian trong từng bước lặp, kết quả cuối cùng cần đưa ra 
tập cạnh và độ dài của cây khung nhỏ nhất. 
a b 
c d e 
h 
f 
i 
k 
g 
j 
l 
a b 
c d e f 
g h 
42 
14 10 4 
3 1 11 
3 
15 
5 
7 
20 9 
A B C D E F G 
A
H 
B 
C 
D 
E 
F 
G 
H 
 103 
13. Duyệt các cây sau đây lần lượt bằng các thuật toán tiền thứ tự, trung thứ tự và hậu 
thứ tự. 
 a) b) 
14. Viết các biểu thức sau đây theo ký pháp Ba Lan và ký pháp Ba Lan đảo. 
 a) 
BDC
BDA
DCBA
DCBA





2
2
)(
))((
. 
 b) 
5
)243(
3
5
3
)(
342
4 dbadad
c
ba






 






 . 
15. Viết các biểu thức sau đây theo ký pháp quen thuộc. 
 a) x y + 2 ↑ x y − 2 ↑ − x y * /. 
b)    /   a b  3 c 2 4   c d 5    a c d /   b  2 d 4 3. 
a 
c b 
d e 
g 
 f 
h 
i j 
e d g f 
b c 
a 
h i 
m n 
 j k 
p q 
l 
o