Chương 7: Cây (Tree)
CHƯƠNG VII: CÂY (TREE)
Nội dung chính của chương này đề cập đến một loại đồ thị đơn giản nhất đó là cây. Cây
được ứng dụng rộng rãi trong nhiều lĩnh vực khác nhau của tin học như tổ chức các thư mục, lưu
trữ dữ liệu, biểu diễn tính toán, biểu diễn quyết định và tổ chức truyền tin. Những nội dung được
trình bày bao gồm:
9 Cây và các tính chất cơ bản của cây.
9 Một số ứng dụng quan trọng của cây trong tin học.
9 Cây khung của đồ thị & các thuật toán cơ bản xây dựng cây khung của đồ thị.
9 Bài toán tìm cây khung nhỏ nhất & các thuật toán tìm cây khung nhỏ nhất.
9 Thuật toán Kruskal tìm cây bao trùm nhỏ nhất.
9 Thuật toán Prim tìm cây bao trùm nhỏ nhất.
Bạn đọc có thể tìm thấy những chứng minh cụ thể cho các định lý, tính đúng đắn và độ
phức tạp các thuật toán thông qua các tài liệu [1], [2].
7.1. CÂY VÀ MỘT SỐ TÍNH CHẤT CƠ BẢN
Định nghĩa 1. Ta gọi cây là đồ thị vô hướng liên thông không có chu trình. Đồ thị không
liên thông, không có chu trình được gọi là rừng.
Như vậy, rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây.
Ví dụ. Rừng gồm 3 cây trong hình 7.1. T1 T2 T3
Hình 7.1. Rừng gồm 3 cây T1, T2, T3. 152
Chương 7: Cây (Tree)
Cây được coi là dạng đồ thị đơn giản nhất của đồ thị. Định lý sau đây cho ta một số tính

10
9
8
7
6
10
15
20
25
30
10
6 15
4 8 13 20
3 5 12 14 25
Hình 7.2.

153
Chương 7: Cây (Tree)
Cây nhị phân tìm kiếm rất thuận tiện trong tổ chức lưu trữ và tìm kiếm thông tin. Dưới đây
ta xét các thao tác điển hình trên cây nhị phân tìm kiếm.
Thao tác thêm đỉnh mới vào cây nhị phân tìm kiếm: để thêm đỉnh x vào cây nhị phân
tìm kiếm, ta thực hiện như sau:
 Nếu giá trị khóa của đỉnh x trùng với giá trị khóa tại đỉnh gốc thì không thể thêm
node.
 Nếu giá trị khóa của đỉnh x nhỏ hơn giá trị khóa tại đỉnh gốc và chưa có lá con bên
trái thì thực hiện thêm node vào nhánh bên trái.
 Nếu giá trị khóa của đỉnh x lớn hơn giá trị khóa tại đỉnh gốc và chưa có lá con bên
phải thì thực hiện thêm node vào nhánh bên phải.
Thao tác tìm kiếm đỉnh trên cây nhị phân tìm kiếm: Giả sử ta cần tìm kiếm khóa có giá
trị x trên cây nhị phân tìm kiếm, trước hết ta bắt đầu từ gốc:

< > < >
1 2 3 4
1 2 3 4
1 2 3 4

Hình 7.3. Cây quyết định giải quyết bài toán

Ví dụ 2. Có tám đồng xu trong đó có một đồng xu giả với trọng lượng nhỏ hơn so với 7
đồng xu còn lại. Nếu sử dụng cân thăng bằng thì cần mất ít nhất bao nhiêu lần cân để xác định
đồng xu giả.
Giải. Ta mất ít nhất hai lần cân để xác định đồng xu giả. Vì nếu ta đặt lên bàn cân mỗi bàn
cân ba đồng xu thì có ba kết cục có thể xảy ra. Hoặc ba đồng xu bên trái nhẹ hơn ba đồng xu bên
phải, hoặc ba đồng xu bên trái nặng hơn ba đồng xu bên phải hoặc là chúng thăng bằng. Kết cục
thứ nhất cho ta xác định chính xác đồng xu giả nằm trong số ba đồng xu bên trái và ta chỉ cần mất
một lần cân tiếp theo để xác định đồng xu nào là đồng xu giả. Kết cục thứ hai cho ta biết chính
xác cả ba đồng xu bên phải là thật. Kết cục còn lại cho ta biết chính xác hai đồng xu còn lại có
một đồng xu giả và ta chỉ cần thực hiện một lần cân thăng bằng tiếp theo để xác định đồng xu nào
là giả. Hình 7.4 dưới đây cho ta cây quyết định giải quyết bài toán.

< = > < = > < = >
> <
Hình 7.4. Cây quyết định giải quyết bài toán.

155

