Luận văn tốt nghiệp Phan Thanh Long
Chơng 5
Một số vấn đề về cây
I. Các khái niệm và tính chất cơ bản
1. Định nghĩa Cho đồ thị G = <X, U>, G đợc gọi là một cây nếu G liên thông và
không có chu trình, ở đây n = X > 1.
Khi đó sáu tính chất sau là tơng đơng
1) G là đồ thị liên thông và không có chu trình
2) G không có chu trình và có n - 1 cạnh
3) G liên thông và có n - 1 cạnh
4) G không có chu trình và nếu thêm vào một cạnh nối 2 đỉnh không kề nhau thì
G xuất hiện duy nhất một chu trình.
5) G liên thông và nếu bỏ đi một cạnh tuỳ ý thì đồ thị nhận đợc sẽ không liên
thông.
6) Mỗi cặp đỉnh trong G đợc nối với nhau bằng một đờng duy nhất.
Chứng minh: Ta chứng minh theo trình tự sau:
1) 2) 3) 4) 5) 6) 1). Ta sử dụng đẳng thức v(G) = m - n + p là số
chu trình độc lập của đồ thị G = <X, U>, ở đây X = n, U = m và p là số thành
phần liên thông của G.
1) 2): Vì G không có chu trình nên v(G) = m - n + p = 0. Do G liên thông nên p
=1 khi đó m - n + 1 = 0 hay số cạnh m = n - 1.
2) 3): Giả sử G không có chu trình và n - 1 cạnh ta chứng minh 3)
Thật vậy, giả sử ngợc lại G không liên thông, khi đó p 2 . Từ 2) ta có v(G) = m -
n + p = 0 và m = n -1, kết hợp ta có (n - 1) - n + p = 0 hay p = 1, trái với giả thiết p
2. Vậy G liên thông và số cạnh là n -1.
3) 4): Giả sử G là liên thông và có n - 1 cạnh, ta chứng minh 4).
Thật vậy vì G liên thông nên p = 1, mặt khác m = n - 1 nên v(G) = m - n + 1 = 0
hay G không có chu trình . Nếu thêm vào G một cạnh thì ta đợc đồ thị G' với số
cạnh là n, hay v(G') = n - n + 1 = 1 hay G' có một chu trình.
4) 5): Giả sử ngợc lại G không liên thông, tức là tồn tại cặp đỉnh x, y trong G
mà không có đờng nào nối x với y. Khi đó nối x và y bởi 1 cạnh, đồ thị nhận đợc

