Cây

8.3. Các phương pháp duyệt cây
Tài liệu này được soạn theo sách Toán học rời rạc ứng dụng trong tin học , K. H.
Rosen, người dòch: Phạm Văn Thiều và Đặng Hữu Thònh, Nhà xuất bản Khoa học
và kỹ thuật, 1998.
Tài liệu lưu hành nội bộ

10/01/15

8.3. Các phương

1


Hệ đòa chỉ phổ dụng
•

•

•

Hệ đòa chỉ phổ dụng là cách gán nhãn cho tất cả các đỉnh bằng
phương pháp truy hồi như sau:
– Gán nhãn cho gốc bằng số nguyên 0. Sau đó k đỉnh con của nó
(ở mức 1) từ trái sang phải được gán các nhãn là 1, 2, 3,…, k.
– Với mọi đỉnh v ở mức n có nhãn là A, thì kv đỉnh con của nó từ
trái sang phải được gán các nhãn là A.1, A.2,…, A.kv .
Nhận xét: Theo thủ tục này, đỉnh v ở mức n, với n ≥ 1, có nhãn là
x1.x2…xn , trong đó đỉnh xi ở mức i.
Ứng dụng: sắp tất cả các đỉnh của cây theo thứ tự từ điển của các


5

4.1 5.1 5.2 5.3

3.1.2
3.1.1
3.1.2.1

5.1.1

3.1.3
3.1.2.4

3.1.2.2 3.1.2.3

10/01/15

8.3. Các phương

3


Các thuật toán duyệt cây
•

Đònh nghóa 1. Giả sử T là cây có gốc và được sắp thứ tự với gốc r.
– Nếu T chỉ có r thì r là cách duyệt tiền thứ tự của T;
– nếu không thì gọi T1, T2,…, Tn là các cây con tại r từ trái qua phải
của T.

Bước 2:
thăm T1
kiểu tiền thứ tự

Bước 3:
thăm T2
kiểu tiền thứ tự

Bước n + 1:
thăm Tn
kiểu tiền thứ tự

8.3. Các phương

5


Các thuật toán duyệt cây
•

Ví dụ 2. Duyệt kiểu tiền thứ tự sẽ viếng thăm các đỉnh của cây có
gốc và được sắp dưới đây theo thứ tự nào?
a
b

k

f

h i

a

c

b
e

d g h i

l
n

o

m

p

p

b e j

k

f c

n

o


k

n

a

d

d g l

b e j

m h i

k n o p f c

8.3. Các phương

d g l

7

m h i


Các thuật toán duyệt cây
•

•
•

° duyệt trung thứ tựï sẽ bắt đầu bằng việc duyệt T theo kiểu
1
trung thứ tựï,
° sau đó viếng thăm r,
° tiếp tục duyệt T theo kiểu trung thứ tự, tiếp tục duyệt T theo
2
3
kiểu trung thứ tự,… cho đến khi Tn được duyệt theo kiểu trung
thứ tự.

10/01/15

8.3. Các phương

9


Các thuật toán duyệt cây
•

Duyệt cây theo kiểu trung thứ tự
r

T1

Bước 2: thăm r

T2

Tn


j
n

d

g

e

10/01/15

c

o

m

p

8.3. Các phương

11


Các thuật toán duyệt cây
•

Ví dụ 3. (tiếp theo)
a

d

h i

f

a

c

l

g

m

d

h i

p

o

j

d h i

n


j

e

n

k

e

k

b

n

o

p

o

p

b

8.3. Các phương

12


– Nếu T chỉ có r thì r là cách duyệt hậu thứ tự của T;
– nếu không, thì gọi T1, T2,…, Tn là các cây con tại r từ trái qua phải
của T,
° duyệt hậu thứ tựï sẽ bắt đầu bằng việc duyệt T theo kiểu hậu
1
thứ tựï, tiếp tục duyệt T2 theo kiểu hậu thứ tự,,… cho đến khi
Tn được duyệt theo kiểu hậu thứ tự.
°

10/01/15

cuối cùng viếng thăm r.

8.3. Các phương

14


Các thuật toán duyệt cây
•

Duyệt cây theo kiểu hậu thứ tự
r

10/01/15

Bước n + 1: thăm r

T1



f

h i
l

j
n

d

g

e

10/01/15

c

o

m

p

8.3. Các phương

16



i

d a

m

l

j

m

l

p

p

j

10/01/15

g

b c

k

f


e f

b c l

8.3. Các phương

m

g

h

17

i

d a


Các thuật toán duyệt cây
•

Thuật toán 3. Duyệt kiểu hậu thứ tự
procedure postorder(T: cây có gốc và được sắp)
r := gốc của T
for mỗi cây con c của r từ trái sang phải
begin
T(c) := cây con với gốc c
postorder(T(c))
end

Ví dụ 5. Tìm cây có gốc biểu diễn biểu thức
((x + y) ↑ 2) + ((x − 4) / 3).
– Xây dựng cây nhò phân cho biểu thức trên từ dưới lên.
+

−
+

x

x

y

4

↑

↑
+

/
2

+

10/01/15

y


Các ký pháp trung tố, tiền tố và hậu tố
– Nhận được dạng trung tố của biểu thức khi duyệt cây có gốc
theo kiểu trung thứ tự và dùng các dấu ngoặc mỗi khi gặp một
phép toán.

10/01/15

8.3. Các phương

21


Các ký pháp trung tố, tiền tố và hậu tố
•

+

+
/

+

+
x

x

+
y



8.3. Các phương

22

3


Các ký pháp trung tố, tiền tố và hậu tố
– Nhận được dạng tiền tố của biểu thức khi duyệt cây có gốc theo
kiểu tiền thứ tự.
– Biểu thức dưới dạng tiền tố được gọi là ký pháp Ba lan.

10/01/15

8.3. Các phương

23


Các ký pháp trung tố, tiền tố và hậu tố
•

Ví dụ 6. Dạng tiền tố của biểu thức ((x + y) ↑ 2) + ((x − 4) / 3)
– Duyệt cây nhò phân biểu diển biểu thức trên theo kiểu tiền thứ
tự
∀ ⇒ Dạng tiền tố: + ↑ + x y 2 / − x 4 3

10/01/15