›
›

Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Cây và các bài toán trên cây - Võ Minh Phổ

Download
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
CH¦¥NG 4. C©y vµ c¸c bµi to¸n trªn c©y.  
$1. Mét sè kh¸i niÖm vÒ c©y.  
1.1. C©y vµ bËc cña c©y.  
a. §inh nghÜa. C©y lµ mét tËp hîp T rçng hoÆc gåm nhiÒu phÇn tö gäi lµ nót  
(node), trong ®ã:  
- Mét nót ®-îc gäi lµ nót gèc (root)  
- C¸c nót cßn l¹i ph©n chia thµnh m nhãm(m>=0), mçi  
nhãm lµ mét c©y vµ ®-îc gäi lµ c©y con (subtree).  
Nót lµ mét phÇn tö cña danh s¸ch vµ cã thÓ cã kiÓu bÊt k×. C¸c nót ®-îc biÓu  
diÔn bëi mét kÝ tù ch÷, mét chuçi, mét sè ghi trong mét vßng trßn. C©y kh«ng  
cã nót nµo c¶ gäi lµ c©y rçng (nulltree)  
b. BËc cña nót vµ bËc cña c©y(degree). BËc cña nót lµ sè c©y con cña nót ®ã.  
BËc cña c©y lµ bËc lín nhÊt cña c¸c nót cña c©y. NÕu c©y cã bËc n th× ta gäi c©y  
n-ph©n.  
VÝ dô. Víi c©y  
A
B
D
C
G
E
F
H
K
L
BËc cña nót A lµ 3, cña nót B lµ 0, cña nót D lµ 2  
BËc cña c©y lµ 3 -> C©y tam ph©n.  
c. Nót kÕt thóc vµ nót trung gian.  
Nót kÕt thóc ( hoÆc nót l¸ - leaf) lµ nót cã bËc b»ng 0.  
Nót trung gian (interior node) lµ nót cã bËc kh¸c 0 vµ kh«ng ph¶i nót gèc.  
73  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
VÝ dô : C¸c nót l¸ lµ B,G,H,K,L,F  
C¸c nót trung gian lµ C,E,D  
1.2. Møc cña nót (level)vµ chiÒu cao cña c©y(depth, height):  
a. Møc cña nót.  
- Møc cña gèc b»ng 1  
- Møc cña nót kh¸c gèc b»ng møc cña nót gèc cña c©y con nhá nhÊt chøa nã  
céng víi 1.  
ChiÒu cao cña c©y lµ møc lín nhÊt cña nót l¸.  
VÝ dô :  
C¸c nót B,C,D co møc 2  
C¸c nót G,E,F cã møc lµ 3  
ChiÒu cao cña c©y lµ 4  
b. Nót tr-íc vµ nót sau.  
Nót y ®-îc gäi lµ nót tr-íc cña nót x nÕu c©y con cã gèc lµ y chøa x, vµ khi ®ã  
nót x gäi lµ nót sau cña nót y.  
VÝ dô.  
Nót D lµ nót tr-íc cña nót H vµ nót H lµ nót sau cña nót D.  
c. Nót cha (ancestor) vµ nót con (descendant).  
NÕu y lµ nót tr-íc cña nót x vµ møc cña x b»ng møc cña nót y c«ng 1, th× y  
®-îc gäi lµ nót cha cña nót x vµ nót x ®-îc gäi lµ nót con cña nót y.  
VÝ dô.  
Nót E lµ nót cha cña nót H vµ nót H lµ nót con cña nót E.  
Nót D kh«ng ph¶i lµ nót cha cña nót H  
1.3. C©y cã thø tù(ordered tree) vµ rõng.  
a. C©y cã thø tù. Mét c©y ®-îc gäi lµ cã thø tù nÕu ta thay ®æi vÞ trÝ cña c¸c  
c©y con th× sÏ cã mét c©y míi.  
VÝ dô.  
74  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
A
A
B
E
B
E
C
D
D
C
b. Rõng (forest).  
NÕu cã mét tËp h÷u h¹n c¸c c©y ph©n biÖt th× ta gäi ®ã lµ rõng. Nh- vËy nÕu  
mét c©y bÞ lo¹i bá nót gèc cã thÓ cho ta mét rõng.  
1.4. Ph-¬ng ph¸p biÓu diÔn c©y.  
Cã thÓ biÓu diÔn c©y b»ng nhiÒu ph-¬ng ph¸p ë ®ay ta chØ h¹n chÕ trong mét  
sè ph-¬ng ph¸p c¬ b¶n sau:  
a. BiÓu diÔn c©y b»ng ®å thÞ.  
- Mçi nót lµ mét ®Ønh  
- C¹nh øng víi 2 nót ®-îc nèi thµnh ®o¹n th¼ng.  
b. BiÓu diÔn c©y b»ng gi¶n ®å.  
c. C¸ch chøa c©y trong bé nhí.  
Ta cã thÓ chøa c©y trong bé nhí b»ng c¸ch sö dông danh s¸ch liªn kÕt, mçi  
®Ønh t-¬ng øng víi mét nót.  
- ¸p dông cho c©y nhÞ ph©n:  
Mét nót gåm cã:  
Left INFO right  
Tr-êng INFO øng víi th«ng tin (d÷ liÖu) cña nót  
- Tr-êng left øng víi con trá, trá tíi c©y con tr¸i cña nót ®ã.  
- Tr-êng right øng víi con trá, trá tíi c©y con ph¶i cña nót ®ã.  
VÝ dô c©y nhÞ ph©n ta biÓu diÔn b»ng danh s¸ch liªn kÕt nh- sau:  
75  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
A
C
D
L
E
F
G
H
Root  
A
C
x
D
x
G
x
E
x
F
x
x
H
x
x
L
x
Trong ®ã ký hiÖu x ë c¸c liªn kÕt lªn r»ng liªn kÕt chØ ra nil  
- ¸p dông c©y n- ph©n , ta cã thÓ sö dông liªn kÕt sau  
info Link1 Link2  
Linkn  
…
Ph-¬ng ph¸p m« t¶ vµ chøa c©y n- ph©n b»ng danh s¸ch liªn kÕt chØ cã lîi khi  
hÇu hÕt c¸c nót cña c©y cã bËc n, tøc lµ c¸c vïng liªn kÕt cña c¸c nót ®Òu ®-îc  
sö dông. Nh-ng nÕu trong c©y cã nhiÒu nót cã bËc nhá h¬n n th× khi ®ã ta sÏ  
l·ng phÝ bé nhí v× cã nhiÒu vïng liªn kÕt kh«ng ®-îc sö dông.  
Ta còng cã thÓ m« t¶ vµ chøa c©y n- ph©n b»ng c¸ch dïng c©y nhÞ ph©n vµ  
chøa trong bé nhí. ViÖc m« t¶ theo quy -íc:  
- C¸c cã cïng nót cha (c¸c nót anh em ) sÏ ë trªn cïng ®-êng ngang.  
- C¸c nót con ë ®-êng phÝa d-íi.  
Khi ®ã ®èi víi mét nót th× liªn kÕt tr¸i chØ ®Õn mét nót con (mòi tªn th¼ng  
®øng) vµ liªn kÕt ph¶i chØ ®Õn mét nót anh em cã cïng nót cha(mòi tªn ngang).  
76  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
A
B
C
G
D
E
F
H
K
L
C©y nhÞ ph©n lµ c©y c¬ b¶n vµ ®-îc øng dông nhiÒu, khai b¸o c©y nhÞ ph©n nh-  
sau:  
d. Tæ chøc c©y. Ta khai b¸o  
Type  
Infor = integer;  
Ref = ^node;  
Node = record  
Info: infor ;(*néi dung cña nót*)  
Left, right: ref;  
End;  
Var  
Root: ref;  
d. Khëi t¹o c©y (c©y rçng).  
Procedure InnitializeT;  
Begin  
Root:=nil;  
End;  
1.4. C¸c phÐp duyÖt c©y.  
a. DuyÖt tiÒn thø tù (NLR, NRL)  
- NÕu c©y chØ cã nót gèc, duyÖt gèc lµ duyÖt tiÒn thø tù.  
- Gäi r lµ gèc T1,T2,…,Tk lµ c¸c c©y con øng víi gèc theo thø tù tõ tr¸i sang  
ph¶I (ph¶i sang tr¸i). Khi ®ã duyÖt tiÒn thø tù lµ c¸ch duyÖt sau:  
77  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
+ DuyÖt gèc r  
+ DuyÖt T1 theo tiÒn thø tù  
+ DuyÖt T2 theo tiÒn thø tù  
…
+ DuyÖt Tk theo tiÒn thø tù  
A
B
H
C
K
F
L
D
E
ABCDEFHKL lµ duyÖt tiÒn thø tù NLR  
AHLKBDFEC lµ duyÖt tiÒn thø tù NRL  
b. DuyÖt trung thø tù (LNR, RNL)  
- NÕu c©y chØ cã gèc th× duyÖt gèc theo trung thø tù.  
- Gäi r lµ gèc T1,T2,…,Tk lµ c¸c c©y con øng víi gèc theo thø tù tõ tr¸i sang  
ph¶i (ph¶i sang tr¸i). Khi ®ã duyÖt trung thø tù lµ c¸ch duyÖt sau:  
+ DuyÖt T1 theo trung thø thù  
+ DuyÖt gèc r  
+ DuyÖt T2, T3,…, Tk theo trung thø tù  
CBEDFAKHL lµ duyÖt trung thø tù LNR  
LHKAFDEBC lµ duyÖt trung thø tù RNL  
c. DuyÖt hËu thø tù (LRN, RLN).  
- NÕu c©y chØ cã gèc lµ r th× duyÖt r lµ duyÖt hËu thø tù  
- Gäi r lµ gèc T1,T2,…,Tk lµ c¸c c©y con øng víi gèc theo thø tù tõ tr¸i sang  
ph¶i (ph¶i sang tr¸i). Khi ®ã duyÖt hËu thø tù lµ c¸ch duyÖt sau:  
+ DuyÖt T1 theo hËu thø tù  
78  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
+ DuyÖt T2 theo hËu thø tù  
…
+ DuyÖt Tk theo hËu thø tù  
+ Cuèi cïng duyÖt r.  
CEFDBKLHA lµ duyÖt hËu thø tù LRN  
LKHFEDCBA lµ duyÖt hËu thø tù RLN  
$2. DuyÖt c©y nhÞ ph©n theo thø tù NLR  
2.1. Dïng ph-¬ng ph¸p ®Ö quy vµ dïng Stack.  
a. Dïng ®Ö quy.  
Procedure Traverse_NLR (p: ref);  
Begin  
If p <>nil then  
Begin  
Writeln (p^.info);  
Traverse_NLR (p^.left);  
Traverse_NLR (p^.right);  
End;  
End;  
Gäi thñ tôc lµ:  
Traverse_NLR(root);  
b. Dïng stack  
Khi ®i theo nh¸nh tr¸i, ta l-u gi÷ c¸c nót con bªn ph¶i vµo stack ®Ó sau cã thÓ  
trë l¹i nót nµy.  
Thªm biÕn :  
+ stack: array [1.. stackno] of ref;  
+ cont kiÓu boolean cho gi¸ trÞ false khi stack rçng.  
Procedure traverse_NLR;  
Var  
Cont: boolean;  
79  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
P : ref;  
Stack : array[1.. stackno]of ref;  
Sp : 0.. stackno;  
Begin  
P := root;  
Sp := 0;  
Cont := true;  
While p<>nil and cont do  
Begin  
Writeln(p^.info);  
If P^.right<>nil then  
Begin  
Sp:= sp+1;  
Stack[sp]:= p^.right;  
End;  
If p^left<>nil then  
P:= p^.left  
else  
if sp =0 then  
cont:= false;  
else  
begin  
p:= stack[sp];  
sp:= sp -1;  
end;  
end;  
end;  
c. Ph-¬ng ph¸p ®æi ng-îc vïng liªn kÕt.  
80  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
C¸ch nµy kh«ng th«ng dông v× cÊu tróc c©y sÏ bÞ ph¸ huû hoµn toµn sau khi  
duyÖt xong do khi ®i xuèng nót con ta ®æi ng-îc vïng liªn kÕt chØ lªn nót cha  
®Ó trë vÒ ®-îc dÔ dµng.  
2.2. C©y liªn kÕt vßng  
a. C©y liªn kÕt vßng.  
- Khi tæ chøc c©y lµ mét danh s¸ch liªn kÕt, cã nh÷ng nót vïng liªn kÕt chØ vµo  
nil. Ta cho c¸c vïng liªn kÕt nµy chØ ®Õn nh÷ng nót ®øng sau nã theo phÐp  
duyÖt nh»m lµm cho phÐp duyÖt dÔ dµng vµ nhanh h¬n. C©y cã cÊu tróc nµy gäi  
lµ c©y liªn kÕt vßng  
- Sö dông thªm c¸c liªn kÕt gi¶ gäi lµ liªn kÕt vßng, chØ ®Õn nót ®øng sau theo  
phÐp duyÖt, ta g¸n mét gi¸ trÞ ©m cho vïng liªn kÕt gi¶.  
- Ta kÝ hiÖu:  
*p – nót tr-íc nót p theo phÐp duyÖt  
p* - nót sau nót p theo phÐp duyÖt  
*(p*) = p  
- Ta tæ chøc c©y liªn kÕt vßng theo quy t¾c sau:  
+ NÕu vïng liªn kÕt left lµ nil th× vïng nµy sÏ chØ vµo nót ®øng tr-íc  
nã theo phÐp duyÖt.  
+ NÕu vïng liªn kÕt right lµ nil th× vïng nµy sÏ chØ vµo nót ®øng sau  
theo phÐp duyÖt, do ®ã c©y liªn kÕt vßng ®-îc t¹o tõ c©y kh«ng liªn kÕt vßng  
theo quy t¾c sau:  
C©y kh«ng liªn kÕt vßng:  
P^.left = q  
P^.right =q  
C©y liªn kÕt vßng  
P^.left = q  
P^.right = q  
P^.left =nil  
P^.right =nil  
P^left = -(*p)  
P^.right = -(p*)  
81  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
head  
root  
A
B
H
D
C
K
L
E
F
- Mét nót cña c©y liªn kÕt vßng ph¶i cã thªm hai vïng Ltype cña liªn kÕt tr¸i  
vµ Rtype cña liªn kÕt ph¶i ®Ó ph©n biÖt liªn kÕt thËt hay liªn kÕt gi¶.  
b. Khai b¸o c©y liªn kÕt vßng.  
Type  
Infor = integer;  
Ref = ^node;  
Node=record  
Info : infor;  
Left, Right : ref;  
Ltype, Rtype : boolean;  
End;  
- NÕu Ltype (Rtype) cã gi¸ trÞ true th× liªn kÕt left(right) lµ liªn kÕt thËt.  
- NÕu Ltype(Rtype) cã gi¸ trÞ false th× liªn kÕt left(right) lµ liªn kÕt gi¶.  
2.3. C¸c phÐp to¸n trªn c©y liªn kÕt vßng NLR:  
a. T¹o c©y liªn kÕt vßng NLR tõ c©y kh«ng liªn kÕt vßng:  
T¹i nót p cña c©y nÕu:  
82  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
+P^.left = nil ta cho liªn kÕt gi¶ chØ ®Õn nót ®øng tr-íc theo phÐp  
duyÖt.  
+P^.right = nil ta cho liªn kÕt gi¶ chØ ®Õn nót ®øng sau theo phÐp duyÖt.  
Sau khi t¹o c©y liªn kÕt vßng ta b¾t ®Çu duyÖt head (lµ nót mµ liªn kÕt tr¸i chØ  
vµo gèc, liªn kÕt ph¶i chØ vµo chÝnh nã ). Trong gi¶i thuËt d-íi ®©y tr-íc tiªn ta  
ph¶i ®-a head vµo Stack ®Ó cho vïng liªn kÕt right cña nót cuèi cïng theo phÐp  
duyÖt chØ ®Õn head. Khai b¸o bæ sung thªm biÕn head  
Var  
Head : ref;  
Gäi q lµ nót ®øng tr-íc nót p theo phÐp duyÖt(NLR). L-u ý c¸c tr-êng hîp:  
TH1. Nót p kh«ng cã nót con bªn tr¸i. Ta cho liªn kÕt gi¶ left cña nót p  
chØ ®Õn nót q  
q
q
1
p
p
TH2. Nót p lµ nót l¸. Ta cho liªn kÕt gi¶ right cña nót p chØ ®Õn nót p*  
(nót x)  
q
q
p
x
p
X
TH3. Nót p cã nót con bªn tr¸i vµ kh«ng cã nót con bªn ph¶i. Cho liªn  
kÕt gi¶ right cña nót p chØ ®Õn nót con bªn tr¸i cña nót p  
p
p
83  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
3
TH4. NÕu c©y rçng ta cho liªn kÕt gi¶ left cña head chØ ®Õn hed  
Gäi q lµ nót ®øng tr-íc p, x lµ nót ®øng sau p theo phÐp duyÖt. Gi¶i thuËt ®-îc  
m« t¶ nh- sau:  
Procedure Intialize_NLR  
Var  
Sp: 0.. stackno; { Stack pointer}  
Stack:= array[1..stackno] of ref;  
p, q, x: ref;  
Begin  
New(head)  
p:= root;  
Head^.right:=head;Head^.Rtype:= false; {5}  
q:=head;  
if p>nil then {c©y kh¸c rçng}  
begin  
head^.left:= root;  
head^.Ltype:= true;{®-a head vµo stack}  
sp:= 1;  
stack[sp]:= head;  
repeat  
if p^.left = nil then  
begin{p kh«ng cã nót con tr¸i}  
p^.left := q;  
p^.Ltype:= false; {1}  
q:= p;  
84  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
if p^.right = nil then{p lµ nót l¸}  
{LÊy ra tõ stack}  
begin  
x:= stack[sp];  
sp:= sp-1;  
p^right:= x; {2}  
p^Rtype:= false;  
p:=x;  
end  
else {®Õn nót con bªn ph¶I cña p}  
begin  
p^.rtype:= true;  
p:= p^.right;  
end;  
end  
else  
begin {p cã nót con bªn tr¸i }  
p^.ltype:= true;  
q:= p;  
if p^.right = nil then  
begin  
{p kh«ng cã nót con bªn ph¶i }  
p^.right:= p^.left;  
p^.Rtype:= false; {3}  
end  
else  
begin  
{p cã nót con bªn ph¶I, ®-a nót con  
vµo Stack }  
85  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
p^.Rtype:= true;  
sp:= sp + 1;  
stack[sp]:= p^.right;  
end;  
p:= p^.left; {®Õn nót con bªn tr¸i }  
end;  
until p = head;  
end  
else  
begin {c©y rçng}  
head^..left:= head;  
head^.Ltype:= false;{4}  
end;  
end;  
A
B
H
C
K
F
L
D
E
86  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
SB  
1
Q
P
P^.L P^.R P^.L:= P^.R:= P^.LT:= P^.RT:= Q:= P:= STACK  
Head  
head  
A
A
B
C
D
E
F
B
H
true  
true  
A
B
C
D
E
F
B
C
D
E
F
H,head  
D,H,head  
H,head  
F,H,head  
H,head  
Head  
2
3
4
5
6
7
8
9
A
B
C
D
E
F
C
D
True  
False  
true  
true  
Nil  
E
Nil  
F
B
D
false  
true  
E
D
E
K
H
K
F
Nil  
Nil  
K
nil  
nil  
L
F
false  
false  
true  
false  
false  
true  
H
H
K
L
H
K
L
L
H
K
L,head  
H
K
Nil  
Nil  
nil  
nil  
L
false  
false  
false  
false  
Head  
head  
Stack Rçng  
b. DuyÖt c©y liªn kÕt vßng NLR: Ta cã nhËn xÐt sau:  
- Trong c©y liªn kÕt vßng NLR, liªn kÕt ph¶i right (thËt hay gi¶) cña mét nót  
bao giê còng chØ ®Õn nót ®øng sau nã theo phÐp duyÖt. Do ®ã ta cã gi¶i thuËt  
duyÖt NLR nh- sau:  
+ NÕu nót p cã nót con bªn tr¸i (liªn kÕt tr¸i left lµ thËt) th× ta ®i ®Õn nót con.  
+ NÕu nót p kh«ng con bªn tr¸i th× ta ®i ®Õn nót p* (liªn kÕt right lµ thËt hay  
gi¶).  
- Gi¶i thuËt:  
Procedure traverse_LNR;  
Var  
P : ref;  
Begin  
P:= head^.left;  
While p<> head do  
Begin  
Write(p^.info);  
If p^.Ltype then { liªn kÕt left th©t-®Õn nót con bªn tr¸I  
nót p}  
P:= p^.left  
Else { liªn kÕt right thËt hay gi¶- ®Õn nót p*}  
P:= p^.right;  
End;  
87  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
End;  
c. T¹o c©y liªn kÕt vßng NLR  
Khi t¹o c©y kiªn kÕt vßng NLR cho liªn kÕt gi¶ right, left cña head chØ ®Õn  
head.  
procedure initialize_NLR;  
begin  
new(head);  
with head^ do  
begin  
left:= head;  
Ltype:= false;  
Right:= head;  
Rtype:= false;  
End;  
End;  
d. Thªm mét nót vµo c©y liªn kÕt vßng NLR:  
d1. Thªm mét nót vµo bªn tr¸i nót q.  
- Gäi p lµ nót cÇn thªm vµo c©y. XÐt c¸c tr-êng hîp:  
1/. Nót q cã nót con bªn tr¸i.  
Gäi q1 lµ nót con bªn tr¸i cña nót q (q1:= q^.left). Ta cho:  
+ Liªn kÕt thËt left cña nót p chØ ®Õn nót q1 {1}  
p^.left:=q1; p^.Ltype:=true;  
+ Liªn kÕt gi¶ right cña nót p chØ ®Õn nót q1 {2}  
p^.left:=q1; p^.Rtype:=false;  
+ Liªn kÕt thËt left cña nót q chØ ®Õn nót p {3}  
q^.left:=p; q^.ltype:=true;  
q
q
3
p
q1  
88  
Vâ Minh PBé m«n KHMT - HVKTQS  
q1  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
1
2
C¸c tr-êng hîp cã thÓ:  
+ TH1: Nót q kh«ng cã nót con bªn ph¶i.  
Ta cho liªn kÕt gi¶ right cña nót q chØ ®Õn nót p {4}.  
q^.right:=p; q^.Rtype: false  
q
q
4
p
q1  
q1  
+ TH2. Nót q1 kh«ng cã nót con bªn tr¸i.  
Ta cho liªn kÕt gi¶ left cña nót q1 chØ ®Õn nót p {5}.  
q1^.left:=p; q1^.Ltype:=false;  
q
q
p
q1  
5
q1  
+ Gi¶i thuËt:  
Procedure Insert_left_NLR(q: ref; Newinfo: infor );  
Var  
p, q1: ref;  
Begin  
New(p);  
q1: = q^.left;  
89  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
with p^ do  
begin  
info:= newinfo;  
left:= q1; Ltype:= true;  
right:=q1; Rtype:= false; {2}  
end;  
q^.left:= p;  
{1}  
{3}  
if not q^.Rtype then q^.right:= p; {4}  
if not q1^.Ltype then q1^.left:= p; {5}  
end;  
2/. Nót q kh«ng cã nót con bªn tr¸i.  
+ Cho liªn kÕt thËt left cña nót q chØ ®Õn nót p{6}  
q^.left:=p; q^.Ltype:=true;  
q
q
7
6
p
+ Liªn kÕt gi¶ left cña nót p chØ ®Õn nót q{7}  
p^.left:=q; p^.Ltype:=false;  
+ Liªn kÕt gi¶ right cña nót p chØ ®Õn nót q*{8}  
p^.right:=q*; p^.Rtype:=false;  
q
q
p
8
90  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
C¸c tr-êng hîp x¶y ra lµ :  
TH1. Nót q kh«ng cã nót con bªn ph¶i.  
- Cho liªn kÕt gi¶ right cña nót q chØ ®Õn nót p {9}.  
q^.right:=p; q^.Rtype:=false;  
q
q
9
p
q*  
8
q*  
TH2. Nót q* kh«ng cã nót con bªn tr¸i.  
- Cho liªn kÕt gi¶ left cña nót q* chØ ®Õn nót p{10}.  
q*^.left:=p; q*^.Ltype:=false;  
q
q
q*  
q*  
p
10  
Gi¶i thuËt:  
Procedure Insert_left_NLR2(q: ref; Newwinfo: Infor);  
Var  
P, q1: ref;  
Begin  
New(p);  
q^.left:= p; q^.Ltype:= true;  
with p^ do  
{6}  
begin  
info:= Newinfor;  
left:= q; Ltype:= false;  
right:= q^.right; Rtype:= false;  
end;  
{7}  
{8}  
91  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
C¸c bµi gi¶ng CÊu tróc d÷ liÖu vµ Gi¶i thuËt  
q1:= p^.right;  
if not q^.Rtype then q^.Right:= p;  
if not q1^.Ltype then q1^.left:= p;  
end;  
{9}  
{10}  
Ta cã thÓ viÕt l¹i mét c¸ch ®Çy ®ñ tÊt c¶ c¸c tr-êng hîp nh- sau:  
Procedure Insert_left_NLR(q: ref; Newwinfo: Infor);  
Var  
P,q1: ref;  
Begin  
New(p);  
P^.info:=Newinfo;  
If q^.Ltype then {q cã nót con tr¸i}  
Begin  
q1:=q^.left;  
with p^ do  
begin  
left:= q1; Ltype:= true;  
right:= q1; Rtype:= false;  
{1}  
{2}  
end;  
if not q1^.Ltype then q1.^left:=p;  
end  
{5}  
else  
begin { q kh«ng cã nót con bªn tr¸i}  
with p^ do  
begin  
left:= q; Ltype:= false;  
right:= q^.right; Rtype:= false;  
end;  
{7}  
{8}  
q1:=p^.Right;  
92  
Vâ Minh Phæ – Bé m«n KHMT - HVKTQS  
Tải về để xem bản đầy đủ
doc 47 trang baolam 20960 Free
Download
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và giải thuật - Chương 4: Cây và các bài toán trên cây - Võ Minh Phổ", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

  • docbai_giang_cau_truc_du_lieu_va_giai_thuat_chuong_4_cay_va_cac.doc