Bài giảng chương 4: Cây trong Cấu trúc giữ liệu và giải thuật

Bài giảng chương 4: Cây trong Cấu trúc giữ liệu và giải thuật của Đại học Bách Khoa Hà Nội với những kiến thức và thông tin bổ ích giúp sinh viên tham khảo, ôn luyện và phục vụ nhu cầu học tập của mình cụ thể là có định hướng ôn tập, nắm vững kiến thức môn học và làm bài tốt trong những bài kiểm tra, bài tiểu luận, bài tập kết thúc học phần, từ đó học tập tốt và có kết quả cao cũng như có thể vận dụng tốt những kiến thức mình đã học vào thực tiễn cuộc sống. Mời bạn đọc đón xem!

Chương 4
CÂY
Nội dung
4.1. Định nghĩa và các khái niệm
4.2. Cây nhị phân
4.3. Các ứng dụng
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
2
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
4.1. Định nghĩa và khái niệm
4.1.1. Định nghĩa
4.1.2. Các thuật ng
4.1.3. Cây có thứ tự
4.1.4. Cây có nhãn
4.1.5. ADT cây
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
3
4.1.1. Định nghĩa cây
Cây bao gồm các nút, một nút đặc biệt được gọi gốc (root)
các cạnh nối các nút. Cây được định nghĩa đệ qui như sau:
Định nghĩa cây:
Basic Step: Một nút r là cây và r được gọi là gốc của cây này.
Recursive Step: Giả sử T
1
,T
2
,...,T
k
các cây với gốc r
1
,r
2
,...,r
k
.
Ta thể xây dựng cây mới bằng cách đặt r làm cha (parent) của
các nút r
1
,r
2
,..., r
k
. Trong cây này r là gốc T
1
, T
2
, . . . , T
k
các
cây con của gốc r. Các nút r
1
, r
2
, . . . , r
k
được gọi con (children)
của nút r.
Chú ý: Nhiều khi để phù hợp ta cần định nghĩa cây rỗng (null
tree) cây không nút nào cả.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
4
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Cấu trúc đệ qui của cây
r
r
1
r
k
r
2
T
1
T
2
T
k
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
5
Cây trong thực tế ứng dụng
Biểu đồ lịch thi đấu
Cây gia phả
Biểu đồ phân cấp quản lý hành chính.
Cây thư mục
Cấu trúc ca một quyn ch
Cây biểu thức
Cây phân hoạch tập hợp
...
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYN ĐƯC NGHĨA - B môn KHMT
6
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Cây lịch thi đấu
1/28/2013
Trong đi thườngy rt hay được s dng đ din t
lch thi đu cac gii th thao theo th thc đu loi
trc tiếp, chng hn vòng 2 ca World Cub
Pp
Tây ban nha
Brazin
Anh
Đc
Ucrain
Italia
Ahentina
Pp
Brazin
Đc
Italia
Pp
Italia
Italia
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
7
Cây gia phả
1/28/2013
Cây gia ph ca các nhà toán dòng h Bernoulli
Nikolaus
1623-1708
Johan I
1667-1748
Nikolaus
1662-1716
Jacob I
1654-1705
Nikolaus II
1695-1726
Daniel
1700-1782
Johan II
1710-1790
Nikolaus I
1687-1759
Jacob II
1759-1789
Johan III
1746-1807
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
8
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Cây phân cấp quản lý hành chính
Ban Giám đốc
Phòng
Tài vụ
Phòng
Tổ chức
Phòng
Hành chính
Phòng
Kinh doanh
Phòng
Kế hoạch
Văn thưTP
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
9
Cây thư mục
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYN ĐƯC NGHĨA - B môn KHMT
10
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Cây mục lục sách
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
11
Cây gia phả ngược (Ancestor Tree)
1/28/2013
Cây ph h ngược: mi người đu có b m. Cây
y cây nh pn (binary tree).
Thùy Hương
Thúy Ci
Quang Dũng
Bích Liên
Trung Kiên Hoàng Cúc Quang Ti
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
12
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Cây biểu thức (Expression Tree)
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
/
+
/
1
3 *
6 7
4
1/3 + 6*7 / 4
13
Cây phân hoạch tập hợp
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYN ĐƯC NGHĨA - B môn KHMT
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Tập con các số lẻ:
{1, 3, 5, 7, 9}
Tập con các số chẵn:
{ 2, 4, 6, 8, 10}
Tập con các số nguyên tố:
{ 3, 5, 7 }
{1, 9}
Tập con số hoàn hảo:
{ 6 }
{ 2, 4, 8, 10}
14
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
4.1. Định nghĩa và khái niệm
4.1.1. Định nghĩa
4.1.2. Các thuật ngữ
4.1.3. Cây có thứ tự
4.1.4. Cây có nhãn
4.1.5. ADT cây
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
15
4.1.2. Các thuật ngữ chính
Nút - node
Gốc - root
Lá - leaf
Con - child
Cha - parent
Tổ tiên - ancestors
Hậu duệ - descendants
Anh em - sibling
Nút trong - internal node
Chiều cao - hight
Chiều sâu - depth
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
16
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Các thuật ngữ chính
Nếu n
1
, n
2
, . . . , n
k
dãy t trên cây sao cho n
i
cha của n
i+1
với 1 i < k, thì dãy
này được gọi đường đi (path) từ nút n
1
tới nút n
k
. Độ dài (length) của đường đi
bằng số lượng nút trên đường đi trừ bớt 1. Như vậy đường đi độ dài 0 đường đi từ
một nút đến chính nó.
Nếu đường đi từ nút a tới nút b, thì a được gọi tổ tiên (ancestor) của b, còn b
được gọi hậu duệ (descendant) của a.
Tổ tiên (hậu duệ) của một nút khác với chính được gọi tổ tiên (hậu duệ) chính
thường (proper). Trong cây, gốc là t không tổ tiên chính thường mọi nút khác
trên cây đều hậu duệ chính thường của nó.
Một nút không hậu duệ chính thường được gọi (leaf).
Các nút cùng cha được gọi anh em (sibling).
Cây con (subtree) của một cây một nút cùng với tất cả các hậu duệ của nó.
Chiều cao (height) của nút trên cây là bằng đ dài của đường đi dài nhất từ nút đó
đến cộng 1. Chiều cao của cây (height of a tree) chiều cao của gốc. Độ sâu/mức
(depth/level) của nút bằng 1 cộng với độ dài của đường đi duy nhất từ gốc đến .
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
17
Thuật ngữThuật ngữ
nút
nodes
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
18
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Thuật ngữThuật ngữ
Nút cha
parent node
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
19
Thuật ngữThuật ngữ
con
child
cha
parent
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
20
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Thuật ngữThuật ngữ
con
cha
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
21
Thuật ngữThuật ngữ
gốc - root
lá - leaf
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
22
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Thuật ngữThuật ngữ
cây con - subtree
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
23
Thuật ngữThuật ngữ
cây con
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
24
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Thuật ngữThuật ngữ
cây con
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
25
Các thuật ngữ vi cây có gốc
a
b
d
e f
i
j
g
h
c
k
root, ancestor
parent
nút
child child
descendent
leaf (không có con)
e, i, k, g, h
là lá (leaves)
internal node
(không là lá)
sibling
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYN ĐƯC NGHĨA - B môn KHMT
26
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Đường đi trên cây
a
c
b
e
f
d
g
j
i
h
Path 1
Path 2
Path 1: { a, b, f, j }
Path 2: { d, i }
Từ cha đến con và đến
các nút hậu duệ.
Có duy nhất 1 đường đi từ
một nút đến một nút là
hậu duệ của nó.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
27
Độ cao (height) và độ sâu/mức (depth/level)
7
3 10
8
4
12
1
6 5
211
9
độ cao h = 5
độ sâu 1
độ sâu 2
độ sâu 3
độ sâu 4
độ sâu 5
độ cao = 4
độ cao = 3
độ cao h=1
h = 2
Độ cao của cây là 5
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
28
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
How We View a TreeHow We View a Tree
Nature Lovers View Computer Scientists View
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
29
Bậc (Degree)
9
Số lượng con của nút
x được gọi là
bậc (degree) của x.
degree = 3
7
3 10
8
4
12
1
6 5
211
degree = 1
degree = 0
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
30
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
4.1. Định nghĩa và khái niệm
4.1.1. Định nghĩa
4.1.2. Các thuật ng
4.1.3. Cây có thứ tự
4.1.4. Cây có nhãn
4.1.5. ADT cây
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
31
4.1.3. Cây có thứ tự - Ordered Tree
Thứ tự của các nút
Các con của một nút thường được xếp thứ tự từ trái sang phải. Như
vậy hai cây trong hình sau đây là khác nhau, bởi vì hai con của nút
a xuất hiện trong hai cây theo thứ tự khác nhau:
Cây với các t được xếp thứ tự được gọi là cây thứ tự. Ta sẽ xét
chủ yếu cây thứ tự. vậy, tiếp theo thuật ngữ y là để chỉ
cây thứ tự. Khi muốn khẳng định là không quan m đến thứ tự,
ta sẽ phải nói cây không thứ tự.
a
b
c
a
c
b
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYN ĐƯC NGHĨA - B môn KHMT
32
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Xếp thứ tự các nút
Ta thể xếp thứ tự các nút của y theo nhiều cách. ba
thứ tự quan trọng nhất, đó Thứ tự trước, Th tự sau
Thứ tự giữa (Preorder, Postorder, Inorder)
Các thứ tự y được định nghĩa một cách đệ qui như sau
Nếu y T rỗng, thì danh sách rỗng danh sách theo thứ
tự trước, thứ tự sau thứ tự giữa của cây T.
Nếu y T một nút, thì nút đó chính danh sách theo
thứ tự trước, thứ tự sau thứ tự giữa của cây T.
Trái lại, giả sử T y gốc r với các y con T
1
, T
2
,...,
T
k.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
33
Duyệt theo thứ tự trước - Preorder Traversal
Thứ tự trước (hay duyệt theo thứ t trước - preorder
traversal) của các nút của T là:
Gốc r của T,
tiếp đến là các nút của T
1
theo thứ tự trước,
tiếp đến là các nút của T
2
theo thứ tự trước,
...
cuối cùng là các nút của T
k
theo thứ tự trước.
r
r
1
r
k
r
2
T
1
T
2
T
k
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
34
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Duyệt theo thứ tự sau - Postorder Traversal
Thứ tự sau của các nút của cây T là:
Các nút của T
1
theo thứ tự sau,
tiếp đến là các nút của T
2
theo thứ tự sau,
...
các nút của T
k
theo thứ tự sau,
sau cùng làt gốc r.
r
r
1
r
k
r
2
T
1
T
2
T
k
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
35
Duyệt theo thứ tự giữa - Inorder Traversal
Thứ tự giữa của các nút của cây T là:
Các nút của T
1
theo thứ tự giữa,
tiếp đến là nút gốc r,
tiếp theo là các nút của T
2
, . . . , T
k
, mỗi nhóm nút được xếp theo thứ tự
giữa.
r
r
1
r
k
r
2
T
1
T
2
T
k
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
36
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Thuật toán duyệt theo thứ tự trước - Preorder Traversal
void PREORDER ( nodeT r )
{
(1) Đưa ra r;
(2) for (mỗi con c của r, nếu có, theo thứ tự từ trái sang) do
PREORDER(c);
}
Ví dụ: Thứ tự trước của các đỉnh của cây trên hình vẽ là
a, b, c, e, h, i, f, j, d, g
a
b
c d
f
g
ih
e
j
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
37
Thuật toán duyệt theo thứ tự sau - Postorder Traversal
Thuật toán duyệt theo thứ tự sau thu được bằng cách đảo ngược hai thao
tác (1) và (2) trong PREORDER:
void POSTORDER ( nodeT r )
{
for (mỗi con c của r, nếu , theo thứ tự từ trái sang) do
POSTORDER(c)
Đưa ra r;
}
Ví dụ: Dãy các đỉnh được liệt kê theo thứ tự sau của cây trong hình vẽ là:
b, h, i, e, j, f, c, g, d, a
a
b
c d
f
g
ih
e
j
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYN ĐƯC NGHĨA - B môn KHMT
38
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Thuật toán duyệt theo thứ tự giữa - Inorder Traversal
void INORDER (nodeT r )
{
if ( r ) Đưa ra r;
else
{
INORDER(con trái nhất của r);
Đưa ra r;
for (mỗi con c của r, ngoại trừ con trái nhất, theo thứ tự từ trái sang) do
INORDER(c);
}
}
Ví dụ: Dãy các đỉnh của cây trong hình vẽ được liệt kê theo thứ tự giữa:
b, a, h, e, i, c, j, f, g, d
a
b
c d
f
g
ih
e
j
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
39
Xếp thứ tự các nút
Để nhcách đưa ra các nút theo ba thứ tự
vừa trình bày hãy hình dung là ta đi vòng
quanh bên ngoài cây bắt đầu từ gốc, ngược
chiều kim đồng hồ và sát theo cây nhất.
Chẳng hạn, đường đi đó đối với cây trong
các ví dụ đã xét trên như sau:
a
b
c d
f
g
ih
e
j
Đối với thứ tự trước, ta đưa ra nút mỗi khi đi qua .
Đối với
thứ tự sau, ta đưa ra nút khi qua lần cuối trước khi
quay về cha của nó.
Đối với
thứ tự giữa, ta đưa ra ngay khi đi qua , còn những nút
trong được đưa ra khi lần thứ hai được đi qua.
Chú ý rằng c được xếp thứ tự từ trái sang phải như nhau trong cả
ba cách sắp xếp.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
40
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
4.1.4. Cây có nhãn (Labeled Tree)
Thông thường người ta gán cho mỗi nút của cây một nhãn (label)
hoặc một giá trị, cũng tương tự như chúng ta đã gán mỗi nút của
danh sách với một phần tử. Nghĩa là, nhãn của nút không phải tên
gọi của nút mà giá trị được cất giữ trong nó. Trong một số ứng
dụng ta thể thay đổi nhãn của nút tên của vẫn được giữ
nguyên.
Ví dụ: Xét cây có 7 nút n
1
, ..., n
7
. Ta gán nhãn cho các nút như sau:
Nút n
1
có nhãn *;
Nút n
2
có nhãn +;
Nút n
3
có nhãn -;
Nút n
4
có nhãn a;
Nút n
5
có nhãn b;
Nút n
6
có nhãn a;
Nút n
7
có nhãn c.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
n
1
*
+
-
a
n
3
n
6
n
7
n
5
n
4
n
2
b
a
c
41
Cây biểu thức (Expression Tree)
Cây trong ví dụ vừa nêu có tên gọi là cây biểu thức
(a+b)*(a-c)
Qui tắc để cây có nhãn biểu diễn một biểu thức là:
Mỗi nút nhãn toán hạng chỉ gồm một toán hạng đó. dụ nút n
4
biểu
diễn biểu thức a.
Mỗi nút trong n đưc gán nhãn là phép toán. Gi s n có nhãn là phép toán hai
ngôi q, như + hoặc *, con trái biểu diễn biểu thức E
1
con phải biểu diễn
biểu thức E
2
. Khi đó n biểu diễn biểu thức (E
1
) q (E
2
). Ta thể b dấu ngoặc
nếu như điều đó không cần thiết.
dụ:
Nút n
2
chứa toán hạng + và con trái
và con phải của nó là a b. Vì thế
n
2
biểu diễn (a) + (b), hay a+b.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYN ĐƯC NGHĨA - B môn KHMT
n
1
*
+
-
a
n
3
n
6
n
7
n
5
n
4
n
2
b
a
c
42
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
4.1. Định nghĩa và khái niệm
4.1.1. Định nghĩa
4.1.2. Các thuật ng
4.1.3. Cây có thứ tự
4.1.4. Cây có nhãn
4.1.5. ADT cây
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
43
4.1.5. ADT Cây
Trong chương y chúng ta tìm hiểu cây vừa như kiểu dữ
liệu trừu tượng vừa như là kiểu dữ liệu. Một trong những ứng
dụng quan trọng của y được dùng để thiết kế cài đặt
nhiều kiểu dữ liu tru tưng quan trọng khác n "Cây tìm
kiếm nhị phân", "Tập hợp",....
Cũng như danh sách, đối với cây cũng thể xét rất nhiều
phép toán làm việc với nó. Dưới đây ta chỉ kể ra một số phép
toán cơ bản.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
44
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
4.1.5. ADT Cây
parent(n, T). Hàm này trả lại cha của nút n trong y T. Nếu
n gốc (nó không cha), trả lại
. Theo nghĩa này, nút
rỗng ("null node") dùng để báo hiệu rằng chúng ta sẽ dời khỏi
cây.
leftmost_child(n, T) trả lại con trái nhất của nút n trong cây T,
và trả lại nếu n là lá (không có con).
right_sibling(n, T) trả lại em bên phải của nút n trong cây T
(được định nghĩa như nút m cùng cha p giống như n
sao cho m nằm sát bên phải của n trong danh ch sắp thứ tự
các con của p.
Ví dụ, với cây trong slide gần nhất:
leftmost_child(n
2
) = n
4
;
right_sibling(n
4
) = n
5
, và RIGHT_SIBLING (n
5
) = L.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
45
4.1.5. ADT Cây
label(n, T) trả lại nhãn của nút n trong y T. Tuy nhiên, ta
không đòi hỏi cây nào cũng nhãn.
createi(v, T
1
, T
2
, . . . , T
i
) họ các hàm, mỗi hàm cho một giá
trị của i = 0, 1, 2, ... createi tạo một nút mới r với nhãn v
gắn cho i con, với các con là các gốc của cây T
1
, T
2
, ..., T
i
,
theo thứ tự từ trái sang. Trả lại cây với gốc r. Chú ý, nếu i = 0,
thì r vừa vừa gốc.
root(T) trả lại nút gốc của cây T, hoặc nếu T cây rỗng.
makenull(T) biến T thành cây rỗng.
1/28/2013
CẤU TRÚC DỮ LIỆU THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
46
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Biểu diễn cây
Có nhiều cách biểu diễn cây. Ta giới thiệu qua về ba cách biểu
diễn cơ bản:
dùng mảng (Array Representation)
danh sách các con (Lists of Children)
dùng con trái em phải (The Leftmost-Child, Right-
Sibling Representation)
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
47
Biểu diễn cây dùng mảng
Giả sử T cây với các nút đặt tên 1, 2, . . . , n. Cách đơn giản để
biểu diễn T là hỗ trợ thao tác parent bởi danh sách tuyến tính A
trong đó mỗi phần tử A[i] chứa con trỏ đến cha của nút i. Riêng gốc
của T thể phân biệt bởi con trỏ rỗng.
Khi dùng mảng, ta đặt A[i] = j nếu nút j cha của nút i, A[i] = 0
nếu nút i gốc.
Cách biểu diễn này dựa trên cơ sở mỗi nút của cây (ngoại trừ gốc)
đều duy nhất một cha. Với cách biểu diễn này cha của một nút
thể xác định trong thời gian hằng số. Đường đi từ một nút đến t
tiên của chúng (kể cả đến gốc) thể xác định dễ dàng:
n <- parent(n) <- parent(parent(n)) <- ...
Ta cũng thể đưa thêm vào mảng L[i] để hỗ trợ việc ghi nhận nhãn
cho các nút, hoặc biến mỗi phần tử A[i] thành bản ghi gồm hai
trường: biến nguyên ghi nhận cha nhãn.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
48
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Biểu diễn cây dùng mảng
Ví dụ
A
Hạn chế: Cách dùng con trỏ cha không thích hợp cho các thao tác với con. Cho nút
n, ta sẽ mất nhiều thời gian để xác định các con của n, hoặc chiều cao của n. Hơn
nữa biểu diễn bởi con trỏ cha không cho ta thứ tự của các nút con. Vì thế các phép
toán như leftmost_child right_sibling không xác định được. Do đó cách biểu
diễn này chỉ dùng trong một số trường hợp nhất định.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1
3
6
10
54
2
9
7 8
0 1 1 2 2 3 6 6 6 3
49
Danh sách các con (Lists of Children)
Trong cách biểu diễn y, với mỗi nút của cây ta cất giữ một
danh ch các con của nó.
Danh sách con thể biểu diễn bởi một trong những cách biểu
diễn danh sách đã trình y trong cơng trưc.
Tuy nhiên, để ý rằng s lượng con của các nút rất khác
nhau, nên danh ch móc nối thường lựa chọn thích hợp
nhất.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYN ĐƯC NGHĨA - B môn KHMT
50
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Danh sách các con (Lists of Children)
Có mng con trỏ đến đầu các danh sách con của các nút 1, 2, . . . , 10:
header[i] trỏ đến danh sách con của nút i.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1
3
6
10
54
2
9
7 8
1 2 3
2 4 5
3 6 10
4
5
6 7 8 9
7
8
9
10
header
51
Danh sách các con (Lists of Children)
Ví dụ: Có thể sử dụng mô tả sau đây để biểu diễn cây
typedef ? NodeT; /* dấu ? cần thay bởi định nghĩa kiểu phù hợp */
typedef ? ListT; /* dấu ? cần thay bởi định nghĩa kiểu danh sách phù hợp */
typedef ? position;
typedef struct
{
ListT header[maxNodes];
labeltype labels[maxNodes];
NodeT root;
} TreeT;
Ta giả thiết rằng gốc của cây được cất giữ trong trường root và 0 để
thể hiện nút rỗng.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
52
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Cài đặt leftmost_child
Dưới đây minh họa cài đặt phép toán leftmost_child. Việc
cài đặt các phép toán còn lại được coi là bài tập.
NodeT leftmost_child (NodeT n, TreeT T)
/* trả lại con trái nhất của nút n trong cây T */
{
ListT L; /* danh sách các con của n */
L = T.header[n];
if (empty(L)) /* n là lá */
return(0);
else return(retrive ( first(L), L));
}
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
53
Dùng con trái và em kế cận phải
(The Leftmost-Child, Right-Sibling Representation)
Rõ ràng, mỗi một nút của cây chỉ có thể có:
hoặc là không có con, hoặc có đúng một nút con cực trái (con cả);
hoặc là không có em kế cận phải, hoặc có đúng một nút em kế cận phải
(right-sibling).
Vì vậy để biểu diễn cây ta có thể lưu trữ thông tin về con cực trái và em kế
cận phải của mỗi nút. Ta có thể sử dụng mô tả sau:
struct Tnode
{
char word[20]; // Dữ liệu cất giữ ở nút
struct Tnode *leftmost_child;
struct Tnode *right_sibling;
};
typedef struct Tnode treeNode;
treeNode Root;
1/28/2013
CẤU TRÚC DỮ LIỆU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
54
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Biểu diễn cây bởi con trái và em kề cận phải
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
A
A
B DC
JIH
FE
G
K
D
FE
H
G
B
I
C
KJ
55
Biểu diễn cây tổng quát bởi cây nhị phân
(con trái và con phải=em kề cận phải)
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
A
A
B
D
C
J
I
H
F
E
G
K
D
FE
H
G
B
I
C
KJ
Cây nhị phân
56
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Dùng con trái và em kế cận phải
(The Leftmost-Child, Right-Sibling Representation)
Với cách biểu diễn này, các thao tác bản dễ dàng cài đặt.
Duy chỉ thao tác parent đòi hỏi phải duyệt danh sách nên
không hiệu quả. Trong trường hợp phép toán này phải dùng
thường xuyên, người ta chấp nhận bổ sung thêm 1 trường nữa
vào bản ghi để lưu cha của nút.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
57
4.2. CÂY NHỊ PHÂN
4.2.1. Định nghĩa và tính chất
4.2.2. Biểu diễn cây nhị phân
4.2.3. Duyệt cây nhphân
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
58
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
4.2.1. Định nghĩa cây nhị phân - Binary Tree
Định nghĩa. Cây nhị phân là cây mà mỗi nút có nhiều nhất
hai con.
Vì mỗi nút chỉ có không quá hai con, nên ta sẽ gọi chúng con trái
con phải (left and right child).
Như vậy mỗi nút của cây nhị phân hoặc là
không có con, hoặc chỉ có
con trái
, hoặc chỉ có con phải, hoặc có cả con trái và con phải.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Con trái
Con phải
59
Chú ý
Vì ta phân biệt con trái và con phải, nên khái niệm cây nhị phân là không
trùng với cây có thứ tự định nghĩa ở 4.1.
Ví dụ:
Vì thế, chúng ta sẽ không so sánh cây nhị phân với cây tổng quát
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
a
a
b b
c
c
d
d
e
a
b
c d
e
e
Cây nhị phân T
1
Cây nhị phân T
2
Cây tổng quát
60
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Tính chất của cây nhị phân
Bổ đề 1.
(i) Số đỉnh lớn nhất ở trên mức i của cây nhị phân là 2
i-1
, i≥1.
(ii) Một cây nhị phân vi chiều cao k không quá 2
k
-1 nút, k ≥ 1.
(iii) Một cây nhị phân n nút có chiều cao tối thiểu log
2
(n+1).
Chứng minh:
(i) Bằng qui nạp theo i.
sở: Gốc nút duy nhất trên mức i=1. Như vậy số đỉnh lớn nhất
trên mức i=1 2
0
= 2
i-1
.
Chuyển qui nạp: Giả sử với mọi j, 1 j < i, số đỉnh lớn nhất trên mức
j 2
j-1
. Do số đỉnh trên mức i-1 2
i -2
, mặt khác theo định nghĩa mỗi
đỉnh trên y nhị phân không quá 2 con, ta suy ra số lượng nút lớn
nhất trên mức i không vượt quá 2 lần số lượng nút trên mức i-1,
nghĩa không vượt quá 2*2
i - 2
= 2
i-1
.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
61
Tính chất của cây nhị phân
(ii) Số lượng nút lớn nhất của y nhị phân chiều cao k
không vượt quá tổng số lượng nút lớn nhất trên các mức i = 1,
2, ..., k, theo bổ đề 1, số này không vượt quá
(iii) Cây nhị phân n nút chiều cao thấp nhất k khi số lượng
nút các mức i =1, 2, ..., k đều lớn nhất thể được. Từ đó
ta có:
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
1
1
2 2 1.
k
i k
i
1
2
1
2 2 1, suy ra 2 1, hay log ( 1) .
k
i k k
i
n n k n
62
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Cây nhị phân đầy đủ (full binary tree)
Định nghĩa. Cây nhị phân đầy đủ (Full Binary Trees) là cây
nhị phân thoả mãn
mỗi nút lá đều có cùng độ sâu và
các nút trong có đúng 2 con.
Bổ đề. Cây nhị phân đầy đủ với độ sâu n có 2
n
-1 nút.
Chứng minh. Suy trực tiếp từ bổ đề 1.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
63
Cây nhị phân hoàn chỉnh (Complete Binary Trees)
Định nghĩa. Cây nhị phân hoàn chỉnh (Complete Binary Trees):
Cây
nhị phân độ sâu n thoả mãn:
là cây nhị phân đầy đủ nếu không tính đến các nút ở độ sâu n, và
tất cả các nút ở độ sâu n là lệch sang trái nhất có thể được.
Bổ đề 3. Cây nhị phân hoàn chỉnh độ sâu n có số lượng nút nằm trong
khoảng từ 2
n-1
đến 2
n
- 1.
Chứng minh. Suy trực tiếp từ định nghĩa và bổ đề 1.
Ví dụ. Cây nhị phân hoàn chỉnh
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
64
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Cây nhị phân cân đối (balanced binary tree)
Định nghĩa. y nhị phân được gọi cân đối (balanced ) nếu chiều cao
của y con trái chiều cao của cây con phải chênh lêch nhau không quá
1 đơn vị.
Nhận xét:
Nếu cây nhị phân là đầy đủ thì nó là hoàn chỉnh
Nếu cây nhị phân là hoàn chỉnh thì nó là cân đối
Ví dụ:
1.1. Cây nào là đầy đủ?Cây nào là đầy đủ?
2. Cây nào là hoàn chỉnh?
3. Cây nào là cân đối?
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
65
4.2. CÂY NHỊ PHÂN
4.2.1. Định nghĩa và tính chất
4.2.2. Biểu diễn cây nhị phân
4.2.3. Duyệt cây nhphân
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
66
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
4.2.2. Biểu diễn cây nhị phân
Ta xét hai phương pháp:
Biểu diễn sử dụng mảng
Biểu diễn sử dụng con trỏ
Biểu diễn sử dụng mảng: Hoàn toàn tương tự như trong cách biểu diễn
cây tổng quát. Tuy nhiên, trong trường hợp cây nhị phân hoàn chỉnh, sử
dụng cách biểu diễn này ta thể cài đặt nhiều phép toán với cây rất
hiệu quả.
Xét cây nhị phân hoàn chỉnh T n nút, trong đó mỗi t chứa một giá
trị. Gán tên cho các nút của cây nhị phân hoàn chỉnh T từ trên xuống
dưới từ trái qua phải bằng các số 1, 2,..., n. Đặt tương ứng cây T với
mảng A trong đó phần tử thứ i của A giá trị cất giữ trong nút thứ i
của cây T, i = 1, 2, ..., n.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
67
Biểu diễn mng của cây nhị phân hoàn chỉnhBiểu diễn mng của cây nhị phân hoàn chỉnh
Complete Complete Binary TreeBinary Tree
H
D
B
K
L
JF
E
CA
1
2 3
4
5 6
7
8 9
10
Biểu diễn kế tiếp (dùng mảng)
HH DD KK BB FF JJ LL AA CC EE
0 1 8 9
10
6 74 52 3
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
68
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Cây nhị phân hoàn chỉnh Cây nhị phân hoàn chỉnh -- Complete Complete Binary TreeBinary Tree
HH DD KK BB FF JJ LL AA CC EE
0 1 8 9 106 74 52 3
Để tìmĐể tìm Sử dụngSử dụng Hạn chếHạn chế
Con trái của A[i]Con trái của A[i] A[2*i]A[2*i] 2*i <= n2*i <= n
Con phải của A[i]Con phải của A[i] A[2*i + 1]A[2*i + 1] 2*i + 1 <= n2*i + 1 <= n
Cha của A[i]Cha của A[i] A[i/2]A[i/2] i > 1i > 1
GốcGốc A[1]A[1] A khác rỗngA khác rỗng
Thử A[i] là lá?Thử A[i] là lá? TrueTrue 2*i > n2*i > n
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
69
Biểu diễn cây nhị phân dùng con trỏ
Mỗi nút của cây sẽ có con trỏ đến con trái và con trỏ đến
con phải:
struct Tnode {
DataType Item; // DataType - kiểu dữ liệu của phần tử
struct Tnode *left;
struct Tnode *right;
};
typedef struct Tnode treeNode;
key
Trỏ đến con trái
Trỏ đến con phải
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
70
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Ví dụ
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
A
A
B
D
C
J
I
H
F
E
G
K
D
FE
H
G
B
I
C
KJ
Cây nhị phân
71
Các phép toán cơ bản
struct Tnode
{ char word[20]; // Dữ liệu của nút
struct Tnode * left;
struct Tnode *right;
};
typedef struct Tnode treeNode;
treeNode* makeTreeNode(char *word);
treeNode *RandomInsert(treeNode* tree,char *word);
void freeTree(treeNode *tree);
void printPreorder(treeNode *tree);
void printPostorder(treeNode *tree);
void printInorder(treeNode *tree);
int countNodes(treeNode *tree);
int depth(treeNode *tree);
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
72
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
MakeNode
Thông số: Dữ liệu của nút cần bổ sung
Các bước:
phân bổ bộ nhớ cho nút mới
kiểm tra cấp phát bộ nhớ có thành ng?
nếu đúng, đưa item vào nút mới
đặt con trỏ trái và phải bằng NULL
trả lại: con trỏ đến (là địa chỉ của) nút mới
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
73
Cài đặt MakeNode
treeNode* makeTreeNode(char *word)
{
treeNode* newNode = NULL;
newNode = (treeNode*)malloc(sizeof(treeNode));
if (newNode == NULL){
printf("Out of memory\n");
exit(1);
}
else {
newNode->left = NULL;
newNode->right= NULL;
strcpy(newNode->word,word);
}
return newNode;
}
1/28/2013
CẤU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
74
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Cài đặt hàm tính số nút và độ sâu của cây
int countNodes(treeNode *tree) {
/* the function counts the number of nodes of a tree*/
if( tree == NULL ) return 0;
else {
int ld = countNodes(tree->left);
int rd = countNodes(tree->right);
return 1+ld+rd;
}
}
int depth(treeNode *tree) {
/* the function computes the depth of a tree */
if( tree == NULL ) return 0;
int ld = depth(tree->left);
int rd = depth(tree->right);
/* if (ld > rd) return 1+ld; else return 1+rd; */
return 1 + (ld > rd ? ld : rd);
}
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
75
Loại bỏ cây
void freeTree(treeNode *tree)
{
if( tree == NULL ) return;
freeTree(tree->left);
freeTree(tree->right);
free(tree);
return;
}
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
76
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Duyệt cây nhị phân
Duyệt cây nhị phân là cách duyệt hệ thống các nút của cây.
Tương tự cây tổng quát, ta xét ba thứ tự duyệt cây nhị phân:
Thứ tự trước (Preorder)
NLR
Thăm nút (Visit a node),
Thăm cây con trái theo thứ tự trước (Visit left subtree),
Thăm cây con phải theo thứ tự trước (Visit right subtree)
Thứ tự giữa (Inorder)
LNR
Thăm cây con trái theo thứ tự giữa (Visit left subtree),
Thăm nút (Visit a node),
Thăm cây con phải theo thứ tự giữa (Visit right subtree)
Thứ tự sau (Postorder)
LRN
Thăm cây con trái theo thứ tự sau (Visit left subtree),
Thăm cây con phải theo thứ tự sau (Visit right subtree)
Thăm nút (Visit a node),
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
77
Duyệt theo thứ tự trước - NLR
Preorder Traversal
Thăm nút (Visit the node).
Duyệt cây con trái (Traverse the left subtree).
Duyệt cây con phải (Traverse the right subtree).
void printPreorder(treeNode *tree)
{
if( tree != NULL )
{
printf("%s\n", tree->word);
printPreorder(tree->left);
printPreorder(tree->right);
}
}
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
78
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Preorder TraversalPreorder Traversal
2
4
7
5
8
103
6
91
11
2, 4, 7, 1, 9, 3, 6, 5, 10, 8, 11
2
4
7
1 9
3
6
5
10
8
11
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
79
Duyệt theo thứ tự giữa - LNR
Inorder Traversal
Duyệt cây con trái (Traverse the left subtree).
Thăm nút (Visit the node).
Duyệt cây con phải (Traverse the right subtree).
void printInorder(treeNode *tree)
{
if( tree != NULL )
{
printInorder(tree->left);
printf("%s\n", tree->word);
printInorder(tree->right);
}
}
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
80
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Inorder TraversalInorder Traversal
2
4
7
5
8
103
6
91
11
1, 7, 9, 4, 6, 3, 2, 10, 5, 11, 8
2
4
7
1 9
3
6
5
10
8
11
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
81
Thứ tự giữa thu được bằng phép chiếu
Inorder By Projection
a
b c
d
e
f
g
h i
j
g d h b e i a f j c
1/28/2013
CẤU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
82
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Duyệt theo thứ tự sau - LRN
Postorder Traversal
Duyệt cây con trái (Traverse the left subtree).
Duyệt cây con phải (Traverse the right subtree).
Thăm nút (Visit the node).
void printPostorder(treeNode *tree)
{
if( tree != NULL )
{
printPostorder(tree->left);
printPostorder(tree->right);
printf("%s\n", tree->word);
}
}
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
83
Postorder TraversalPostorder Traversal
2
4
7
5
8
103
6
91
11
1, 9, 7, 6, 3, 4, 10, 11, 8, 5, 2
2
4
7
1 9
3
6
5
10
8
11
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
84
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Ví dụ: Duyệt cây nhị phân
Chú ý: Ta có thể xây dựng được cây nhị phân mà thứ tự trước
thứ tự giữa hoặc thứ tự sau và thứ tự giữa là như nhau; nhưng không
thể có cây nhị phân mà thứ tự trước và thứ tự sau là như nhau.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
85
Chương trình minh hoạ
/* The program for testing binary tree traversal */
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include <process.h>
struct Tnode {
char word[20];
struct Tnode * left;
struct Tnode *right;
};
typedef struct Tnode treeNode;
treeNode* makeTreeNode(char *word);
treeNode *RandomInsert(treeNode* tree,char *word);
void freeTree(treeNode *tree);
void printPreorder(treeNode *tree);
void printPostorder(treeNode *tree);
void printInorder(treeNode *tree);
int countNodes(treeNode *tree);
int depth(treeNode *tree);
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
86
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Chương trình minh hoạ
int main() {
treeNode *randomTree=NULL;
char word[20] = "a";
while( strcmp(word,"~")!=0)
{ printf("\nEnter item (~ to finish): ");
scanf("%s", word);
if (strcmp(word,"~")==0) printf("Cham dut nhap thong tin nut... \n");
else randomTree=RandomInsert(randomTree,word);
}
printf("The tree in preorder:\n"); printPreorder(randomTree);
printf("The tree in postorder:\n"); printPostorder(randomTree);
printf("The tree in inorder:\n"); printInorder(randomTree);
printf("The number of nodes is: %d\n",countNodes(randomTree));
printf("The depth of the tree is: %d\n", depth(randomTree));
freeTree(randomTree);
getch(); return 0;
}
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
87
Gắn ngẫu nhiên nút mới vào cây
treeNode *RandomInsert(treeNode *tree,char *word){
treeNode *newNode, *p;
newNode = makeTreeNode(word);
if ( tree == NULL ) return newNode;
if ( rand()%2 ==0 ){
p=tree;
while (p->left !=NULL) p=p->left;
p->left=newNode;
printf("Node %s is left child of %s \n",word,(*p).word); }
else {
p=tree;
while (p->right !=NULL) p=p->right;
p->right=newNode;
printf("Node %s is right child of %s \n",word,(*p).word);
}
return tree;
}
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
88
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Chương trình minh hoạ
/***********************************************
The program for testing binary tree traversal
************************************************/
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#include <process.h>
struct Tnode
{
char word[20];
struct Tnode * left;
struct Tnode *right;
};
typedef struct Tnode treeNode;
treeNode* makeTreeNode(char *word);
treeNode *RandomInsert(treeNode* tree,char *word);
void freeTree(treeNode *tree);
void printPreorder(treeNode *tree);
void printPostorder(treeNode *tree);
void printInorder(treeNode *tree);
int countNodes(treeNode *tree);
int depth(treeNode *tree);
int main()
{
treeNode *randomTree=NULL;
char word[20] = "a";
while( strcmp(word,"~")!=0)
{ printf("\nEnter item (~ to finish): ");
scanf("%s", word);
if ( strcmp(word,"~")==0 )
printf("Cham dut nhap thong tin nut... \n");
else randomTree=RandomInsert(randomTree,word);
}
printf("The tree in preorder:\n");
printPreorder(randomTree);
printf("***************************************************\n");
printf("The tree in postorder:\n");
printPostorder(randomTree);
printf("***************************************************\n");
printf("The tree in inorder:\n");
printInorder(randomTree);
printf("***************************************************\n");
printf("The number of nodes is: %d\n",countNodes(randomTree));
printf("The depth of the tree is: %d\n", depth(randomTree));
freeTree(randomTree);
getch();
return 0;
}
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
89
4.3. Các ví dụ ứng dụng
4.3.1. Cây biểu thức
4.3.2. Cây mã Huffman
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
90
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
4.3.1. Cây biểu thức
An application of binary trees:An application of binary trees:
Binary Expression Trees
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
91
Khái niệm
Cây biểu thức là cây nhị phân trong đó:
1. Mỗi
nút lá chứa một toán hạng
2. Mỗi
nút trong chứa mt phép toán hai ngôi
3. Các cây con trái phải của nút phép toán biểu diễn
các
biểu thức con (subexpressions) cần được thực
hiện
trước khi thực hiện phép toán gốc của các cây
con.
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
92
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Ví dụ: Cây nhị phân 4 mức
‘*’
‘-’
‘8’
‘5’
‘/’
‘+’
‘4’
‘3’
‘2’
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
93
Các mức thể hiện mức độ ưu tiên
Mức (độ sâu) của các nút trên cây cho biết trình tự
thực hiện chúng (ta không cần sử dụng ngoặc để ch
ra trình tự).
Phép toán ti mc cao hơn của cây đưc thc hiện
muộn hơn
so với các mức dưới chúng.
Phép toán gốc luôn được thực hiện sau cùng.
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
94
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Ví dụ:
Xét Cây biểu thức
Cây này có giá trị nào?
( 4 + 2 ) * 3 = 18
‘*’
‘+’
‘4’
‘3’
‘2’
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
95
Infix: ( ( 8 - 5 ) * ( ( 4 + 2 ) / 3 ) )
Prefix: * - 8 5 / + 4 2 3
Postfix: 8 5 - 4 2 + 3 / *
‘*’
‘-’
‘8’
‘5’
‘/’
‘+’
‘4’
‘3’
‘2’
Sử dụng cây biểu thức ta có thể đưa ra biểu thức trong ký pháp
trung tố, tiền tố và hậu tố (infix, prefix, postfix)
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
96
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Thứ tự giữa của cây biểu thức
Inorder Of Expression Tree
+
a
b
-
c
d
+
e
f
*
/
Cho ta biểu thức trung tố (thiếu dấu ngoặc)!
ea + b * c d / + f-
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
97
Các ký pháp
Duyệt cây biểu thức theo thtự trước (Preorder)
Cho ta ký pháp tiền t(Prefix Notation)
Duyệt cây biểu thức theo thtự giữa (Inorder)
Cho ta ký pháp trung t (Infix Notation)
Duyệt cây biểu thức theo thtự sau (Postorder)
Cho ta ký pháp hậu tố (Postfix Notation)
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
98
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Ví dụ: Infix Notation
/
+
/
1
3 *
6 7
4
1 / 3 + *6 7 / 4
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
99
7
//
/
1
+
/
3 *
6
4
Ví dụ: Postfix Notation
Còn gọi là: Reverse Polish Notation
1
1
3
3
6
6
7
7
*
*
4
4
/
/
+
+
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
100
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
/
+
/
1
3 *
6 7
4
Ví dụ: Prefix
+ / 1 3 / * 6 7 4
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
101
4.3. Các ví dụ ứng dụng
4.3.1. Cây biểu thức
4.3.2. Cây mã Huffman
1/28/2013
CU TRÚC D LIU VÀ THUT TOÁN
NGUYN ĐƯC NGHĨA - B môn KHMT
102
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
4.3.3. Mã Huffman
An application of binary trees:An application of binary trees:
Huffman Code
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013 103
Mã Huffman
Giả s một văn bản trên bảng chữ cái C. Với mỗi
chữ cái c C ta biết tần suất xuất hiện của trong
văn bản f(c). Cần tìm ch hoá văn bản s dụng
ít bộ nhớ nhất.
ho¸ ví i ®é dµi cè ®Þnh (fixed length code). m·
ho¸ còng nh gi¶i , nhng i
®ßi hái nhí n
phi tiÒn (prefix free code) ch ho¸ i
c bëi mét u nhÞph©n code(c) sao cho cña
mét t kh«ng ® n ®Çu cña t cø
cña nµo trong c n i. Tuy ®ßi hái
viÖc ho¸ gi¶i phøc p h¬n nhng th«ng
thêng ra
®ßi hái Ýt nhí n.
David A. Huffman
1925-1999
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013 104
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
h độ dài cố định
Để mã hoá 26 chữ cái tiếng Anh bởi mã nhị phân độ dài cố
định, độ dài của xâu tối thiểu là [log 26] =5 bit.
Các xâu từ 11011 đến 11111 không sử dụng
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013 105
y mã hoá độ dài cố định
Mã hoá độ dài cố định là mã phi tiền tố
Gii mã 0011101000 HI
Các nút * không s dụng
CẤU TRÚC DỮ LIU VÀ THUT TOÁN
NGUYỄN ĐƯC NGHĨA - B môn KHMT
1/28/2013 106
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Morse Code
Căn cứ vào thống kê tần suất của các chữ cái trong tiếng Anh
Morse đề xuất cách mã hoá:
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013 107
Cây hoá Morse
Mã hoá Morse không là phi tiền tố
Giải mã “....-” ??? Chịu chết?
Phải có dấu phân biệt các chữ cái: “..#..-” IU
Cây không đầy đủ
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013 108
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Mã Huffman
Mỗi mã phi tiền tố thể biểu diễn bởi một cây nhị
phân T mi lá cuả tương ứng với một chữ i
cạnh của được gán cho một trong hai số 0 hoặc
1.
của mt chữ cái c 1 dãy nhị phân gồm các số
gán cho các cạnh trên đường đi từ gốc đến tương
ứng với c.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013 109
Mã Huffman
Bài toán: Tìm cách mã hoá tối ưu, tức là tìm cây nhị phân T
làm tối thiểu hoá tổng độ dài có trọng số
trong đó depth(c) là độ dài đường đi từ gốc đến lá tương ứng
với ký tự c.
Cc
cdepthcfTB )()()(
CẤU TRÚC DỮ LIỆU VÀ THUT TOÁN
NGUYỄN ĐƯC NGHĨA - B môn KHMT
1/28/2013 110
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
Mã Huffman
Ý tưởng thuật toán:
Chữ cái có tần suất nhỏ hơn cần được gán cho lá có khoảng
cách đến gốc là lớn hơn; chữ cái có tần suất xuất hiện lớn hơn
cần được gán cho nút gần gốc hơn
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013 111
Mã Huffman: Thuật toán
procedure Huffman(C, f);
begin
n |C|;
Q C;
for i:=1 to n-1 do
begin
x, y 2 chữ cái có tần suất nhỏ nhất trong Q; (* Thao tác 1 *)
Tạo nút p vi hai con x, y;
f(p) := f(x) + f(y);
Q Q \ {x, y} {p} (* Thao tác 2 *)
end;
end;
M· x©y dùng theo thuËt to¸n Huffman thêng ®îc gäi lµ m· Huffman
(Huffman Code).
thcài đặt với thi gian O(n log n) sử dụng priority queue
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013 112
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
y dùng m· Huffman
Tần suất của các ký tự trong văn bản.
125
Freq
93
80
76
72
71
61
55
41
40
E
Char
T
A
O
I
N
R
H
L
D
31
27
C
U
65S
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013 113
y dùng m· Huffman
R S N I
E
H
C U
31 27
55
71 7361 65
125
40
T
D L
41
93
A O
80 76
CU TRÚC D LIU VÀ THUT TOÁN
NGUYỄN ĐƯC NGHĨA - B môn KHMT
1/28/2013
114
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
y dùng m· Huffman
R S N I
E
H
C U
58
D L
A O T
31 27
55
71 7361 65
125
40 41
93
80 76
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013
115
y dùng m· Huffman
R S N I
E
H
C U
58
D L
81
A O T
31 27
55
71 7361 65
125
40 41
93
80 76
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013
116
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
y dùng m· Huffman
R S N I
E
H
C U
58
113
D L
81
A O T
31 27
55
71 7361 65
125
40 41
93
80 76
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013
117
y dùng m· Huffman
R S N I
E
H
C U
58
113126
D L
81
A O T
31 27
55
71 7361 65
125
40 41
93
80 76
CẤU TRÚC D LIU VÀ THUT TOÁN
NGUYỄN ĐƯC NGHĨA - B môn KHMT
1/28/2013
118
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
y dùng m· Huffman
R S N I
E
H
C U
58
113144126
D L
81
A O T
31 27
55
71 7361 65
125
40 41
93
80 76
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013
119
y dùng m· Huffman
R S N I
E
H
C U
58
113144126
D L
81
156
A O T
31 27
55
71 7361 65
125
40 41
93
80 76
CU TRÚC D LIU VÀ THUT TOÁN
NGUYỄN ĐƯC NGHĨA - B môn KHMT
1/28/2013
120
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
y dùng m· Huffman
R S N I
E
H
C U
58
113144126
D L
81
156 174
A O T
31 27
55
71 7361 65
125
40 41
93
80 76
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013
121
y dùng m· Huffman
R S N I
E
H
C U
58
113144126
238
T
D L
81
156 174
A O
CU TRÚC D LIU VÀ THUT TOÁN
NGUYỄN ĐƯC NGHĨA - B môn KHMT
1/28/2013
122
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
y dùng m· Huffman
R S N I
E
H
C U
58
113144126
238
270
T
D L
81
156 174
A O
31 27
55
71 7361 65
125
40 41
93
80 76
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013
123
y dùng m· Huffman
R S N I
E
H
C U
58
113144126
238
270
330
T
D L
81
156 174
A O
31 27
55
71 7361 65
125
40 41
93
80 76
CU TRÚC D LIU VÀ THUT TOÁN
NGUYỄN ĐƯC NGHĨA - B môn KHMT
1/28/2013
124
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
y dùng m· Huffman
R S N I
E
H
C U
58
113144126
238
270
330 508
T
D L
81
156 174
A O
31 27
55
71 7361 65
125
40 41
93
80 76
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
1/28/2013
125
y dùng m· Huffman
R S N I
E
H
C U
58
113144126
238
270
330 508
838
T
D L
81
156 174
A O
31 27
55
71 7361 65
125
40 41
93
80 76
0
0
0
0
0
0
0
0 0
0
0
0
1
1
1 1
1
1
1
1
1
1
1
1
CU TRÚC D LIU VÀ THUT TOÁN
NGUYỄN ĐƯC NGHĨA - B môn KHMT
1/28/2013
126
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
y dùng m· Huffman
125
Freq
93
80
76
73
71
61
55
41
40
E
Char
T
A
O
I
N
R
H
L
D
31
27
C
U
65S
0000
Fixed
0001
0010
0011
0100
0101
0111
1000
1001
1010
1011
1100
0110
110
Huff
011
000
001
1011
1010
1000
1111
0101
0100
11100
11101
1001
838
Tæng
30363352
1/28/2013 127
Mã Huffman: Giải
procedure Huffman_Decode(B);
(* B lµ x©u m· hãa văn b¶n theo m· ho¸ Huffman. *)
begin
<Khëi ®éng P lµ gèc cña c©y Huffman>
While <cha ®¹t ®Õn kÕt thóc cña B> do
begin
x bit tiÕp theo trong x©u B;
If x = 0 then P Con tr¸ i cña P
Else P Con ph¶i cña P
If (P lµ nót l¸ ) then
begin
<HiÓn thÞ kÝ hiÖu t¬ng øng víi nót l¸>
<ĐÆt l¹ i P lµ gèc cña c©y Huffman>
end;
end
end;
CU TRÚC D LIU VÀ THUT TOÁN
NGUYỄN ĐƯC NGHĨA - B môn KHMT
1/28/2013 128
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
QUESTIONS?
1/28/2013
CẤU TRÚC DỮ LIỆU THUẬT TN
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
129
CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)
lOMoARcPSD|36442750
| 1/65

