Bài giảng Cấu trúc dữ liệu và giải thuật

Ch-¬ng 4

c © y

Trong ch-¬ng nµy chóng ta sÏ nghiªn cøu m« h×nh d÷ liÖu c©y. C©y lµ

mét cÊu tróc ph©n cÊp trªn mét tËp hîp nµo ®ã c¸c ®èi t-îng. Mét vÝ dô quen

thuéc vÒ c©y, ®ã lµ c©y th- môc. C©y ®-îc sö dông réng r·i trong rÊt nhiÒu

vÊn ®Ò kh¸c nhau. Ch¼ng h¹n, nã ®-îc ¸p dông ®Ó tæ chøc th«ng tin trong c¸c

hÖ c¬ së d÷ liÖu, ®Ó m« t¶ cÊu tróc có ph¸p cña c¸c ch-¬ng tr×nh nguån khi

x©y dùng c¸c ch-¬ng tr×nh dÞch. RÊt nhiÒu c¸c bµi to¸n mµ ta gÆp trong c¸c

lÜnh vùc kh¸c nhau ®-îc quy vÒ viÖc thùc hiÖn c¸c phÐp to¸n trªn c©y. Trong

ch-¬ng nµy chóng ta sÏ tr×nh bµy ®Þnh nghÜa vµ c¸c kh¸i niÖm c¬ b¶n vÒ c©y.

Chóng ta còng sÏ xÐt c¸c ph-¬ng ph¸p cµi ®Æt c©y vµ sù thùc hiÖn c¸c phÐp

to¸n c¬ b¶n trªn c©y. Sau ®ã chóng ta sÏ nghiªn cøu kü mét d¹ng c©y ®Æc

biÖt, ®ã lµ c©y t×m kiÕm nhÞ ph©n.

4.1. C©y vµ c¸c kh¸i niÖm vÒ c©y

H×nh 4.1 minh ho¹ mét c©y T. §ã lµ mét tËp hîp T gåm 11 phÇn tö,

T={a, b, c, d, e, f, g, h, i, j, k}. C¸c phÇn tö cña T ®-îc gäi lµ c¸c ®Ønh cña c©y

T. TËp T cã cÊu tróc nh- sau. C¸c ®Ønh cña T ®-îc ph©n thµnh c¸c líp kh«ng

c¾t nhau : líp thø nhÊt gåm mét ®Ønh duy nhÊt a, ®Ønh nµy gäi lµ gèc cña c©y;

líp thø hai gåm c¸c ®Ønh b, c ; líp thø ba gåm c¸c ®Ønh d, e, f, g, h vµ líp

cuèi cïng gåm c¸c ®Ønh i, j, k, mçi ®Ønh thuéc mét líp (trõ gèc), cã mét cung

duy nhÊt nèi víi mét ®Ønh nµo ®ã thuéc líp kÒ trªn. (Cung nµy biÓu diÔn mèi

quan hÖ nµo ®ã).

a

b

c

d

e

f

g

k

h

i

j

H×nh 4.1 BiÓu diÔn h×nh häc mét c©y

0

Trong to¸n häc cã nhiÒu c¸ch ®Þnh nghÜa c©y. ë ®©y chóng ta ®-a ra

®Þnh nghÜa ®Ö quy vÒ c©y. §Þnh nghÜa nµy cho phÐp ta xuÊt ph¸t tõ c¸c c©y

®¬n gi¶n nhÊt ( c©y chØ cã mét ®Ønh) x©y dùng nªn c¸c c©y lín h¬n.

C©y (c©y cã gèc) ®-îc x¸c ®Þnh ®Ö quy nh- sau.

1. TËp hîp gåm mét ®Ønh lµ c©y. C©y nµy cã gèc lµ ®Ønh duy nhÊt cña

nã.

2. Gi¶ sö T₁, T₂, ... , T_k(k  1) lµ c¸c c©y cã gèc t-¬ng øng lµ r₁,r₂...,r_k.

C¸c c©y T_i(i = 1, 2,...k) , kh«ng kh«ng c¾t nhau tøc lµ T_i T_j=  víi i  j.

Gi¶ sö r lµ mét ®Ønh míi kh«ng thuéc c¸c c©y Ti (i = 1, 2,... , k). Khi ®ã, tËp

hîp T gåm ®Ønh r vµ tÊt c¶ c¸c ®Ønh cña c©y T_i(i = 1, 2, ... , k) lËp thµnh mét

c©y míi víi gèc r. C¸c c©y T_i(i = 1, 2, ... , k) ®-îc gäi lµ c©y con cña gèc r.

Trong biÓu diÔn h×nh häc cña c©y T, mçi ®Ønh r_i(i =1, 2, ... ,k) cã cung nèi

víi gèc r (xem h×nh 4.2)

r

r₁

r₂

r_k

T₁

T₂

T_k

H×nh 4.2 C©y cã gèc r vµ c¸c c©y con cña gèc T₁, T₂, ... , T_k.

Cha, con, ®-êng ®i.