Hình 1.1
2
a
b
d
i
j
e
h
k
c
g
f
h
a
d
i
j
b
e
k
g
c
f
Luận văn tốt nghiệp Phan Thanh Long
Ví dụ nh hình 1.1 cây T là một cây tự do, nếu chọn a làm gốc thì nó trở thành
cây phân cấp T' có gốc. Với cây T' gốc a có bậc 2 và mức 0, đỉnh c có bậc là 3 và
mức 1 ... Mức cao nhất là 3 ở các đỉnh là lá nh i, j, k nên chiều cao của cây h(T')
= 3.
3. Cây m - phân

0
1
1
1
1
1
1
1
1
a e
i
k o
p u
Luận văn tốt nghiệp Phan Thanh Long
Thuật toán mã hoá Huffman:
Một số thuật toán về mã tiền tố đã ra đời đã đợc sử dụng rộng rãi và đem lại
hiệu quả cao trong vấn đề nén và mã hoá thông tin. Một trong những thuật toán đó
là Huffman xuất hiện từ năm 1952, thuật toán này mã hoá theo phơng pháp kiểu
thống kê, tạo ra mã có độ dài thay đổi khác nhau khi đã có bảng tần số xuất hiện
của các ký tự. Quá trình mã hoá và giải mã phụ thuộc vào việc xây dựng cây nhị
phân mã hoá. Thuật toán Huffman tạo cây nhị phân từ nút lá đến nút gốc, ký tự
nào có tần số càng cao thì nút lá tơng ứng càng gần gốc hơn.
Thuật toán:
Vào: Bảng tần số xuất hiện các ký tự sắp xếp giảm dần
Ra : Cây nhị phân biểu diễn mã, nhánh phải là 1, trái là 0.
Bớc 1: Lấy hai phần tử cuối bảng tần số xuất hiện ra khỏi bảng
Bớc 2: Nếu phần tử nào cha nằm trong cây nhị phân thì tạo ra một nút lá chứa
phần tử đó, phần tử này chính là ký tự. Nối hai nút tơng ứng với hai phần tử này
với nhau thông qua việc tạo nút cha của chúng. Phần tử có tần số xuất hiện lớn
hơn là nút trái, nhỏ hơn là nút phải.

begin
for i:=1 to n do with A[i] do
begin S:=Round(exp(n/5)/exp(i/5))+1;Name:=Char(64+i);Code:=''; end;
end;
Procedure FindCode(m:integer); {Sinh mã huffman}
Var y,z:nod;
k:integer;
Begin
if m=1 then exit;
y:=a[m-1];
a[m-1].s:=a[m-1].s+a[m].s;
5
a,e,f,d,b,c
a,e,f,d b,c
e,f,da
e,f
d
e
f
b
c
0
0
0
0
0
1
1
1
1

trong mang dấu của một phép tính, gốc của cây mang phép tính sau cùng của A, ở
đây là dấu nhân ký hiệu: *, mỗi lá mang 1 số hoặc một chữ đại diện cho số.
Hình 1.4
Một phép duyệt cây là tiền thứ tự nếu thăm gốc trớc rồi sau đó thăm con trái
nh là một cây con với phơng pháp thăm gốc trớc và cuối cùng thăm con phải nh là
một cây con với phơng pháp thăm gốc trớc. Duyệt cây nh vậy mang tính đệ quy.
6
( )






ì+=
2
d
cbaA
a
*
+
-
/
b
c
d
2
Luận văn tốt nghiệp Phan Thanh Long
Khi duyệt cây trên theo tiền thứ tự ta có: * + a b - c / d 2
Cách viết biểu thức theo tiền thứ tự là ký pháp Balan.

a<b<c
b<a a<b
c<a
a<c
c<b
b<c
c<b
b<c
c<a
a<c
Luận văn tốt nghiệp Phan Thanh Long
Begin
Readln(a,b,c);
If Can(a,b) then Begin
If Can(a,c) then Begin
if Can(b,c) then Writeln(c,' ',b,' ',a)
Else Writeln(b,' ',c,' ',a);
End
Else Writeln(b,' ',a,' ',c);
End
Else Begin
If Can(b,c) then Begin
if Can(a,c) then Writeln(c,' ',a,' ',b)
Else Writeln(a,' ',c,' ',b);
End
Else Writeln(a,' ',b,' ',c);
End;
End.
4.4 Cây sắp xếp và tìm kiếm
Sắp xếp và tìm kiếm là một trong những vấn đề cơ bản trong kỹ thuật lập trình,

chèn theo cách này gọi là chèn nhị phân.
Ví dụ để sắp xếp B = x
1
, x
2
, x
3
, ... x
n
ta thực hiện nh sau:
A := ;
For i:=1 to n do Begin
- Tìm vị trí đúng của x
i
trong A theo phơng pháp tìm nhị phân
- Chèn x
i
vào A theo đúng vị trí vừa tìm đợc (A := A {x
i
})
End;
Kết quả A là danh sách sắp xếp của B.
Chơng trình Pascal sau sắp xếp tăng dần theo phơng pháp chèn nhị phân
Const n = 9;
Ds : Array[1..n] of Integer = (1,9,1,6,3,10,10,8,7);
{Ham tra lai vi tri dung cua Pt trong danh sach}
Function FindNp(l,r,Pt: Integer): Integer;
Var t: Integer;
Begin
9

End;
For i:=1 to n do Write(ds[i]:3);
End.
4.4.2 Thuật toán sắp xếp hoà nhập
Giả sử ta có danh sách cha đợc sắp 8, 2, 4, 6, 9, 7, 10, 1, 5 ,3 có thể dùng cây
nhị phân mô tả quá trình sắp xếp danh sách theo thứ tự tăng dần nh sau:
Cây nhị phân với gốc đợc gán là chính là danh sách đó. Các con của gốc đợc
gán theo nguyên tắc: Con bên trái gán nửa danh sách đầu, con bên phải gán nửa
danh sách còn lại (danh sách gán ở gốc cây con trái và cây con phải hoặc bằng
nhau về số lợng hoặc chênh lệch nhau 1 phần tử).
Cứ tiếp tục cho tới khi cây nhị phân có mỗi lá đợc gán 1 phần tử trong dãy. Đó là
cây nh hình 1.7
10