Preview text:

lOMoARcPSD|36442750 Chương 4 CÂY Nội dung
4.1. Định nghĩa và các khái niệm 4.2. Cây nhị phân 4.3. Các ứng dụng
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 2
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
4.1. Định nghĩa và khái niệm 4.1.1. Định nghĩa 4.1.2. Các thuật ngữ 4.1.3. Cây có thứ tự 4.1.4. Cây có nhãn 4.1.5. ADT cây
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 3
4.1.1. Định nghĩa cây
Cây bao gồm các nút, có một nút đặc biệt được gọi là gốc (root) và
các cạnh nối các nút. Cây được định nghĩa đệ qui như sau: Định nghĩa cây:
Basic Step: Một nút r là cây và r được gọi là gốc của cây này.
Recursive Step: Giả sử T ,T ,...,T là các cây với gốc là r ,r ,...,r .
1 2 k 1 2 k
Ta có thể xây dựng cây mới bằng cách đặt r làm cha (parent) của
các nút r ,r ,..., r . Trong cây này r là gốc và T
, T , . . . , T là các 1 2 k 1 2 k
cây con của gốc r. Các nút r , r , . . . , r được gọi là con (children) 1 2 k của nút r.
Chú ý: Nhiều khi để phù hợp ta cần định nghĩa cây rỗng (null
tree
) là cây không có nút nào cả.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013 4
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Cấu trúc đệ qui của cây r r r2 r 1 k T T T 1 2 k
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 5
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Cây trong thực tế ứng dụng
• Biểu đồ lịch thi đấu • Cây gia phả
• Biểu đồ phân cấp quản lý hành chính. • Cây thư mục
• Cấu trúc của một quyển sách • Cây biểu thức
• Cây phân hoạch tập hợp • ...
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 6
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Cây lịch thi đấu
Trong đời thường cây rất hay được sử dụng để diễn tả
lịch thi đấu của các giải thể thao theo thể thức đấu loại
trực tiếp, chẳng hạn vòng 2 của World Cub Pháp Pháp Tây ban nha Pháp Brazin Brazin Anh Italia Đức Đức Ucrain Italia Italia Italia Ahentina
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 7
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT Cây gia phả
Cây gia phả của các nhà toán dòng họ Bernoulli Nikolaus 1623-1708 Johan I Nikolaus Jacob I 1667-1748 1662-1716 1654-1705 Nikolaus II Daniel Johan II Nikolaus I 1695-1726 1700-1782 1710-1790 1687-1759 Johan III Jacob II 1746-1807 1759-1789
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013 8
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Cây phân cấp quản lý hành chính Ban Giám đốc Phòng Phòng Phòng Phòng Phòng Hành chính Tổ chức Tài vụ Kinh doanh Kế hoạch TP Văn thư
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 9 Cây thư mục
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 10
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Cây mục lục sách
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 11
Cây gia phả ngược (Ancestor Tree)
Cây phả hệ ngược: mỗi người đều có bố mẹ. Cây
này là cây nhị phân (binary tree). Thùy Hương Thúy Cải Quang Dũng Bích Liên Trung Kiên Hoàng Cúc Quang Thái
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 12
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Cây biểu thức (Expression Tree) + / / 1 3 * 4 6 7 1/3 + 6*7 / 4
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 13 - Bộ môn KHMT
Cây phân hoạch tập hợp
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Tập con các số lẻ:
Tập con các số chẵn: {1, 3, 5, 7, 9} { 2, 4, 6, 8, 10} {1, 9}
Tập con các số nguyên tố: { 2, 4, 8, 10}
Tập con số hoàn hảo: { 3, 5, 7 } { 6 }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013 NGUYỄN ĐƯC NGHĨA 14 - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
4.1. Định nghĩa và khái niệm 4.1.1. Định nghĩa 4.1.2. Các thuật ngữ 4.1.3. Cây có thứ tự 4.1.4. Cây có nhãn 4.1.5. ADT cây
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 15
4.1.2. Các thuật ngữ chính • Nút - node • Gốc - root • Lá - leaf • Con - child • Cha - parent • Tổ tiên - ancestors • Hậu duệ - descendants • Anh em - sibling • Nút trong - internal node • Chiều cao - hight • Chiều sâu - depth
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 16
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Các thuật ngữ chính
Nếu n , n , . . . , n là dãy nút trên cây sao cho n là cha của n với 1  i < k, thì dãy 1 2 k i i+1
này được gọi là đường đi (path) từ nút n tới nút n . Độ dài (length) của đường đi là 1 k
bằng số lượng nút trên đường đi trừ bớt 1. Như vậy đường đi độ dài 0 là đường đi từ một nút đến chính nó. •
Nếu có đường đi từ nút a tới nút b, thì a được gọi là tổ tiên (ancestor) của b, còn b
được gọi là hậu duệ (descendant) của a. •
Tổ tiên (hậu duệ) của một nút khác với chính nó được gọi là tổ tiên (hậu duệ) chính
thường (proper). Trong cây, gốc là nút không có tổ tiên chính thường và mọi nút khác
trên cây đều là hậu duệ chính thường của nó. •
Một nút không có hậu duệ chính thường được gọi lá (leaf). •
Các nút có cùng cha được gọi là anh em (sibling). •
Cây con (subtree) của một cây là một nút cùng với tất cả các hậu duệ của nó. •
Chiều cao (height) của nút trên cây là bằng độ dài của đường đi dài nhất từ nút đó
đến lá cộng 1. Chiều cao của cây (height of a tree) là chiều cao của gốc. Độ sâu/mức
(depth/level) của nút là bằng 1 cộng với độ dài của đường đi duy nhất từ gốc đến nó.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 17 Thuật n t gữ nút nodes
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com NGUYỄN ĐƯC NGHĨA 18 - Bộ môn KHMT 1/28/2013
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Thuật n t gữ Nút cha parent node
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA 19 - Bộ môn KHMT 1/28/2013 Thuật n t gữ cha con parent child
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com NGUYỄN ĐƯC NGHĨA 20 - Bộ môn KHMT 1/28/2013
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Thuật n t gữ con cha
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA 21 - Bộ môn KHMT 1/28/2013 Thuật n t gữ gốc lá - leaf - root
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com NGUYỄN ĐƯC NGHĨA 22 - Bộ môn KHMT 1/28/2013
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Thuật n t gữ
cây con - subtree
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA 23 - Bộ môn KHMT 1/28/2013 Thuật n t gữ cây con
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com NGUYỄN ĐƯC NGHĨA 24 - Bộ môn KHMT 1/28/2013
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Thuật n t gữ cây con
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA 25 - Bộ môn KHMT 1/28/2013
Các thuật ngữ với cây có gốc root, ancestor a internal node parent (không là lá) b d nút c sibling e f leaf (không có con) g h child child i j descendent e, i, k, g, h là lá (leaves) k
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013 26
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Đường đi trên cây
Có duy nhất 1 đường đi từ
Từ cha đến con và đến
một nút đến một nút là các nút hậu duệ. a hậu duệ của nó. b d c Path 1 Path 2 f e h g i j Path 1: { a, b, f, j } Path 2: { d, i }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 27
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Độ cao (height) và độ sâu/mức (depth/level) độ cao h = 5 7 độ sâu 1 độ cao = 4 3 10 4 độ sâu 2 độ cao = 3 8 12 11 2 độ sâu 3 h = 2 1 6 5 độ sâu 4 Độ cao của cây là 5 độ cao h=1 9 độ sâu 5
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013 28
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Ho H w We e View Vie a T re r e e Nature Lovers View
Computer Scientists View
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA 29 - Bộ môn KHMT 1/28/2013 Bậc (Degree) Số lượng con của nút x được gọi là degree = 3 7
bậc (degree) của x. 3 10 4 8 12 degree = 1 11 2 degree = 0 1 6 5 9
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013 30
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
4.1. Định nghĩa và khái niệm 4.1.1. Định nghĩa 4.1.2. Các thuật ngữ 4.1.3. Cây có thứ tự 4.1.4. Cây có nhãn 4.1.5. ADT cây
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 31
4.1.3. Cây có thứ tự - Ordered Tree
Thứ tự của các nút
• Các con của một nút thường được xếp thứ tự từ trái sang phải. Như
vậy hai cây trong hình sau đây là khác nhau, bởi vì hai con của nút
a xuất hiện trong hai cây theo thứ tự khác nhau: a a b c c b
• Cây với các nút được xếp thứ tự được gọi là cây có thứ tự. Ta sẽ xét
chủ yếu là cây có thứ tự. Vì vậy, tiếp theo thuật ngữ cây là để chỉ
cây có thứ tự. Khi muốn khẳng định là không quan tâm đến thứ tự,
ta sẽ phải nói rõ là cây không có thứ tự.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 32
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Xếp thứ tự các nút
• Ta có thể xếp thứ tự các nút của cây theo nhiều cách. Có ba
thứ tự quan trọng nhất, đó là Thứ tự trước, Thứ tự sau và
Thứ tự giữa (Preorder, Postorder, và Inorder)