Tõ ®Þnh nghÜa c©y ta suy ra r»ng, mçi ®Ønh cña c©y lµ gèc cña c¸c c©y

con cña nã. Sè c¸c c©y con cña mét ®Ønh gäi lµ bËc cña ®Ønh ®ã. C¸c ®Ønh cã

bËc kh«ng ®-îc gäi lµ l¸ cña c©y.

NÕu ®Ønh b lµ gèc cña mét c©y con cña ®Ønh a th× ta nãi ®Ønh b lµ con

cña ®Ønh a vµ a lµ cha cña b. Nh- vËy, bËc cña mét ®Ønh lµ sè c¸c ®Ønh con

cña nã, cßn l¸ lµ ®Ønh kh«ng cã con. C¸c ®Ønh cã Ýt nhÊt mét con ®-îc gäi lµ

®Ønh trong. C¸c ®Ønh cña c©y hoÆc lµ l¸ hoÆc lµ ®Ønh trong.

C¸c ®Ønh cã cïng mét cha ®-îc gäi lµ anh em. Mét d·y c¸c ®Ønh a₁, a₂,

... a_n(n  1), sao cho a_i(i = 1, 2, ... , n-1) lµ cha cña a_i+1®-îc gäi lµ ®-êng ®i

tõ a₁®Õn a_n. §é dµi cña ®-êng ®i nµy lµ n-1. Ta cã nhËn xÐt r»ng, lu«n lu«n

tån t¹i mét ®-êng ®i duy nhÊt tõ gèc tíi mét ®Ønh bÊt kú trong c©y.

1

NÕu cã mét ®-êng ®i tõ ®Ønh a ®Õn ®Ønh b cã ®é dµi k  1, th× ta nãi a lµ

tiÒn th©n cña b vµ b lµ hËu thÕ cña a.

VÝ dô. Trong c©y ë h×nh 4.1, ®Ønh c lµ cha cña ®Ønh f, g, h. C¸c ®Ønh d,

i, j, k vµ h lµ l¸, c¸c ®Ønh cßn l¹i lµ ®Ønh trong. a, c, g, k lµ ®-êng ®i cã ®é dµi

3 tõ a ®Õn k. §Ønh b lµ tiÒn th©n cña c¸c ®Ønh d, e, i, j.

C©y con.

Tõ ®Þnh nghÜa c©y ta cã, mçi ®Ønh a bÊt kú cña c©y T lµ gèc cña mét

c©y nµo ®ã, ta gäi c©y nµy lµ c©y con cña c©y T. Nã gåm ®Ønh a vµ tÊt c¶ c¸c

®Ønh lµ hËu thÕ cña a. Ch¼ng h¹n, víi c©y T trong h×nh 4.1, T₁= {c, f, g, h, k}

lµ mét c©y con

§é cao, møc.

Trong mét c©y, ®é cao cña mét ®Ønh a lµ ®é dµi cña ®-êng ®i dµi nhÊt

tõ a ®Õn mét l¸. §é cao cña gèc ®-îc gäi lµ ®é cao cña c©y. Møc cña ®Ønh a lµ

®é dµi cña ®-êng ®i tõ gèc ®Õn a. Nh- vËy gèc cã møc 0.

VÝ dô. Trong c©y ë h×nh 4.1, ®Ønh b cã dé cao lµ 2, c©y cã ®é cao lµ 3.

C¸c ®Ønh b, c cã møc 1 ; c¸c ®Ønh d, e, f, g, h cã møc 2, cßn møc cña c¸c ®Ønh

i, j, k lµ 3.

C©y ®-îc s¾p.

Trong mét c©y, nÕu c¸c c©y con cña mçi ®Ønh ®-îc s¾p theo mét thø tù

nhÊt ®Þnh, th× c©y ®-îc gäi lµ c©y ®-îc s¾p. Ch¼ng h¹n, h×nh 4.3 minh ho¹ hai

c©y ®-îc s¾p kh¸c nhau,

a



b

c

b

H×nh 4.3. Hai c©y ®-îc s¾p kh¸c nhau

Sau nµy chóng ta chØ quan t©m ®Õn c¸c c©y ®-îc s¾p. Do ®ã khi nãi ®Õn

c©y th× cÇn ®-îc hiÓu lµ c©y ®-îc s¾p.

Gi¶ sö trong mét c©y ®-îc s¾p T, ®Ønh a cã c¸c con ®-îc s¾p theo thø

tù : b₁, b₂, ..., b_k(k  1). Khi ®ã ta nãi b₁lµ con tr-ëng cña a, vµ b_ilµ anh liÒn

kÒ cña b_i+1(b_i+1lµ em liÒn kÒ cña b_i), i = 1,2, ..., k-1. Ta cßn nãi, víi i < j th×

2

b_ië bªn tr¸i b_j(b_jë bªn ph¶i b_i). Quan hÖ nµy ®-îc më réng nh- sau. NÕu a ë

bªn tr¸i b th× mäi hËu thÕ cña a ë bªn tr¸i mäi hËu thÕ cña b.

