Xem mẫu
- h a n g e Vi h a n g e Vi
XC XC
e e
F- F-
w w
PD
PD
er
er
!
!
W
W
O
O
N
N
y
y
bu
bu
to
to
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
k
k
lic
lic
C
C
w
w
m
m
w w
w
w
o
o
.c .c
.d o .d o
{ BinT_Type NewNode = BinT_Create_Node(NewData);
c u -tr a c k c u -tr a c k
if (NewNode == NULL)
return (NewNode);
if (BT_Tree == NULL)
BT_Tree = NewNode;
else
{ BinT_Type Rnode = BT_Tree;
while (Rnode->BinT_Right != NULL)
Rnode = Rnode->BinT_Right;
Rnode->BinT_Right = NewNode;
}
return (NewNode);
}
d. Duyeät qua caùc nuùt treân caây nhò phaân:
Trong thao taùc naøy chuùng ta tìm caùch duyeät qua (gheù thaêm) taát caû caùc nuùt trong caây
nhò phaân ñeå thöïc hieän moät thao taùc xöû lyù naøo ñoù ñoái vôùi nuùt naøy (Xem noäi dung
thaønh phaàn döõ lieäu chaúng haïn). Caên cöù vaøo thöù töï duyeät nuùt goác so vôùi 2 nuùt goác
caây con, thao taùc duyeät coù theå thöïc hieän theo moät trong ba thöù töï:
- Duyeät theo thöù töï nuùt goác tröôùc (Preorder):
Theo caùch duyeät naøy thì nuùt goác seõ ñöôïc duyeät tröôùc sau ñoù môùi duyeät ñeán hai caây
con. Caên cöù vaøo thöù töï duyeät hai caây con maø chuùng ta coù hai caùch duyeät theo thöù töï
nuùt goác tröôùc:
+ Duyeät nuùt goác, duyeät caây con traùi, duyeät caây con phaûi (Root – Left – Right)
+ Duyeät nuùt goác, duyeät caây con phaûi, duyeät caây con traùi (Root – Right - Left)
- Duyeät theo thöù töï nuùt goác giöõa (Inorder):
Theo caùch duyeät naøy thì chuùng ta duyeät moät trong hai caây con tröôùc roài ñeán duyeät
nuùt goác vaø sau ñoù môùi duyeät caây con coøn laïi. Caên cöù vaøo thöù töï duyeät hai caây con
chuùng ta cuõng seõ coù hai caùch duyeät theo thöù töï nuùt goác giöõa:
+ Duyeät caây con traùi, duyeät nuùt goác, duyeät caây con phaûi (Left – Root - Right)
+ Duyeät caây con phaûi, duyeät nuùt goác, duyeät caây con traùi (Right – Root - Left)
- Duyeät theo thöù töï nuùt goác sau (Postorder):
Töông töï nhö duyeät theo nuùt goác tröôùc, trong caùch duyeät naøy thì nuùt goác seõ ñöôïc
duyeät sau cuøng so vôùi duyeät hai nuùt goác caây con. Do vaäy, caên cöù vaøo thöù töï duyeät
hai caây con maø chuùng ta cuõng coù hai caùch duyeät theo thöù töï nuùt goác sau:
+ Duyeät caây con traùi, duyeät caây con phaûi, duyeät nuùt goác (Left – Right - Root)
+ Duyeät caây con phaûi, duyeät caây con traùi, duyeät nuùt goác (Right – Left - Root)
Trong phaàn naøy chuùng ta chæ trình baøy moät caùch duyeät theo moät thöù töï cuï theå ñoù laø:
Duyeät caây con traùi, duyeät nuùt goác vaø duyeät caây con phaûi (Left – Root – Right) vaø söû
duïng thuaät toaùn ñeä quy. Caùc caùch duyeät khaùc baèng thuaät toaùn ñeä quy hay khoâng ñeä
quy sinh vieân töï vaän duïng töông töï.
- Thuaät toaùn ñeä quy ñeå duyeät caây nhò phaân theo thöù töï Left – Root – Right (LRootR):
B1: CurNode = BinTree
Trang: 158
- h a n g e Vi h a n g e Vi
XC XC
e e
F- F-
w w
PD
PD
er
er
!
!
W
W
O
O
N
N
y
y
bu
bu
to
to
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
k
k
lic
lic
C
C
w
w
m
m
w w
w
w
o
o
.c .c
.d o .d o
B2: IF (CurNode = NULL)
c u -tr a c k c u -tr a c k
Thöïc hieän Bkt
B3: LRootR (BinTree->BinT_Left) // Duyeät caây con traùi
B4: Process (CurNode->Key) // Xöû lyù thoâng tin nuùt goác
B5: LRootR (BinTree->BinT_Right) // Duyeät caây con phaûi
Bkt: Keát thuùc
- Minh hoïa thuaät toaùn:
Giaû söû chuùng ta caàn duyeät qua caùc nuùt trong caây nhò phaân döôùi ñaây theo thöù töï
Left – Root – Right:
BinTree
40
36 55
12 18 45 21
NULL NULL NULL NULL 10 8 NULL NULL
NULL NULL 11 5
NULL NULL NULL NULL
LRootR(BinTree->BinT_Left)
LRootR(BinTree->BinT_Left->BinT_Left)
LRootR(NULL)
Process(12)
LRootR(NULL)
Process(36)
LRootR(BinTree->BinT_Left->BinT_Right)
LRootR(NULL)
Process(18)
LRootR(NULL)
Process(40)
LRootR(BinTree->BinT_Right)
LRootR(BinTree->BinT_Right->BinT_Left)
LRootR(BinTree->BinT_Right->BinT_Left->BinT_Left)
LRootR(NULL)
Process(10)
LRootR(NULL)
Trang: 159
- h a n g e Vi h a n g e Vi
XC XC
e e
F- F-
w w
PD
PD
er
er
!
!
W
W
O
O
N
N
y
y
bu
bu
to
to
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
k
k
lic
lic
C
C
w
w
m
m
w w
w
w
o
o
.c .c
.d o .d o
Process(45)
c u -tr a c k c u -tr a c k
LRootR(BinTree->BinT_Right->BinT_Left->BinT_Right)
LRootR(BinTree->BinT_Right->BinT_Left->BinT_Right->BinT_Left)
LRootR(NULL)
Process(11)
LRootR(NULL)
Process(8)
LRootR(BinTree->BinT_Right->BinT_Left->BinT_Right->BinT_Right)
LRootR(NULL)
Process(5)
LRootR(NULL)
Process(55)
LRootR(BinTree->BinT_Right->BinT_Right)
LRootR(NULL)
Process(21)
LRootR(NULL)
Nhö vaäy thöù töï caùc thoâng tin cuûa caùc nuùt ñöôïc xöû lyù nhö sau:
12 -> 36 -> 18 -> 40 -> 10 -> 45 -> 11 -> 8 -> 5 -> 55 -> 21
- Caøi ñaët thuaät toaùn:
Haøm BinT_LRootR_Travelling coù prototype:
void BinT_LRootR_Travelling(BinT_Type BT_Tree);
Haøm thöïc hieän thao taùc duyeät qua taát caû caùc nuùt trong caây nhò phaân BT_Tree theo
thöù töï duyeät Left – Root – Right ñeå xöû lyù thoâng tin ôû moãi nuùt.
void BinT_LRootR_Travelling(BinT_Type BT_Tree)
{ if (BT_Tree == NULL)
return;
BinT_LRootR_Travelling (BT_Tree->BinT_Left);
Process (BT_Tree->Key)
BinT_LRootR_Travelling (BT_Tree->BinT_Right);
return;
}
Löu yù:
Haøm Process thöïc hieän vieäc xöû lyù thoâng tin (Key) cuûa moãi nuùt. Do vaäy tuøy töøng
tröôøng hôïp cuï theå maø chuùng ta vieát haøm cho phuø hôïp. Chaúng haïn ñeå xuaát thoâng
tin thì chæ caàn caùc leänh xuaát döõ lieäu ñeå xuaát thaønh phaàn Key.
e. Tính chieàu cao cuûa caây:
Ñeå tính chieàu cao cuûa caây (TH) chuùng ta phaûi tính chieàu cao cuûa caùc caây con, khi ñoù
chieàu cao cuûa caây chính laø chieàu cao lôùn nhaát cuûa caùc caây con coäng theâm 1 (chieàu
cao nuùt goác). Nhö vaäy thao taùc tính chieàu cao cuûa caây laø thao taùc tính ñeä quy chieàu
cao cuûa caùc caây con (chieàu cao cuûa caây con coù goác laø nuùt laù baèng 1).
- Thuaät toaùn:
Trang: 160
- h a n g e Vi h a n g e Vi
XC XC
e e
F- F-
w w
PD
PD
er
er
!
!
W
W
O
O
N
N
y
y
bu
bu
to
to
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
k
k
lic
lic
C
C
w
w
m
m
w w
w
w
o
o
.c .c
.d o .d o
B1: IF (BinTree = NULL)
c u -tr a c k c u -tr a c k
B1.1: TH = 0
B1.2: Thöïc hieän Bkt
B2: THL = TH(BinTree->BinT_Left)
B3: THR = TH(BinTree->BinT_Right)
B4: IF (THL > THR)
TH = THL + 1
B5: ELSE
TH = THR + 1
Bkt: Keát thuùc
Ví duï: Chieàu cao cuûa caây nhò phaân sau baèng 4.
BinTree
40
36 55
2 4
12 18 3 45 21
1 1 2 1
0 NULL 0 NULL 0 NULL 0 NULL 0 NULL 8 0 NULL 0 NULL
1
0 NULL 0 NULL
- Caøi ñaët thuaät toaùn:
Haøm BinT_Height coù prototype:
int BinT_Height(BinT_Type BTree);
Haøm tính chieàu cao cuûa caây BTree theo thuaät toaùn ñeä quy. Haøm traû veà chieàu cao
cuûa caây caàn tính.
int BinT_Height(BinT_Type BTree)
{ if (BTree == NULL)
return (0);
int HTL = BinT_Height(BTree->BinT_Left);
int HTR = BinT_Height(BTree->BinT_Right);
if (HTL > HTR)
return (HTL+1);
return (HTR+1);
}
f. Tính soá nuùt cuûa caây:
Töông töï nhö tính chieàu cao cuûa caây, soá nuùt cuûa caây (NN) baèng toång soá nuùt cuûa hai
caây con coäng theâm 1. Do vaäy thao taùc naøy chuùng ta cuõng seõ tính ñeä quy soá nuùt cuûa
caùc caây con (soá nuùt cuûa caây con coù goác laø nuùt laù baèng 1).
Trang: 161
- h a n g e Vi h a n g e Vi
XC XC
e e
F- F-
w w
PD
PD
er
er
!
!
W
W
O
O
N
N
y
y
bu
bu
to
to
Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät
k
k
lic
lic
C
C
w
w
m
m
w w
w
w
o
o
.c .c
.d o .d o
- Thuaät toaùn:
c u -tr a c k c u -tr a c k
B1: IF (BinTree = NULL)
B1.1: NN = 0
B1.2: Thöïc hieän Bkt
B2: NNL = NN(BinTree->BinT_Left)
B3: NNR = NN(BinTree->BinT_Right)
B4: NN = NNL + NNR + 1
Bkt: Keát thuùc
Ví duï: Soá nuùt cuûa caây nhò phaân sau baèng 8.
BinTree
40
36 55
12 18 45 21
NULL NULL NULL NULL NULL 8 NULL NULL
0 0 0 0 0 0 0
1(0+0+1) 1 (0+0+1) NULL NULL 1 (0+0+1)
3 (1+1+1) 0 0
1 (0+0+1)
2 (0+1+1)
4 (2+1+1)
8 (3+4+1)
- Caøi ñaët thuaät toaùn:
Haøm BinT_Num_Node coù prototype:
int BinT_Num_Node(BinT_Type BTree);
Haøm tính soá nuùt cuûa caây BTree theo thuaät toaùn ñeä quy. Haøm traû veà soá nuùt cuûa caây
caàn tính.
int BinT_Num_Node(BinT_Type BTree)
{ if (BTree == NULL)
return (0);
int NNL = BinT_Num_Node(BTree->BinT_Left);
int NNR = BinT_Num_Node(BTree->BinT_Right);
return (NNL + NNR + 1);
}
g. Huûy moät nuùt treân caây nhò phaân:
Vieäc huûy moät nuùt trong caây coù theå laøm cho caây trôû thaønh röøng. Do vaäy trong thao taùc
naøy neáu chuùng ta tieán haønh huûy moät nuùt laù thì khoâng coù ñieàu gì xaûy ra, song neáu huûy
Trang: 162
nguon tai.lieu . vn