• Các thứ tự này được định nghĩa một cách đệ qui như sau
– Nếu cây T là rỗng, thì danh sách rỗng là danh sách theo thứ
tự trước, thứ tự sau và thứ tự giữa của cây T.
– Nếu cây T có một nút, thì nút đó chính là danh sách theo
thứ tự trước, thứ tự sau và thứ tự giữa của cây T.
– Trái lại, giả sử T là cây có gốc r với các cây con là T , T ,..., 1 2 Tk.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 33
Duyệt theo thứ tự trước - Preorder Traversal r r r2 r 1 k T T T 1 2 k
Thứ tự trước (hay duyệt theo thứ tự trước - preorder
traversal) của các nút của T là:
– Gốc r của T,
– tiếp đến là các nút của T theo thứ tự trước, 1
– tiếp đến là các nút của T theo thứ tự trước, 2 – ...
– và cuối cùng là các nút của T theo thứ tự trước. k
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 34
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Duyệt theo thứ tự sau - Postorder Traversal r r r2 r 1 k T T T 1 2 k
• Thứ tự sau của các nút của cây T là:
– Các nút của T theo thứ tự sau, 1
– tiếp đến là các nút của T theo thứ tự sau, 2 – ...
– các nút của T theo thứ tự sau, k
– sau cùng là nút gốc r.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 35
Duyệt theo thứ tự giữa - Inorder Traversal r r r2 r 1 k T T T 1 2 k
Thứ tự giữa của các nút của cây T là:
– Các nút của T theo thứ tự giữa, 1
– tiếp đến là nút gốc r,
– tiếp theo là các nút của T , . . . , T , mỗi nhóm nút được xếp theo thứ tự 2 k giữa.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 36
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Thuật toán duyệt theo thứ tự trước - Preorder Traversal
void PREORDER ( nodeT r ) { (1) Đưa ra r;
(2) for (mỗi con c của r, nếu có, theo thứ tự từ trái sang) do PREORDER(c); } a b c d e f g h i j
Ví dụ: Thứ tự trước của các đỉnh của cây trên hình vẽ là
a, b, c, e, h, i, f, j, d, g
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 37
Thuật toán duyệt theo thứ tự sau - Postorder Traversal
Thuật toán duyệt theo thứ tự sau thu được bằng cách đảo ngược hai thao
tác (1) và (2) trong PREORDER:
void POSTORDER ( nodeT r ) {
for (mỗi con c của r, nếu có, theo thứ tự từ trái sang) do POSTORDER(c) Đưa ra a r; } b c d e f g h i j
Ví dụ: Dãy các đỉnh được liệt kê theo thứ tự sau của cây trong hình vẽ là:
b, h, i, e, j, f, c, g, d, a
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 38
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Thuật toán duyệt theo thứ tự giữa - Inorder Traversal
void INORDER (nodeT r ) a {
if ( r ) Đưa ra r; b c d else e f g {
INORDER(con trái nhất của r); h i j Đưa ra r;
for (mỗi con c của r, ngoại trừ con trái nhất, theo thứ tự từ trái sang) do INORDER(c); } }
Ví dụ: Dãy các đỉnh của cây trong hình vẽ được liệt kê theo thứ tự giữa:
b, a, h, e, i, c, j, f, g, d
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 39
Xếp thứ tự các nút
Để nhớ cách đưa ra các nút theo ba thứ tự a
vừa trình bày hãy hình dung là ta đi vòng
quanh bên ngoài cây bắt đầu từ gốc, ngược b c d
chiều kim đồng hồ và sát theo cây nhất. e f g
Chẳng hạn, đường đi đó đối với cây trong
các ví dụ đã xét trên là như sau: h i j
• Đối với thứ tự trước, ta đưa ra nút mỗi khi đi qua nó.
• Đối với thứ tự sau, ta đưa ra nút khi qua nó ở lần cuối trước khi
quay về cha của nó.
• Đối với thứ tự giữa, ta đưa ra lá ngay khi đi qua nó, còn những nút
trong được đưa ra khi lần thứ hai được đi qua.
• Chú ý rằng các lá được xếp thứ tự từ trái sang phải như nhau trong cả ba cách sắp xếp.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 40
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
4.1.4. Cây có nhãn (Labeled Tree)
• Thông thường người ta gán cho mỗi nút của cây một nhãn (label)
hoặc một giá trị, cũng tương tự như chúng ta đã gán mỗi nút của
danh sách với một phần tử. Nghĩa là, nhãn của nút không phải là tên
gọi của nút mà là giá trị được cất giữ trong nó. Trong một số ứng
dụng ta có thể thay đổi nhãn của nút mà tên của nó vẫn được giữ nguyên.
Ví dụ: Xét cây có 7 nút n , ..., n . Ta gán nhãn cho các nút như sau: 1 7 – Nút n có nhãn *; 1 n1* Nút n có nhãn +; 2 – Nút n có nhãn -; 3 n n3
– Nút n có nhãn a; 2 + - 4
– Nút n có nhãn b; 5 – Nút n có nhãn a; 6
n4 a n n n 5 b a 6 7 c
– Nút n có nhãn c. 7
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 41 - Bộ môn KHMT
Cây biểu thức (Expression Tree)
• Cây trong ví dụ vừa nêu có tên gọi là cây biểu thức (a+b)*(a-c)
• Qui tắc để cây có nhãn biểu diễn một biểu thức là:
– Mỗi nút lá có nhãn là toán hạng và chỉ gồm một toán hạng đó. Ví dụ nút n biểu 4 diễn biểu thức a.
– Mỗi nút trong n được gán nhãn là phép toán. Giả sử n có nhãn là phép toán hai
ngôi q, như + hoặc *, và con trái biểu diễn biểu thức E và con phải biểu diễn 1
biểu thức E . Khi đó n biểu diễn biểu thức (E ) q (E ). Ta có thể bỏ dấu ngoặc 2 1 2
nếu như điều đó là không cần thiết. n1 *Ví dụ:
– Nút n chứa toán hạng + và con trái 2 n n và con phải của nó là 2 + 3 -
a b. Vì thế
n biểu diễn (a) + (b), hay a+b. 2
n4 a n n n 5 b a 6 7 c
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013 NGUYỄN ĐƯC NGHĨA 42 - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
4.1. Định nghĩa và khái niệm 4.1.1. Định nghĩa 4.1.2. Các thuật ngữ 4.1.3. Cây có thứ tự 4.1.4. Cây có nhãn 4.1.5. ADT cây
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 43 4.1.5. ADT Cây
• Trong chương này chúng ta tìm hiểu cây vừa như là kiểu dữ
liệu trừu tượng vừa như là kiểu dữ liệu. Một trong những ứng
dụng quan trọng của cây là nó được dùng để thiết kế và cài đặt
nhiều kiểu dữ liệu trừu tượng quan trọng khác như "Cây tìm
kiếm nhị phân", "Tập hợp",....
• Cũng như danh sách, đối với cây cũng có thể xét rất nhiều
phép toán làm việc với nó. Dưới đây ta chỉ kể ra một số phép toán cơ bản.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 44
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 4.1.5. ADT Cây
parent(n, T). Hàm này trả lại cha của nút n trong cây T. Nếu
n là gốc (nó không có cha), trả lại . Theo nghĩa này,  là nút
rỗng ("null node") dùng để báo hiệu rằng chúng ta sẽ dời khỏi cây.
leftmost_child(n, T) trả lại con trái nhất của nút n trong cây T,
và trả lại  nếu n là lá (không có con).
right_sibling(n, T) trả lại em bên phải của nút n trong cây T
(được định nghĩa như là nút m có cùng cha là p giống như n
sao cho m nằm sát bên phải của n trong danh sách sắp thứ tự các con của p.
– Ví dụ, với cây trong slide gần nhất:
• leftmost_child(n ) = n ; 2 4
• right_sibling(n ) = n , và RIGHT_SIBLING (n ) = L. 4 5 5
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 45 4.1.5. ADT Cây
label(n, T) trả lại nhãn của nút n trong cây T. Tuy nhiên, ta
không đòi hỏi cây nào cũng có nhãn.
createi(v, T , T , . . . , T ) là họ các hàm, mỗi hàm cho một giá 1 2 i
trị của i = 0, 1, 2, ... createi tạo một nút mới r với nhãn v
gắn cho nó i con, với các con là các gốc của cây T , T , ..., T , 1 2 i
theo thứ tự từ trái sang. Trả lại cây với gốc r. Chú ý, nếu i = 0,
thì r vừa là lá vừa là gốc.
root(T) trả lại nút là gốc của cây T, hoặc  nếu T là cây rỗng.
makenull(T) biến T thành cây rỗng.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 46
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Biểu diễn cây
• Có nhiều cách biểu diễn cây. Ta giới thiệu qua về ba cách biểu diễn cơ bản:
– dùng mảng (Array Representation)
– danh sách các con (Lists of Children)
– dùng con trái và em phải (The Leftmost-Child, Right- Sibling Representation)
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 47
Biểu diễn cây dùng mảng
• Giả sử T là cây với các nút đặt tên là 1, 2, . . . , n. Cách đơn giản để
biểu diễn T là hỗ trợ thao tác parent bởi danh sách tuyến tính A
trong đó mỗi phần tử A[i] chứa con trỏ đến cha của nút i. Riêng gốc
của T có thể phân biệt bởi con trỏ rỗng.
• Khi dùng mảng, ta đặt A[i] = j nếu nút j là cha của nút i, và A[i] = 0 nếu nút i là gốc.
• Cách biểu diễn này dựa trên cơ sở là mỗi nút của cây (ngoại trừ gốc)
đều có duy nhất một cha. Với cách biểu diễn này cha của một nút có
thể xác định trong thời gian hằng số. Đường đi từ một nút đến tổ
tiên của chúng (kể cả đến gốc) có thể xác định dễ dàng:
n <- parent(n) <- parent(parent(n)) <- ...
• Ta cũng có thể đưa thêm vào mảng L[i] để hỗ trợ việc ghi nhận nhãn
cho các nút, hoặc biến mỗi phần tử A[i] thành bản ghi gồm hai
trường: biến nguyên ghi nhận cha và nhãn.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 48
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Biểu diễn cây dùng mảngVí dụ 1 2 3 4 5 6 10 7 8 9 A 0 1 1 2 2 3 6 6 6 3
Hạn chế: Cách dùng con trỏ cha không thích hợp cho các thao tác với con. Cho nút
n, ta sẽ mất nhiều thời gian để xác định các con của n, hoặc chiều cao của n. Hơn
nữa biểu diễn bởi con trỏ cha không cho ta thứ tự của các nút con. Vì thế các phép
toán như leftmost_child right_sibling là không xác định được. Do đó cách biểu
diễn này chỉ dùng trong một số trường hợp nhất định.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 49 - Bộ môn KHMT
Danh sách các con (Lists of Children)
• Trong cách biểu diễn này, với mỗi nút của cây ta cất giữ một danh sách các con của nó.
• Danh sách con có thể biểu diễn bởi một trong những cách biểu
diễn danh sách đã trình bày trong chương trước.
• Tuy nhiên, để ý rằng số lượng con của các nút là rất khác
nhau, nên danh sách móc nối thường là lựa chọn thích hợp nhất.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 50
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Danh sách các con (Lists of Children) 1 2 3 2 4 5 1 3 6 10 4 2 3 5 6 7 8 9 4 5 6 10 7 8 7 8 9 9 10 header
Có mảng con trỏ đến đầu các danh sách con của các nút 1, 2, . . . , 10:
header[i] trỏ đến danh sách con của nút i.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 51 - Bộ môn KHMT
Danh sách các con (Lists of Children)
Ví dụ: Có thể sử dụng mô tả sau đây để biểu diễn cây
typedef ? NodeT; /* dấu ? cần thay bởi định nghĩa kiểu phù hợp */
typedef ? ListT; /* dấu ? cần thay bởi định nghĩa kiểu danh sách phù hợp */ typedef ? position; typedef struct { ListT header[maxNodes]; labeltype labels[maxNodes]; NodeT root; } TreeT;
• Ta giả thiết rằng gốc của cây được cất giữ trong trường root và 0 để thể hiện nút rỗng.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 52
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Cài đặt leftmost_child
• Dưới đây là minh họa cài đặt phép toán leftmost_child. Việc
cài đặt các phép toán còn lại được coi là bài tập.
NodeT leftmost_child (NodeT n, TreeT T)
/* trả lại con trái nhất của nút n trong cây T */ {

ListT L; /* danh sách các con của n */ L = T.header[n];
if (empty(L)) /* n là lá */
return(0);
else return(retrive ( first(L), L)); }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 53
Dùng con trái và em kế cận phải
(The Leftmost-Child, Right-Sibling Representation)
Rõ ràng, mỗi một nút của cây chỉ có thể có:
– hoặc là không có con, hoặc có đúng một nút con cực trái (con cả);
– hoặc là không có em kế cận phải, hoặc có đúng một nút em kế cận phải (right-sibling). •
Vì vậy để biểu diễn cây ta có thể lưu trữ thông tin về con cực trái và em kế
cận phải của mỗi nút. Ta có thể sử dụng mô tả sau: struct Tnode {
char word[20]; // Dữ liệu cất giữ ở nút
struct Tnode *leftmost_child;
struct Tnode *right_sibling; };
typedef struct Tnode treeNode; treeNode Root;
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 54
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Biểu diễn cây bởi con trái và em kề cận phải A A B C D B C D E F G E F G H I J K H I J K
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 55 - Bộ môn KHMT
Biểu diễn cây tổng quát bởi cây nhị phân
(con trái và con phải=em kề cận phải) A B A E C B C D F G D H E F G I J H I J K K Cây nhị phân
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013 NGUYỄN ĐƯC NGHĨA 56 - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Dùng con trái và em kế cận phải
(The Leftmost-Child, Right-Sibling Representation)
• Với cách biểu diễn này, các thao tác cơ bản dễ dàng cài đặt.
Duy chỉ có thao tác parent là đòi hỏi phải duyệt danh sách nên
không hiệu quả. Trong trường hợp phép toán này phải dùng
thường xuyên, người ta chấp nhận bổ sung thêm 1 trường nữa
vào bản ghi để lưu cha của nút.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 57 4.2. CÂY NHỊ PHÂN
4.2.1. Định nghĩa và tính chất
4.2.2. Biểu diễn cây nhị phân
4.2.3. Duyệt cây nhị phân
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 58
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
4.2.1. Định nghĩa cây nhị phân - Binary Tree
Định nghĩa. Cây nhị phân là cây mà mỗi nút có nhiều nhất là hai con.
– Vì mỗi nút chỉ có không quá hai con, nên ta sẽ gọi chúng là con trái
con phải (left and right child).
– Như vậy mỗi nút của cây nhị phân hoặc là không có con, hoặc chỉ có
con trái, hoặc chỉ có con phải, hoặc có cả con trái và con phải. Con trái Con phải
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 59 - Bộ môn KHMT Chú ý
Vì ta phân biệt con trái và con phải, nên khái niệm cây nhị phân là không
trùng với cây có thứ tự định nghĩa ở 4.1. • Ví dụ: a a a b b b c c d d c d e e e Cây nhị phân T Cây nhị phân T Cây tổng quát 1 2
Vì thế, chúng ta sẽ không so sánh cây nhị phân với cây tổng quát
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013 NGUYỄN ĐƯC NGHĨA 60 - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Tính chất của cây nhị phânBổ đề 1.
(i) Số đỉnh lớn nhất ở trên mức i của cây nhị phân là 2i-1, i≥1.
(ii) Một cây nhị phân với chiều cao k có không quá 2k-1 nút, k ≥ 1.
(iii) Một cây nhị phân có n nút có chiều cao tối thiểu là log (n+1). 2 • Chứng minh:
(i) Bằng qui nạp theo i.
Cơ sở: Gốc là nút duy nhất trên mức i=1. Như vậy số đỉnh lớn nhất
trên mức i=1 là 20= 2i-1.
Chuyển qui nạp: Giả sử với mọi j, 1 ≤ j < i, số đỉnh lớn nhất trên mức
j là 2j-1. Do số đỉnh trên mức i-1 là 2i -2, mặt khác theo định nghĩa mỗi
đỉnh trên cây nhị phân có không quá 2 con, ta suy ra số lượng nút lớn
nhất trên mức i là không vượt quá 2 lần số lượng nút trên mức i-1,
nghĩa là không vượt quá 2*2i - 2= 2i-1 .
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 61
Tính chất của cây nhị phân
• (ii) Số lượng nút lớn nhất của cây nhị phân chiều cao k
không vượt quá tổng số lượng nút lớn nhất trên các mức i = 1,
2, ..., k, theo bổ đề 1, số này là không vượt quá k i 1 2   2k 1. i 1 
• (iii) Cây nhị phân n nút có chiều cao thấp nhất k khi số lượng
nút ở các mức i =1, 2, ..., k đều là lớn nhất có thể được. Từ đó ta có: k i 1
n   2   2k 1, suy ra 2k n 1, hay k  log (n 1)  . 2  i 1 
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013 NGUYỄN ĐƯC NGHĨA 62 - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Cây nhị phân đầy đủ (full binary tree)
Định nghĩa. Cây nhị phân đầy đủ (Full Binary Trees) là cây nhị phân thoả mãn
mỗi nút lá đều có cùng độ sâu và
các nút trong có đúng 2 con.
Bổ đề. Cây nhị phân đầy đủ với độ sâu n có 2n -1 nút.
Chứng minh. Suy trực tiếp từ bổ đề 1.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 63
Cây nhị phân hoàn chỉnh (Complete Binary Trees)
Định nghĩa. Cây nhị phân hoàn chỉnh (Complete Binary Trees): Cây
nhị phân độ sâu n thoả mãn:
– là cây nhị phân đầy đủ nếu không tính đến các nút ở độ sâu n, và
– tất cả các nút ở độ sâu n là lệch sang trái nhất có thể được. •
Bổ đề 3. Cây nhị phân hoàn chỉnh độ sâu n có số lượng nút nằm trong
khoảng từ 2n-1 đến 2n - 1. •
Chứng minh. Suy trực tiếp từ định nghĩa và bổ đề 1.
Ví dụ. Cây nhị phân hoàn chỉnh
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 64
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Cây nhị phân cân đối (balanced binary tree)
Định nghĩa. Cây nhị phân được gọi là cân đối (balanced ) nếu chiều cao
của cây con trái và chiều cao của cây con phải chênh lêch nhau không quá 1 đơn vị. • Nhận xét:
– Nếu cây nhị phân là đầy đủ thì nó là hoàn chỉnh
– Nếu cây nhị phân là hoàn chỉnh thì nó là cân đối Ví dụ: 1. Câ C y y n ào l à đ ầy y đủ? 2. Cây nào là hoàn chỉnh? 3. Cây nào là cân đối?
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 65 4.2. CÂY NHỊ PHÂN
4.2.1. Định nghĩa và tính chất
4.2.2. Biểu diễn cây nhị phân
4.2.3. Duyệt cây nhị phân
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 66
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
4.2.2. Biểu diễn cây nhị phân
• Ta xét hai phương pháp:
– Biểu diễn sử dụng mảng
– Biểu diễn sử dụng con trỏ
• Biểu diễn sử dụng mảng: Hoàn toàn tương tự như trong cách biểu diễn
cây tổng quát. Tuy nhiên, trong trường hợp cây nhị phân hoàn chỉnh, sử
dụng cách biểu diễn này ta có thể cài đặt nhiều phép toán với cây rất hiệu quả.
• Xét cây nhị phân hoàn chỉnh T n nút, trong đó mỗi nút chứa một giá
trị. Gán tên cho các nút của cây nhị phân hoàn chỉnh T từ trên xuống
dưới và từ trái qua phải bằng các số 1, 2,..., n. Đặt tương ứng cây T với
mảng A trong đó phần tử thứ i của A là giá trị cất giữ trong nút thứ i
của cây T, i = 1, 2, ..., n.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 67 Biểu d ểu iễn m
ễn ảng của cây nhị y phân ho n àn chỉ n nh Compl p et l e et Binary T y r T ee 1 H D 2 K 3 B 4 F 5 J 6 L 7 A C E
Biểu diễn kế tiếp (dùng mảng) 8 9 10 H D K B F J L A C E 0 1 2 3 4 5 6 7 8 9 10
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com NGUYỄN ĐƯC NGHĨA 68 - Bộ môn KHMT 1/28/2013
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Cây nhị y phân ho n àn chỉ n nh - Compl p et l e et Binary T y r T ee H D K B F J L A C E 0 1 2 3 4 5 6 7 8 9 10 Để Đ t ể ìm Sử Sử dụng Hạn H c ạn hế Con Co tr n ái á của ủ a A[i A ] [i A[2 A * [2 i * ] i 2* 2 i * < i = < = n Con Co p n h p ả h i ả của ủ a A[i A ] [i A[2 A * [2 i * i + 1 + ] 1 2* 2 i * + i + 1 < 1 = < = n Cha Ch c a ủa ủ a A[i A ] [i A[i A /2 [i ] /2 i > i 1 > Gốc ố A[1 A ] [1 A k A há h c á r ỗn ỗ g n Thử h A[i A ] [i là à lá? á Tr T ue u 2* 2 i * > i > n
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA 69 - Bộ môn KHMT 1/28/2013
Biểu diễn cây nhị phân dùng con trỏ
Mỗi nút của cây sẽ có con trỏ đến con trái và con trỏ đến con phải: Trỏ đến con trái Trỏ đến con phải key struct Tnode {
DataType Item; // DataType - kiểu dữ liệu của phần tử struct Tnode *left; struct Tnode *right; };
typedef struct Tnode treeNode;

CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013 70
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Ví dụ A B A E C B C D F G D H E F G I J H I J K K Cây nhị phân
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 71 - Bộ môn KHMT
Các phép toán cơ bản struct Tnode
{ char word[20]; // Dữ liệu của nút
struct Tnode * left; struct Tnode *right; };
typedef struct Tnode treeNode;

treeNode* makeTreeNode(char *word);
treeNode *RandomInsert(treeNode* tree,char *word); void freeTree(treeNode *tree);
void printPreorder(treeNode *tree);
void printPostorder(treeNode *tree);
void printInorder(treeNode *tree);
int countNodes(treeNode *tree); int depth(treeNode *tree);

CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 72
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 MakeNode
• Thông số: Dữ liệu của nút cần bổ sung • Các bước:
– phân bổ bộ nhớ cho nút mới
– kiểm tra cấp phát bộ nhớ có thành công?
– nếu đúng, đưa item vào nút mới
– đặt con trỏ trái và phải bằng NULL
• trả lại: con trỏ đến (là địa chỉ của) nút mới
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 73 Cài đặt MakeNode
treeNode* makeTreeNode(char *word) { treeNode* newNode = NULL;
newNode = (treeNode*)malloc(sizeof(treeNode)); if (newNode == NULL){
printf("Out of memory\n"); exit(1); } else { newNode->left = NULL; newNode->right= NULL;
strcpy(newNode->word,word); } return newNode; }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 74
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Cài đặt hàm tính số nút và độ sâu của cây
int countNodes(treeNode *tree) {
/* the function counts the number of nodes of a tree*/

if( tree == NULL ) return 0; else {
int ld = countNodes(tree->left);
int rd = countNodes(tree->right); return 1+ld+rd;
} }
int depth(treeNode *tree) {
/* the function computes the depth of a tree */

if( tree == NULL ) return 0; int ld = depth(tree->left);
int rd = depth(tree->right);

/* if (ld > rd) return 1+ld; else return 1+rd; */
return 1 + (ld > rd ? ld : rd); }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 75 Loại bỏ cây
void freeTree(treeNode *tree) { if( tree == NULL ) return; freeTree(tree->left); freeTree(tree->right); free(tree); return; }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 76
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Duyệt cây nhị phân
• Duyệt cây nhị phân là cách duyệt có hệ thống các nút của cây.
Tương tự cây tổng quát, ta xét ba thứ tự duyệt cây nhị phân:
Thứ tự trước (Preorder) NLR
– Thăm nút (Visit a node),
– Thăm cây con trái theo thứ tự trước (Visit left subtree),
– Thăm cây con phải theo thứ tự trước (Visit right subtree)
Thứ tự giữa (Inorder) LNR
– Thăm cây con trái theo thứ tự giữa (Visit left subtree),
– Thăm nút (Visit a node),
– Thăm cây con phải theo thứ tự giữa (Visit right subtree)
Thứ tự sau (Postorder) LRN
– Thăm cây con trái theo thứ tự sau (Visit left subtree),
– Thăm cây con phải theo thứ tự sau (Visit right subtree)
– Thăm nút (Visit a node),
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 77
Duyệt theo thứ tự trước - NLR Preorder Traversal
• Thăm nút (Visit the node).
• Duyệt cây con trái (Traverse the left subtree).
• Duyệt cây con phải (Traverse the right subtree).
void printPreorder(treeNode *tree) { if( tree != NULL ) {
printf("%s\n", tree->word); printPreorder(tree->left);
printPreorder(tree->right);
} }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 78
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Pre r o e rd r er e r Tra r ve v r e s r a s l 2 4 5 7 3 10 1 8 1 9 6 11 1
2, 4, 7, 1, 9, 3, 6, 5, 10, 8, 11
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA 79 - Bộ môn KHMT 1/28/2013
Duyệt theo thứ tự giữa - LNR Inorder Traversal
• Duyệt cây con trái (Traverse the left subtree).
• Thăm nút (Visit the node).
• Duyệt cây con phải (Traverse the right subtree).
void printInorder(treeNode *tree) { if( tree != NULL ) {
printInorder(tree->left); printf("%s\n", tree->word);
printInorder(tree->right);
} }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 80
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 In I ord r er e r Tra r ve v r e s r a s l 2 4 5 7 3 10 1 8 1 9 6 11 1
1, 7, 9, 4, 6, 3, 2, 10, 5, 11, 8
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN NGUYỄN ĐƯC NGHĨA 81 - Bộ môn KHMT 1/28/2013
Thứ tự giữa thu được bằng phép chiếu Inorder By Projection a b c f d e g j h i g d h b e i a f j c
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 82
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Duyệt theo thứ tự sau - LRN Postorder Traversal
• Duyệt cây con trái (Traverse the left subtree).
• Duyệt cây con phải (Traverse the right subtree).
• Thăm nút (Visit the node).
void printPostorder(treeNode *tree) { if( tree != NULL ) {
printPostorder(tree->left);
printPostorder(tree->right);
printf("%s\n", tree->word);
} }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 83 Posto s rd r er e r T ra r ve v r e s r a s l 2 4 5 7 3 10 1 8 1 9 6 11 1
1, 9, 7, 6, 3, 4, 10, 11, 8, 5, 2
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com NGUYỄN ĐƯC NGHĨA 84 - Bộ môn KHMT 1/28/2013
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Ví dụ: Duyệt cây nhị phân
Chú ý: Ta có thể xây dựng được cây nhị phân mà thứ tự trước và
thứ tự giữa hoặc thứ tự sau và thứ tự giữa là như nhau; nhưng không
thể có cây nhị phân mà thứ tự trước và thứ tự sau là như nhau.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 85
Chương trình minh hoạ
/* The program for testing binary tree traversal */ #include #include #include #include #include struct Tnode { char word[20]; struct Tnode * left; struct Tnode *right; };
typedef struct Tnode treeNode;
treeNode* makeTreeNode(char *word);
treeNode *RandomInsert(treeNode* tree,char *word);
void freeTree(treeNode *tree);
void printPreorder(treeNode *tree);
void printPostorder(treeNode *tree);
void printInorder(treeNode *tree);
int countNodes(treeNode *tree);
int depth(treeNode *tree);
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 86
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Chương trình minh hoạ int main() {
treeNode *randomTree=NULL; char word[20] = "a";
while( strcmp(word,"~")!=0)
{ printf("\nEnter item (~ to finish): "); scanf("%s", word);
if (strcmp(word,"~")==0) printf("Cham dut nhap thong tin nut... \n");
else randomTree=RandomInsert(randomTree,word); }
printf("The tree in preorder:\n"); printPreorder(randomTree);
printf("The tree in postorder:\n"); printPostorder(randomTree);
printf("The tree in inorder:\n"); printInorder(randomTree);
printf("The number of nodes is: %d\n",countNodes(randomTree));
printf("The depth of the tree is: %d\n", depth(randomTree)); freeTree(randomTree); getch(); return 0; }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 87
Gắn ngẫu nhiên nút mới vào cây
treeNode *RandomInsert(treeNode *tree,char *word){ treeNode *newNode, *p;
newNode = makeTreeNode(word); if ( tree == NULL ) return newNode; if ( rand()%2 ==0 ){ p=tree;
while (p->left !=NULL) p=p->left; p->left=newNode;
printf("Node %s is left child of %s \n",word,(*p).word); } else { p=tree;
while (p->right !=NULL) p=p->right; p->right=newNode;
printf("Node %s is right child of %s \n",word,(*p).word); } return tree; }
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 88
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Chương trình minh hoạ
/***********************************************
The program for testing binary tree traversal
************************************************/ #include #include #include #include #include struct Tnode { char word[20]; struct Tnode * left; struct Tnode *right; }; typedef struct Tnode treeNode;
treeNode* makeTreeNode(char *word);
treeNode *RandomInsert(treeNode* tree,char *word); void freeTree(treeNode *tree);
void printPreorder(treeNode *tree);
void printPostorder(treeNode *tree);
void printInorder(treeNode *tree);
int countNodes(treeNode *tree); int depth(treeNode *tree); int main() { treeNode *randomTree=NULL; char word[20] = "a"; while( strcmp(word,"~")!=0)
{ printf("\nEnter item (~ to finish): "); scanf("%s", word); if ( strcmp(word,"~")==0 )
printf("Cham dut nhap thong tin nut... \n");
else randomTree=RandomInsert(randomTree,word); }
printf("The tree in preorder:\n"); printPreorder(randomTree);
printf("***************************************************\n");
printf("The tree in postorder:\n"); printPostorder(randomTree);
printf("***************************************************\n");
printf("The tree in inorder:\n"); printInorder(randomTree);
printf("***************************************************\n");
printf("The number of nodes is: %d\n",countNodes(randomTree));
printf("The depth of the tree is: %d\n", depth(randomTree)); freeTree(randomTree); getch();
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN return 0; 1/28/2013 }
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 89
4.3. Các ví dụ ứng dụng
4.3.1. Cây biểu thức 4.3.2. Cây mã Huffman
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 90
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
4.3.1. Cây biểu thức An n a p a pli l c i at a i t o i n n o f b in i a n r a y r t r t e r e e s e : s Binary Expression Trees
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 91 Khái niệm
Cây biểu thức là cây nhị phân trong đó:
1. Mỗi nút lá chứa một toán hạng
2. Mỗi nút trong chứa một phép toán hai ngôi
3. Các cây con trái và phải của nút phép toán biểu diễn
các biểu thức con (subexpressions) cần được thực
hiện trước khi thực hiện phép toán ở gốc của các cây con.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 92
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Ví dụ: Cây nhị phân 4 mức ‘*’ ‘-’ ‘/’ ‘8’ ‘5’ ‘+’ ‘3’ ‘4’ ‘2’
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 93
Các mức thể hiện mức độ ưu tiên
• Mức (độ sâu) của các nút trên cây cho biết trình tự
thực hiện chúng (ta không cần sử dụng ngoặc để chỉ ra trình tự).
• Phép toán tại mức cao hơn của cây được thực hiện
muộn hơn so với các mức dưới chúng.
• Phép toán ở gốc luôn được thực hiện sau cùng.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 94
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Ví dụ: Xét Cây biểu thức ‘*’ ‘+’ ‘3’ ‘4’ ‘2’ Cây này có giá trị nào? ( 4 + 2 ) * 3 = 18
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 95
Sử dụng cây biểu thức ta có thể đưa ra biểu thức trong ký pháp
trung tố, tiền tố và hậu tố (infix, prefix, postfix) ‘*’ ‘-’ ‘/’ ‘8’ ‘5’ ‘+’ ‘3’ ‘4’ ‘2’ Infix:
( ( 8 - 5 ) * ( ( 4 + 2 ) / 3 ) ) Prefix: * - 8 5 / + 4 2 3 Postfix: 8 5 - 4 2 + 3 / *
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 96
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Thứ tự giữa của cây biểu thức
Inorder Of Expression Tree / * + e f + - a b c d a + b * c - d / e + f
Cho ta biểu thức trung tố (thiếu dấu ngoặc)!
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 97 Các ký pháp
• Duyệt cây biểu thức theo thứ tự trước (Preorder)
– Cho ta ký pháp tiền tố (Prefix Notation)
• Duyệt cây biểu thức theo thứ tự giữa (Inorder)
– Cho ta ký pháp trung tố (Infix Notation)
• Duyệt cây biểu thức theo thứ tự sau (Postorder)
– Cho ta ký pháp hậu tố (Postfix Notation)
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 98
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Ví dụ: Infix Notation + / / 1 3 * 4 6 7 1 / 3 + 6 * 7 / 4
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 99
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Ví dụ: Postfix Notation + / / 1 3 * 4 6 7
Còn gọi là: Reverse Polish Notation 1 3 / 6 7 * 4 / +
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013 100
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Ví dụ: Prefix + / / 1 3 * 4 6 7 + / 1 3 / * 6 7 4
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 101
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
4.3. Các ví dụ ứng dụng
4.3.1. Cây biểu thức 4.3.2. Cây mã Huffman
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN CuuDuongThanCong.com 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 102
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 4.3.3. Mã Huffman An n a p a pli l c i at a i t o i n n o f b in i a n r a y r t r t e r e e s e : s Huffman Code
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 103 - Bộ môn KHMT Mã Huffman
• Giả sử có một văn bản trên bảng chữ cái C. Với mỗi
chữ cái c C ta biết tần suất xuất hiện của nó trong
văn bản là f(c). Cần tìm cách mã hoá văn bản sử dụng David A. Huffman 1925-1999 ít bộ nhớ nhất.
– M· ho¸ ví i ®é dµi cè ®Þnh (fixed length code). DÔ m·
ho¸ còng nh­ dÔgi¶i m· , nh­ng l¹ i ®ßi hái bé nhí lí n
– M· phi tiÒn tè (prefix free code) lµ c¸ ch m· ho¸ mçi
ký tù c bëi mét x©u nhÞph©n code(c) sao cho m· cña
mét ký tù bÊt kú kh«ng lµ ®o¹ n ®Çu cña bÊt cø m·
cña ký tù nµo trong sè c¸ c ký tù cßn l¹ i. Tuy ®ßi hái
viÖc m· ho¸ vµ gi¶i m· phøc t¹ p h¬n nh­ng th«ng
th­êng tá ra ®ßi hái Ýt bé nhí h¬n.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 104 - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750
Mã hoá độ dài cố định
• Để mã hoá 26 chữ cái tiếng Anh bởi mã nhị phân độ dài cố
định, độ dài của xâu tối thiểu là [log 26] =5 bit.
• Các xâu từ 11011 đến 11111 không sử dụng
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 105 - Bộ môn KHMT
Cây mã hoá độ dài cố định
• Mã hoá độ dài cố định là mã phi tiền tố
• Giải mã 0011101000  HI
• Các nút * không sử dụng
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 106 - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Morse Code
• Căn cứ vào thống kê tần suất của các chữ cái trong tiếng Anh
• Morse đề xuất cách mã hoá:
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 107 - Bộ môn KHMT Cây mã hoá Morse
• Mã hoá Morse không là phi tiền tố
• Giải mã “....-” ??? Chịu chết?
• Phải có dấu phân biệt các chữ cái: “..#..-”  IU • Cây không đầy đủ
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 108 - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Mã Huffman
• Mỗi mã phi tiền tố có thể biểu diễn bởi một cây nhị
phân T mà mỗi lá cuả nó tương ứng với một chữ cái
và cạnh của nó được gán cho một trong hai số 0 hoặc 1.
• Mã của một chữ cái c là 1 dãy nhị phân gồm các số
gán cho các cạnh trên đường đi từ gốc đến lá tương ứng với c.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 109 - Bộ môn KHMT Mã Huffman
Bài toán: Tìm cách mã hoá tối ưu, tức là tìm cây nhị phân T
làm tối thiểu hoá tổng độ dài có trọng số B T
( )   f (c) depth(c)  c C
trong đó depth(c) là độ dài đường đi từ gốc đến lá tương ứng với ký tự c.
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 110 - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 Mã Huffman
• Ý tưởng thuật toán:
• Chữ cái có tần suất nhỏ hơn cần được gán cho lá có khoảng
cách đến gốc là lớn hơn; chữ cái có tần suất xuất hiện lớn hơn
cần được gán cho nút gần gốc hơn
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 111 - Bộ môn KHMT
Mã Huffman: Thuật toán procedure Huffman(C, f); begin n  |C|; Q  C;
for i:=1 to n-1 do begin
x, y  2 chữ cái có tần suất nhỏ nhất trong Q; (* Thao tác 1 *)
Tạo nút p với hai con x, y; f(p) := f(x) + f(y); Q  Q \ {x, y}  {p} (* Thao tác 2 *) end; end;
M· x©y dùng theo thuËt to¸n Huffman th­êng ®­îc gäi lµ m· Huffman (Huffman Code).
Có thể cài đặt với thời gian O(n log n) sử dụng priority queue
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 112 - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 X©y dùng m· Huffman Char Freq E 125
• Tần suất của các ký tự trong văn bản. T 93 A 80 O 76 I 72 N 71 S 65 R 61 H 55 L 41 D 40 C 31 U 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 113 - Bộ môn KHMT X©y dùng m· Huffman A O T E 80 76 93 125 D L R S N I H 61 65 71 73 40 41 55 C U 31 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 114
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 X©y dùng m· Huffman A O T E 80 76 93 125 D L R S N I H 61 65 71 73 40 41 58 55 C U 31 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 115
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT X©y dùng m· Huffman A O T E 80 76 81 93 125 D L R S N I H 61 65 71 73 40 41 58 55 C U 31 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 116
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 X©y dùng m· Huffman A O T E 80 76 81 93 125 113 D L R S N I H 61 65 71 73 40 41 58 55 C U 31 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 117
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT X©y dùng m· Huffman A O T E 80 76 81 93 126 125 113 D L R S N I H 61 65 71 73 40 41 58 55 C U 31 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 118
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 X©y dùng m· Huffman A O T E 80 76 81 93 126 144 125 113 D L R S N I H 61 65 71 73 40 41 58 55 C U 31 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 119
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT X©y dùng m· Huffman 156 A O T E 80 76 81 93 126 144 125 113 D L R S N I H 61 65 71 73 40 41 58 55 C U 31 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 120
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 X©y dùng m· Huffman 156 174 A O T E 80 76 81 93 126 144 125 113 D L R S N I H 61 65 71 73 40 41 58 55 C U 31 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 121
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT X©y dùng m· Huffman 156 174 238 A O T E 81 126 144 113 D L R S N I H 58 C U
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 122
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 X©y dùng m· Huffman 156 174 270 238 A O T E 80 76 81 93 126 144 125 113 D L R S N I H 61 65 71 73 40 41 58 55 C U 31 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 123
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT X©y dùng m· Huffman 330 156 174 270 238 A O T E 80 76 81 93 126 144 125 113 D L R S N I H 61 65 71 73 40 41 58 55 C U 31 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 124
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 X©y dùng m· Huffman 330 508 156 174 270 238 A O T E 80 76 81 93 126 144 125 113 D L R S N I H 61 65 71 73 40 41 58 55 C U 31 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013 125
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT X©y dùng m· Huffman 0 1 838 0 330 1 508 0 1 0 1 0 156 0 1 174 1 270 0 1 238 A O T E 80 76 81 1 93 0 126 1 0 144 1 125 0 113 0 1 D L R S N I H 61 65 71 73 40 41 58 55 0 1 C U 31 27
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 126
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 X©y dùng m· Huffman Char Freq Fixed Huff E 125 0000 110 T 93 0001 011 A 80 0010 000 O 76 0011 001 I 73 0100 1011 N 71 0101 1010 S 65 0110 1001 R 61 0111 1000 H 55 1000 1111 L 41 1001 0101 D 40 1010 0100 C 31 1011 11100 U 27 1100 11101 Tæng 838 3352 3036 1/28/2013 127 Mã Huffman: Giải mã
procedure Huffman_Decode(B);
(* B lµ x©u m· hãa văn b¶n theo m· ho¸ Huffman. *) begin While do begin
x  bit tiÕp theo trong x©u B; If x = 0 then P  Con tr¸ i cña P Else P  Con ph¶i cña P
If (P lµ nót l¸ ) then begin
<ĐÆt l¹ i P lµ gèc cña c©y Huffman> end; end end;
CẤU TRÚC DỮ LIỆU VÀ THUẬT TO CuuDuongThanCong.comÁN 1/28/2013 NGUYỄN ĐƯC NGHĨA 128 - Bộ môn KHMT
Downloaded by v?n ti?n Lê (vantienle525@gmail.com) lOMoARcPSD|36442750 QUESTIONS?
CẤU TRÚC DỮ LIỆU VÀ THUẬT TOÁN 1/28/2013
NGUYỄN ĐƯC NGHĨA - Bộ môn KHMT 129 CuuDuongThanCong.com
Downloaded by v?n ti?n Lê (vantienle525@gmail.com)