VÝ dô. Trong h×nh 4.1, f lµ con tr-ëng cña c, vµ lµ anh liÒn kÒ cña ®Ønh

g. §Ønh i ë bªn tr¸i ®Ønh g.

C©y g¾n nh·n.

C©y g¾n nh·n lµ c©y mµ mçi ®Ønh cña nã ®-îc g¾n víi mét gi¸ trÞ

(nh·n) nµo ®ã. Nãi mét c¸ch kh¸c, c©y g¾n nh·n lµ mét c©y cïng víi mét ¸nh

x¹ tõ tËp hîp c¸c ®Ønh cña c©y vµo tËp hîp nµo ®ã c¸c gi¸ trÞ (c¸c nh·n).

Chóng ta cã thÓ xem nh·n nh- th«ng tin liªn kÕt víi mçi ®Ønh cña c©y. Nh·n

cã thÓ lµ c¸c d÷ liÖu ®¬n nh- sè nguyªn, sè thùc, hoÆc còng cã thÓ lµ c¸c d÷

liÖu phøc t¹p nh- b¶n ghi. CÇn biÕt r»ng, c¸c ®Ønh kh¸c nhau cña c©y cã thÓ

cã cïng mét nh·n.

Rõng.

Mét rõng F lµ mét danh s¸ch c¸c c©y :

F = (T₁, T₂, ..., T_n)

trong ®ã T_i(i = 1, ..., n) lµ c©y (c©y ®-îc s¾p)

Chóng ta cã t-¬ng øng mét - mét gi÷a tËp hîp c¸c c©y vµ tËp hîp c¸c

rõng. ThËt vËy, mét c©y T víi gèc r vµ c¸c c©y con cña gèc theo thø tù tõ tr¸i

sang ph¶i lµ T₁, T₂, ..., T_n, T = (r, T₁, T₂, ..., T_n) t-¬ng øng víi rõng F = (T₁,

T₂, ..., T_n) vµ ng-îc l¹i.

4.2. C¸c phÐp to¸n trªn c©y.

Trong môc 1 chóng ta ®· tr×nh bµy cÊu tróc to¸n häc c©y. §Ó cã mét

m« h×nh d÷ liÖu c©y, ta cÇn ph¶i x¸c ®Þnh c¸c phÐp to¸n cã thÓ thùc hiÖn ®-îc

trªn c©y. Còng nh- víi danh s¸ch, c¸c phÐp to¸n cã thÓ thùc hiÖn ®-îc trªn

c©y rÊt ®a d¹ng vµ phong phó. Trong sè ®ã, cã mét sè phÐp to¸n c¬ b¶n ®-îc

sö dông th-êng xuyªn ®Ó thùc hiÖn c¸c phÐp to¸n kh¸c vµ thiÕt kÕ c¸c thuËt

to¸n trªn c©y.

4. 2.1. C¸c phÐp to¸n c¬ b¶n trªn c©y.

1. T×m cha cña mçi ®Ønh.

Gi¶ sö x lµ ®Ønh bÊt kú trong c©y T. Hµm Parent(x) x¸c ®Þnh cha cña

®Ønh x. Trong tr-êng hîp ®Ønh x kh«ng cã cha (x lµ gèc) th× gi¸ trÞ cña hµm

Parent (x) lµ mét ký hiÖu ®Æc biÖt nµo ®ã kh¸c víi tÊt c¶ c¸c ®Ønh cña c©y,

ch¼ng h¹n $. Nh- vËy nÕu parent (x) = $ th× x lµ gèc cña c©y.

2. T×m con bªn tr¸i ngoµi cïng (con truëng) cña mçi ®Ønh.

Hµm EldestChild (x) cho ta con tr-ëng cña ®Ønh x. Trong tr-êng hîp x

lµ l¸ (x kh«ng cã con) th× EldestChild (x) = $.

3

3. T×m em liÒn kÓ cña mçi ®Ønh.

Hµm NextSibling (x) x¸c ®Þnh em liÒn kÒ cña ®Ønh x. Trong tr-êng hîp

x kh«ng cã em liÒn kÒ (tøc x lµ con ngoµi cïng bªn ph¶i cña mét ®Ønh nµo ®ã)

th× NextSibling(x) = $.

VÝ dô. Gi¶ sö T lµ c©y ®· cho trong h×nh 4.1. Khi ®ã Parent(e) = b,

Parent(a) = $, EldestChild (c) = f, EldestChild (k) = $, NextSibling (g) = h,

NextSibling (h) = $.

4.2.2. §i qua c©y (duyÖt c©y).

Trong thùc tiÔn chóng ta gÆp rÊt nhiÒu bµi to¸n mµ viÖc gi¶i quyÕt nã

®-îc qui vÒ viÖc ®i qua c©y (cßn gäi lµ duyÖt c©y), "th¨m" tÊt c¶ c¸c ®Ønh cña

c©y mét c¸ch hÖ thèng.

Cã nhiÒu ph-¬ng ph¸p ®i qua c©y. Ch¼ng h¹n, ta cã thÓ ®i qua c©y lÇn