hoặc “RCRRA”.
Nếu mã hóa A bởi 0, B bởi 10, R bởi 110 và C bởi 111, khi ấy xâu kí tự S =”BACBARA”
được mã hóa thành S* = “101111001100” sẽ có một cách duy nhất để giải mã.
Mã có tính chất đảm bảo mọi xâu kí tự tương ứng duy nhất với một dạy nhị phân gọi là mã
tiền tố. Mã tiền tố có thể biểu diễn bằng dãy nhị phân, trong đó
a. Các kí tự là khóa của lá trên cây.
b. Cạnh dẫ tới con bên trái được gán nhãn 0.
c. Cạnh dẫn đến con bên phải được gán nhãn 1.
Dãy nhị phân mã hóa một kí tự là dãy các nhãn của cạnh thuộc đường đi duy nhất từ gốc tới
lá tương ứng.

156
Chương 7: Cây (Tree)
Quá trình giải mã được thực hiện như sau: đối chiếu dãy nhị phân S* và cây nhị phân T lưu
trữ bảng mã, lần lượt đi từ gốc T theo chỉ thị của các chữ số trong dãy nhị phân S*, đi theo cạnh
phải nếu bit đang xét có giá trị 1, đi theo cạnh trái nếu bít đang xét có giá trị 0. Khi gặp lá thì dừng
lại xác định một kí tự là khóa của lá. Việc tìm kiếm các khóa tiếp theo được lặp lại như trên.
Ví dụ. Cây nhị phân tương ứng trong hình 7.5 biểu diễn bảng mã: A:0 C:111 B: 10 R: 110

0 1

0 1
0 1

A
B
R C

Hình 7.5. Cây mã hóa tiền tố các kí tự ABRC
7.2.4. Mã Huffman

Kí tự e r t h #3 #2 #1
Số lần xuất hiện 12 7 7 6 6 4 3
 Thay ’#1’ và ‘#2’ bởi một kí tự #4 với số lần xuất hiện là 7
Kí tự e r t h #3 #4
Số lần xuất hiện 12 7 7 6 6 7
 Thay ‘h’ và ‘3’ bởi một kí tự #5 với số lần xuất hiện là 12
Kí tự e r t #5 #4
Số lần xuất hiện 12 7 7 12 7
 Thay ‘r’ và ‘7’ bởi một kí tự #6 với số lần xuất hiện là 14
Kí tự e #6 #5 #4
Số lần xuất hiện 12 14 12 7
 Thay ‘#4’ và ‘#5’ bởi một kí tự #7 với số lần xuất hiện là 19
Kí tự e #6 #7
Số lần xuất hiện 12 14 19
 Thay ‘#6’ và ‘e’ bởi một kí tự #8 với số lần xuất hiện là 26
Kí tự #8 #7
Số lần xuất hiện 26 19
 Thay ‘#7’ và ‘#8’ bởi một kí tự #9 với số lần xuất hiện là 45

158
Chương 7: Cây (Tree)
Kí tự #9
Số lần xuất hiện 45
Cây nhị phân mô tả bảng mã của xâu kí tự S được thể hiện như trong hình 7.6.
45

0 1
26 19
0 1 0 1
14 12 12 7 1

(chuaxet[v] = true) từ đỉnh u thì cạnh (u,v) được kết nạp vào cây bao trùm. Hai kỹ thuật này được
thể hiện trong hai thủ tục STREE_DFS(u) và STREE_BFS(v) như sau:
void STREE_DFS( int u){

159
Chương 7: Cây (Tree)
/* Tìm kiếm theo chiều sâu, áp dụng cho bài toán xây dựng cây bao trùm của đồ thị vô
hướng liên thông G=<V, E>; các biến chuaxet, Ke, T là toàn cục */
chuaxet[u] = true;
for ( v∈ Ke(u) ) {
if (chuaxet[v] ) {
T:= T ∪ (u,v);
STREE_DFS(v);
}
}
}
/* main program */
{
for ( u∈V )
chuaxet[u]:= true;
T = φ;
STREE_DFS(root); /* root là một đỉnh nào đó của đồ thị*/
}
void STREE_BFS(int u){
QUUE=φ;
QUEUE<= u; /* đưa u vào hàng đợi*/
chuaxet[u] = false;
while (QUEUE≠ φ) {
v<= QUEUE; /* lấy v khỏi hàng đợi */
for ( p ∈ Ke(v) ) {

fp= fopen("BAOTRUM1.IN", "r");
if(fp==NULL){
printf("\n Khong co file input");
getch(); return;
}
fscanf(fp,"%d",&n);
printf("\n So dinh do thi:%d", n);
printf("\n Ma tran ke:");
for(i=1; i<=n; i++){
printf("\n");
for(j=1; j<=n; j++){
fscanf(fp, "%d", &A[i][j]);
printf("%3d", A[i][j]);
}

161