l-ît tõ møc 0, møc 1,... cho tíi møc thÊp nhÊt. Trong cïng mét møc ta sÏ

th¨m c¸c ®Ønh tõ tr¸i sang ph¶i. VÝ dô, víi c©y trong h×nh 4.1, danh s¸ch c¸c

®Ønh lÇn l-ît ®-îc th¨m lµ (a, b, c, d, e, f, g,h, i, j, k). §ã lµ ph-¬ng ph¸p ®i

qua c©y theo bÒ réng.

Tuy nhiªn, ba ph-¬ng ph¸p ®i qua c©y theo c¸c hÖ thèng sau ®©y lµ

quan träng nhÊt : ®i qua c©y theo thø tù Preorder, Inorder vµ Postorder. Danh

s¸ch c¸c ®Ønh cña c©y theo thø tù Preordor, Inorder, vµ Postorder (gäi t¾t lµ

danh s¸ch Preorder, Inorder, vµ Postorder) ®-îc x¸c ®Þnh ®Ö qui nh- sau :

1. NÕu T lµ c©y gåm mét ®Ønh duy nhÊt th× c¸c danh s¸ch Preordor,

Inorder vµ Postorder chØ chøa mét ®Ønh ®ã.

2. NÕu T lµ c©y cã gèc r vµ c¸c c©y con cña gèc lµ T₁, T₂, ..., T_k(h×nh

4.2) th×

2a. Danh s¸ch Preorder c¸c ®Ønh cña c©y T b¾t ®Çu lµ r, theo sau lµ c¸c

®Ønh cña c©y con T₁theo thø tù Preordor, råi ®Õn c¸c ®Ønh cña c©y con T₂

theo thø tù Preorder, ..., cuèi cïng lµ c¸c ®Ønh cña c©y con T_ktheo thø tù

Preordor.

2b. Danh s¸ch Inorder c¸c ®Ønh cña c©y T b¾t ®Çu lµ c¸c ®Ønh cña c©y

con T₁theo thø tù Inordor, råi ®Õn gèc r, theo sau lµ c¸c ®Ønh cña c¸c c©y con

T₂, ... T_ktheo thø tù Inordor.

2c. Danh s¸ch Postorder c¸c ®Ønh cña c©y T lÇn l-ît lµ c¸c ®Ønh cña c¸c

c©y con T₁, T₂,...T_k, theo thø tù Postorder sau cïng lµ gèc r.

VÝ dô, khi ®i qua c©y trong h×nh 4.1 theo thø tù Preordor ta ®-îc danh

s¸ch c¸c ®Ønh lµ (a, b, d, e, i, j, c, f, g, k, h). NÕu ®i qua c©y theo thø tù

Inorder, ta cã danh s¸ch (d, b, i, e, j, a, f, c, k, g, h). Cßn danh s¸ch Postorder

lµ (d, i, j, e, b, f, k, g, h, c, a).

4

Ph-¬ng ph¸p ®i qua c©y theo thø tù Preorder cßn ®-îc gäi lµ kü thuËt

®i qua c©y theo ®é s©u. §ã lµ mét kü thuËt quan träng th-êng ®-îc ¸p dông

®Ó t×m kiÕm nghiÖm cña c¸c bµi to¸n. Gäi lµ ®i qua c©y theo ®é s©u, bëi v× khi

ta ®ang ë mét ®Ønh x nµo ®ã cña c©y (ch¼ng h¹n, ®Ønh b trong c©y ë h×nh 4.1),

ta cè g¾ng ®i s©u xuèng ®Ønh cßn ch-a ®-îc th¨m ngoµi cïng bªn tr¸i chõng

nµo cã thÓ ®-îc (ch¼ng h¹n, ®Ønh d trong c©y ë h×nh 4.1) ®Ó th¨m ®Ønh ®ã.

NÕu tÊt c¶ c¸c ®Ønh con cña x ®· ®-îc th¨m (tøc lµ tõ x kh«ng thÓ ®i s©u

xuèng ®-îc) ta quay lªn t×m ®Õn cha cña x. T¹i ®©y ta l¹i cè g¾ng ®i s©u

xuèng ®Ønh con ch-a ®-îc th¨m. Ch¼ng h¹n, trong c©y ë h×nh 4.1, ta ®ang ë

®Ønh f, t¹i ®©y kh«ng thÓ ®i s©u xuèng, ta quay lªn cha cña f lµ ®Ønh c. T¹i c

cã thÓ ®i s©u xuèng th¨m ®Ønh g, tõ g l¹i cã thÓ ®i s©u xuèng th¨m ®Ønh k.

Qu¸ tr×nh trªn cø tiÕp tôc cho tíi khi nµo toµn bé c¸c ®Ønh cña c©y ®· ®-îc

th¨m.

§èi lËp víi kü thuËt ®i qua c©y theo ®é s©u lµ kü thuËt ®i qua c©y theo

bÒ réng mµ chóng ta ®· tr×nh bµy. Trong kü thuËt nµy, khi ®ang ë th¨m ®Ønh x

nµo ®ã cña c©y, ta ®i theo bÒ ngang sang bªn ph¶i t×m ®Õn em liÒn kÒ cña x ®Ó

th¨m. NÕu x lµ ®Ønh ngoµi cïng bªn ph¶i, ta ®i xuèng møc sau th¨m ®Ønh

ngoµi cïng bªn tr¸i, råi l¹i tiÕp tôc ®i theo bÒ ngang sang bªn ph¶i.

Sau ®©y chóng ta sÏ tr×nh bµy c¸c thñ tôc ®i qua c©y theo c¸c thø tù

Preorder, Inorder, Postorder vµ ®i qua c©y theo bÒ réng.

Sö dông c¸c phÐp to¸n c¬ b¶n trªn c©y vµ ®Þnh nghÜa ®Ö qui cña thø tù

Preorder, chóng ta dÔ dµng viÕt ®-îc thñ tôc ®Ö qui ®i qua c©y theo thø tù

Preorder. Trong thñ tôc, chóng ta sÏ sö dông thñ tôc Visit (x) (th¨m ®Ønh x)

nã ®-îc cµi ®Æt tuú theo tõng øng dông. C¸c biÕn A, B trong thñ tôc lµ c¸c

®Ønh (Node) cña c©y.

procedure Preorder ( A : Node) ;

{Thñ tôc ®Ö qui ®i qua c©y gèc A theo thø tù Preorder}

var B : Node

begin

Visit (A) ;

B : = EldestChild (A)

while B < > $ do

begin

Preorder ( B) ;

B : = NexSibling (B)

end ;

5

Mét c¸ch t-¬ng tù, ta cã thÓ viÕt ®-îc c¸c thñ tôc ®Ö qui ®i qua c©y

theo thø tù Inorder vµ Postorder.

procedure Inorder ( A : Node) ;

{Thñ tôc ®Ö qui ®i qua c©y gèc A theo thø tù Inorder }

var B : Node ;

begin

B := EldestChild (A) ;

if B < > $ then begin Inorder (B) : B : = NextSibling (B) end ;

Visit (A) ;

while B < > $ do

begin

Inorder (B) ;

B : = NextSibling (B)

end ;

procedure Postorder (A : Node) ;

{Thñ tôc ®Ö qui ®i qua c©y gèc A theo thø tù Postorder}

var

B : Node ;

begin

B : = EldestChild (A) ;

while B < > $ do

begin

Postorder (B) ;

B : = NextSibling (B)

end ;

Visit (A)

end ;

Chóng ta còng cã thÓ viÕt ®-îc c¸c thñ tôc kh«ng ®Ö qui ®i qua c©y

theo c¸c thø tù Preordor, Inorder vµ Postorder. Chóng ta sÏ viÕt mét trong ba

thñ tôc ®ã (c¸c thñ tôc kh¸c giµnh l¹i cho ®éc gi¶). T- t-ëng c¬ b¶n cña thuËt

to¸n kh«ng ®Ö qui ®i qua c©y theo thø tù Preorder lµ nh- sau. Chóng ta sÏ sö

dông mét stack S ®Ó l-u gi÷ c¸c ®Ønh cña c©y. NÕu ë mét thêi ®iÓm nµo ®ã ta

6

®ang ë th¨m ®Ønh x th× stack sÏ l-u gi÷ ®-êng ®i tõ gèc ®Õn x, gèc ë ®¸y cña

stack cßn x ë ®Ønh stack. Ch¼ng h¹n, víi c©y trong h×nh 4.1, nÕu ta ®ang ë

th¨m ®Ønh i, th× stack sÏ l-u (a, b, e, i) vµ i ë ®Ønh stack

procedure

Preorder ( A : Node) ;

{Thñ tôc kh«ng ®Ö qui ®i qua c©y theo thø tù Preorder}

var B : Node ;

S : Stack ;

begin

Intealize (S) ; {khëi t¹o stack rçng}

B : = A ;

while B < > $ do

begin

Visit (B) ;

Push (B, S) ; {®Èy B vµo stack}

B : = EldestChild (B)

end ;

while not Empty (S) do

begin

Pop (S,B) ;{lo¹i phÇn tö ë ®Ønh stack vµ g¸n cho B]

B : = NexSibling (B) ;

if B < > $ then

while B < > $ do

begin

Visit (B) ;

Push (B, S) ;

B : = EldestChild (B)

end ;

Sau ®©y chóng ta sÏ tr×nh bµy thuËt to¸n ®i qua c©y theo bÒ réng, chóng

ta sÏ sö dông hµng Q ®Ó l-u gi÷ c¸c ®Ønh theo thø tù ®· ®-îc th¨m, ®Çu hµng

lµ ®Ønh ngoµi cïng bªn tr¸i mµ ta ch-a th¨m c¸c con cña nã, cßn cuèi hµng lµ

7

®Ønh ta ®ang ë th¨m. Ch¼ng h¹n, víi c©y trong h×nh 4.1, nÕu ta ®ang ë th¨m

®Ønh i th× trong hµng sÏ chøa c¸c ®Ønh (f, g, h, i) trong ®ã f ë ®Çu hµng vµ i ë

cuèi hµng. Khi lo¹i mét phÇn tö ë ®Çu hµng, chóng ta sÏ lÇn l-ît th¨m c¸c con

cña nã (nÕu cã) vµ khi th¨m ®Ønh nµo th× ®-a ®Ønh ®ã vµo cuèi hµng. Chóng ta

cã thñ tôc sau

procedure BreadthTraverse ( A : Node) ;

{Thñ tôc ®i qua c©y gèc A theo bÒ réng }

var B : node ;

Q : Queue ;

begin

Initialize (Q) ; {khëi t¹o hµng rçng}

Visit (A) ;

Add (A, Q) ; {®-a gèc A vµo hµng Q}

while not Empty (Q) do

begin

Delete (Q, B) ; {lo¹i phÇn tö ®Çu hµng vµ g¸n cho B}

B : = EldestChild (B) ;

while B < > $ do

begin

Visit (B) ;

Add (B, Q) ;

B : = NextSibling (B)

end ;

4.3. Cµi ®Æt c©y.

Trong môc nµy chóng ta sÏ tr×nh bµy c¸c ph-¬ng ph¸p c¬ b¶n cµi ®Æt

c©y vµ nghiªn cøu kh¶ n¨ng thùc hiÖn c¸c phÐp to¸n c¬ b¶n trªn c©y trong

mçi c¸ch cµi ®Æt.

4.3.1. BiÓu diÔn c©y b»ng danh s¸ch c¸c con cña mçi ®Ønh.

Ph-¬ng ph¸p th«ng dông ®Ó biÓu diÔn c©y lµ, víi mçi ®Ønh cña c©y ta

thµnh lËp mét danh s¸ch c¸c ®Ønh con cña nã theo thø tù tõ tr¸i sang ph¶i.

8

1. Cµi ®Æt bëi m¶ng.

Trong c¸ch cµi ®Æt nµy, ta sÏ sö dông mét m¶ng ®Ó l-u gi÷ c¸c ®Ønh cña

c©y. Mçi thµnh phÇn cña m¶ng lµ mét tÕ bµo chøa th«ng tin g¾n víi mçi ®Ønh

vµ danh s¸ch c¸c ®Ønh con cña nã. Danh s¸ch c¸c ®Ønh con cña mét ®Ønh cã

thÓ biÓu diÔn bëi m¶ng hoÆc bëi danh s¸ch liªn kÕt. Tuy nhiªn, v× sè con cña

mçi ®Ønh cã thÓ thay ®æi nhiÒu, cho nªn ta sÏ sö dông danh s¸ch liªn kÕt. Nh-

vËy mçi tÕ bµo m« t¶ ®Ønh cña c©y lµ mét b¶n ghi gåm hai tr-êng : tr-êng

infor chøa th«ng tin g¾n víi ®Ønh, tr-êng Child lµ con trá tíi danh s¸ch c¸c

con cña ®Ønh ®ã. Gi¶ sö c¸c ®Ønh cña c©y ®-îc ®¸nh sè tõ 1 ®Õn N víi c¸ch

cµi ®Æt nµy, ta cã thÓ khai b¸o cÊu tróc d÷ liÖu biÓu diÔn c©y nh- sau :

const N = ... ; { N lµ sè lín nhÊt c¸c ®Ønh mµ c©y cã thÓ cã }

type pointer = ^ Member :

Member = record

id : 1..N ;

next : pointer

end ;

Node = record

infor : item ;

child : pointer

end ;

Tree = array [1 ... N] of Node ;

Trong khai b¸o trªn, Member biÓu diÔn c¸c thµnh phÇn cña danh s¸ch

c¸c con, cßn Node biÓu diÔn c¸c ®Ønh cña c©y. Víi c¸ch cµi ®Æt nµy, cÊu tróc

d÷ liÖu biÓu diÔn c©y trong h×nh 4.4a ®-îc minh ho¹ trong h×nh 4.4b.

Ta cã nhËn xÐt r»ng, trong c¸ch cµi ®Æt nµy, víi mçi ®Ønh k ta x¸c ®Þnh

ngay con tr-ëng cña nã. Ch¼ng h¹n, víi c©y trong h×nh 4.4b, con tr-ëng cña

®Ønh 3 lµ ®Ønh 6, con tr-ëng cña ®Ønh 5 lµ 9, cßn ®Ønh 6 kh«ng cã con. PhÐp

to¸n t×m con tr-ëng EldestChild (k) cã thÓ ®-îc m« t¶ bëi hµm sau.

function

var P : pointer ;

begin

if T[k] < > nil then

begin

EldestChild ( k : 1 ...N ; T : Tree) : 0 ...N ;

9

P : = T[k]. child ;

EldestChild : = P^. id ;

end else EldestChild : = 0

end ;

Tuy nhiªn trong c¸ch cµi ®Æt nµy, viÖc t×m cha vµ em liÒn kÒ cña mçi

®Ønh l¹i kh«ng ®¬n gi¶n. Ch¼ng h¹n, ®Ó t×m cha cña ®Ønh k, ta ph¶i duyÖt c¸c

danh s¸ch c¸c con cña mçi ®Ønh. NÕu ph¸t hiÖn ra trong danh s¸ch c¸c con

cña ®Ønh m cã chøa k th× Parent (k) = m. Hµm Parent (k) ®-îc x¸c ®Þnh nh-

sau :

function

Parent (k : 1 ...N ; T : Tree) : 0 ...N ;

var P : pointer ;

i : 1 ... N ;

found : boolean ;

begin

i : = 1 ;

found : = false ;

while ( i < = N) and (not found) do

begin

P : = T[i].child ;

while (P < > nil) and (not found) do

if P^.id = k then

begin

Parent : = i :

found : = true ;

end else P : = P^.next ;

i: = i + 1

end ;

if not found then Parent : = 0 ;

end ;

Mét c¸ch t-¬ng tù (duyÖt c¸c danh s¸ch c¸c con), ta còng cã thÓ t×m

®-îc em liÒn kÒ cña mçi ®Ønh. M« t¶ chi tiÕt hµm NextSibling ®-îc ®Ó l¹i

xem nh- bµi tËp.

10

A 1

B 2

E 5

I 9

infor child

C 3

F 6 G 7

M 11

D 4

H 8

K 10

id

(a)

2

3

4

5

6

7

8

9

10

11

(b)

H×nh 4.4 CÊu tróc d÷ liÖu biÓu diÔn c©y

2. Cµi ®Æt bëi con trá.

NÕu kh«ng dïng m¶ng ®Ó l-u gi÷ c¸c ®Ønh cña c©y, ta cã thÓ sö dông

c¸c con trá trá tíi c¸c ®Ønh cña c©y. T¹i mçi ®Ønh, ta sÏ sö dông mét danh

s¸ch c¸c con trá trá tíi c¸c con cña nã, danh s¸ch nµy ®-îc cµi ®Æt bëi m¶ng

c¸c con trá. Mét con trá Root ®-îc sö dông ®Ó trá tíi gèc cña c©y. Ta cã thÓ

khai b¸o cÊu tróc d÷ liÖu biÓu diÔn c©y trong c¸ch cµi ®Æt nµy nh- sau.

const K = ..... ; {K lµ sè tèi ®a c¸c con cña mçi ®Ønh}

type pointer = ^Node ;

11

Note = record

infor : item ;

child : array [1...K] of pointer

end ;

var Root : pointer ;

Víi c¸ch cµi ®Æt nµy, cÊu tróc d÷ liÖu biÓu diÔn c©y trong h×nh 4.4a

®-îc minh ho¹ trong h×nh 4.5.

Root

H×nh 4.5 CÊu tróc d÷ liÖu biÓu diÔn c©y

Gi¶ sö P lµ mét con trá trá tíi mét ®Ønh nµo ®ã trong c©y, ta sÏ gäi ®Ønh

nµy lµ ®Ønh P. Sau ®©y ta sÏ xÐt xem c¸c phÐp to¸n t×m con tr-ëng cña nã

EldesChild (P), t×m cha cña nã Parent (P) vµ t×m em liÒn kÒ NexSibling (P)

®-îc thùc hiÖn nh- thÕ nµo. DÔ dµng thÊy r»ng, còng nh- trong c¸ch cµi ®Æt

bëi m¶ng, ta cã thÓ x¸c ®Þnh ®-îc ngay con tr-ëng cña mét ®Ønh. B¹n ®äc tù

viÕt lÊy hµm EldestChild. T- t-ëng cña thuËt to¸n t×m cha cña ®Ønh P còng

kh«ng cã g× kh¸c tr-íc, khi c©y cµi ®Æt bëi m¶ng, tøc lµ ta còng ph¶i duyÖt

c¸c ®Ønh con cña mçi ®Ønh. Song tr-íc kia, khi c¸c ®Ønh cña c©y ®-îc l-u

trong m¶ng, viÖc ®i lÇn l-ît qua c¸c ®Ønh cña c©y ®Ó xÐt c¸c con cña nã ®-îc

thùc hiÖn rÊt dÔ dµng. Cßn ë ®©y ta ph¶i sö dông mét hµng (Queue) H ®Ó l-u

c¸c ®Ønh ®· ®-îc xÐt. §Çu tiªn hµng chøa gèc Root cña c©y. T¹i mçi thêi

12

®iÓm ta sÏ lo¹i ®Ønh Q ë ®Çu hµng ra khái hµng vµ xÐt c¸c con cña nã. NÕu

mét trong c¸c ®Ønh con cña Q lµ P th× Parent (P) = Q, trong tr-êng hîp ng-îc

l¹i ta sÏ ®-a c¸c ®Ønh con cña Q vµo cuèi hµng. Hµm Parent ®-îc x¸c ®Þnh

nh- sau.

function Parent (P : pointer ; Root : pointer) : pointer ;

var Q, R : pointer ;

H : Queue ;

found : boolean ;

begin

Initialize (H) ; {khëi t¹o hµng rçng H}

Addqueue (Root, H) ; {§-a Root vµo hµng}

found : = false ;

while (not Emty (H) and (not found) do

begin

DeleteQueue (H, Q) ; {Lo¹i Q khái ®Çu hµng}

i : = 0 ;

repeat

i : = i + 1 ;

R : = Q^. child [i] ;

if R < > nil then

if R = P then

begin

Parent : = Q

found : = true

end else AddQueue (R, H)

until found or (R = nil) or (i = N)

end ;

if not found then Parent : = nil

end ;

Mét c¸ch hoµn toµn t-¬ng tù, ta cã thÓ viÕt ®-îc hµm t×m em liÒn kÒ

NextSibling.

13

4.3.2. BiÓu diÔn c©y b»ng con tr-ëng vµ em liÒn kÒ cña mçi ®Ønh.

Mét ph-¬ng ph¸p th«ng dông kh¸c ®Ó biÓu diÔn c©y lµ, víi mçi ®Ønh

cña c©y ta chØ ra con tr-ëng vµ em liÒn kÒ cña nã.

1. Cµi ®Æt bëi m¶ng.

Gi¶ sö c¸c ®Ønh cña c©y ®-îc ®¸nh sè tõ 1 ®Õn N. Dïng m¶ng ®Ó l-u

gi÷ c¸c ®Ønh cña c©y, mçi ®Ønh ®-îc biÓu diÔn bëi b¶n ghi gåm ba tr-êng,

ngoµi tr-êng infor, c¸c tr-êng EldestChild vµ Nexsibling sÏ l-u con tr-ëng vµ

em liÒn kÒ cña mçi ®Ønh. Ta cã thÓ khai b¸o nh- sau :

type Node = record

infor : item ;

EldestChild : 0...N ;

NextSibling : 0...N

end ;

Tree = array[1...N] of Node ;

H×nh 4.6 Minh ho¹ cÊu tróc d÷ liÖu biÓu diÔn c©y trong h×nh 4.4a.

Trong c¸ch biÓu diÔn nµy, EldestChild vµ NexSibling ®-îc ®-a vµo lµm

phÐp to¸n t×m cha cña mçi ®Ønh. Còng nh- tr-íc kia, ®Ó t×m cha cña mét ®Ønh

con cña nã, cho tíi khi t×m thÊy ®Ønh k. Cô thÓ ta cã thÓ m« t¶ hµm Parent(k)

nh- sau :

function Parent (k : 1 ... N ; T : Tree) : 0 ... N ;

var i, j : 0 ... N ;

found : boolean ;

begin

i : = 1 ;

found : = false ;

while (i <=N) and (not found) do

begin

j : = T[i]. EldestChild ;

if j = k then begin

Parent : = i ;

found : = true

end

14

else begin

j : = T[j]. NextSibling ;

while (j < > 0) and (not found) do

if j = k then begin

Parent : = i ;

found : = true

end

else j : = T[j].NextSibling ;

end ;

i : = i+1

end ;

if not found then Parent : = 0

end ;

infor

A

B

EldestChild NextSibling

1

2

4

0

3

C

6

0

4

D

E

0

5

9

0

6

F

0

7

H×nh 4.6

7

G

H

I

11

0

8

0

9

0

10

0

10

11

K

M

0

2. Cµi ®Æt bëi con trá.

Thay cho dïng m¶ng, ta cã thÓ sö dông c¸c con trá ®Ó cµi ®Æt. Khi ®ã

trong b¶n ghi Node, c¸c tr-êng EldestChild vµ NextSibling sÏ lµ c¸c con trá.

type pointer = ^Node ;

Node = record

15

infor : item ;

EldestChild : pointer ;

NextSibling : pointer ;

end ;

var Root : pointer ;

d÷ liÖu trong h×nh 4.7.

Root

§éc gi¶ h·y tù viÕt lÊy thñ tôc t×m cha cña ®Ønh P, Parent (P), trong ®ã

P lµ con trá, trong c¸ch cµi ®Æt nµy.

ph¶i ®-a vµo mçi thµnh phÇn cña m¶ng tr-êng infor m« t¶ th«ng tin ë mçi

16

const N = ... ;

type Node = record

infor : item ;

parent : 0 ...N ;

end ;

Tree = array [1...N] of Node ;

var T : Tree ;

infor

A

B

parent

1

2

0

1

2

3

5

3

C

4

D

E

5

6

F

7

G

H

I

8

9

10

11

K

M

ph©n.

nh- sau.

17

r

T₁

T₂

a)

b)

18

1 A

2 B

3 C

4 D 5 E

6 F

7 G

8 H 9 I 10 J

11 K

tr¸i vµ ®Ønh con ph¶i cña mçi ®Ønh.

th«ng tin g¾n víi mçi ®Ønh, truêng left chØ ®Ønh con tr¸i, tr-êng right chØ ®Ønh

const

type

max = N ;

Node = record

infor : Item ;

left : 0 ... max ;

right : 0 ... max

end ;

Tree = array [1... max] of Node ;

4.11.

19

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