- Trang Chủ
- Cơ sở dữ liệu
- Giáo trình hướng dẫn dùng thuật toán thêm một nút vào bên trái nhất của cây nhị phân p4
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
c u -tr a c k c u -tr a c k
CurNode->Key < SearchData // Tìm kieám treân caây con phaûi
⇒ CurNode = CurNode->BST_Right
BSTree
60
25 CurNode 65
19 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL 50
15
NULL NULL NULL NULL
CurNode->Key > SearchData // Tìm kieám treân caây con traùi
⇒ CurNode = CurNode->BST_Left
BSTree
60
25 65
19 CurNode 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL 50
15
NULL NULL NULL NULL
CurNode->Key < SearchData // Tìm kieám treân caây con phaûi
⇒ CurNode = CurNode->BST_Right
Trang: 168
- 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
BSTree
c u -tr a c k c u -tr a c k
60
25 65
19 40 NULL NULL
10 NULL 30 CurNode 44
NULL NULL NULL NULL 50
15
NULL NULL NULL NULL
CurNode = NULL ⇒ Thuaät toaùn keát thuùc (Khoâng tìm thaáy)
- Caøi ñaët thuaät toaùn:
Haøm BST_Searching coù prototype:
BST_Type BST_Searching(BST_Type BS_Tree, T SearchData);
Haøm thöïc hieän thao taùc tìm kieám treân caây nhò phaân tìm kieám BS_Tree nuùt coù
thaønh phaàn Key laø SearchData. Haøm traû veà con troû troû tôùi ñòa chæ cuûa nuùt coù Key
laø SearchData neáu tìm thaáy, trong tröôøng hôïp ngöôïc laïi haøm traû veà con troû NULL.
BST_Type BST_Searching(BST_Type BS_Tree, T SearchData)
{ BST_Type CurNode = BS_Tree;
while (CurNode != NULL && CurNode->Key != SearchData)
{ if (CurNode->Key > SearchData)
CurNode = CurNode->BST_Left;
else
CurNode = CurNode->BST_Right;
}
return (CurNode);
}
b. Theâm moät nuùt vaøo trong caây:
Giaû söû chuùng ta caàn theâm moät nuùt coù thaønh phaàn döõ lieäu (Key) laø NewData vaøo trong
caây nhò phaân tìm kieám sao cho sau khi theâm caây vaãn laø moät caây nhò phaân tìm kieám.
Trong thao taùc naøy tröôùc heát chuùng ta phaûi tìm kieám vò trí theâm, sau ñoù môùi tieán
haønh theâm nuùt môùi vaøo caây (Do vaäy thuaät toaùn coøn ñöôïc goïi laø thuaät toaùn tìm kieám
vaø theâm vaøo caây). Quaù trình tìm kieám tuaân thuû caùc böôùc trong thuaät toaùn tìm kieám
ñaõ trình baøy ôû treân.
Trong thuaät toaùn naøy chuùng ta seõ trình baøy thao taùc theâm vaøo caây nhò phaân tìm kieám
trong tröôøng hôïp khoâng coù hieän töôïng truøng laép khoùa. Do vaäy, neáu NewData bò truøng
Trang: 169
- 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
vôùi Key cuûa moät trong caùc nuùt ôû trong caây nhò phaân tìm kieám thì chuùng ta seõ khoâng
c u -tr a c k c u -tr a c k
thöïc hieän thao taùc theâm naøy. Tuy nhieân, neáu chuùng ta söû duïng caáu truùc döõ lieäu môû
roäng thì vieäc truøng khoùa seõ giaûi quyeát ñôn giaûn vì khoâng laøm taêng soá nuùt cuûa caây nhò
phaân tìm kieám maø chæ laøm taêng thaønh phaàn Count cuûa nuùt bò truøng khoùa theâm 1.
- Thuaät toaùn theâm 1 nuùt vaøo caây nhò phaân tìm kieám:
B1: NewNode = BinT_Create_Node(NewData)
B2: IF (NewNode = NULL)
Thöïc hieän Bkt
B3: IF (BSTree = NULL) // Caây roãng
B3.1: BSTree = NewNode
B3.2: Thöïc hieän Bkt
B4: CurNode = BSTree
B5: IF (CurNode->Key = NewData) // Truøng khoùa
Thöïc hieän Bkt
B6: IF (CurNode->Key > NewData)
B6.1: AddLeft = True // Theâm vaøo caây con traùi cuûa CurNode
B6.2: If (CurNode->BST_Left != NULL)
CurNode = CurNode->BST_Left
B7: IF (CurNode->Key < NewData)
B7.1: AddLeft = False // Theâm vaøo caây con phaûi cuûa CurNode
B7.2: If (CurNode->BST_Right != NULL)
CurNode = CurNode->BST_Right
B8: Laëp laïi B5
B9: IF (AddLeft = True)
CurNode->BST_Left = NewNode
B10: ELSE
CurNode->BST_Right = NewNode
Bkt: Keát thuùc
- Minh hoïa thuaät toaùn:
Giaû söû chuùng ta caàn theâm vaøo trong caây nhò phaân tìm kieám 1 nuùt coù thaønh phaàn
döõ lieäu laø 55: NewData = 55
NewNode CurNode BSTree
55 60
NULL NULL 25 65
19 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL NULL NULL
Trang: 170
- 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
CurNode->Key > NewData // Theâm vaøo caây con traùi
c u -tr a c k c u -tr a c k
⇒ AddLeft = True
CurNode->BST_Left != NULL // Chuyeån sang caây con traùi
⇒ CurNode = CurNode->BST_Left
BSTree
NewNode CurNode 60
55 25 65
NULL NULL 19 40 NULL NULL
10 NULL 30 44
NULL NULL NULL NULL NULL NULL
CurNode->Key < NewData // Theâm vaøo caây con phaûi
⇒ AddLeft = False
CurNode->BST_Right != NULL // Chuyeån sang caây con phaûi
⇒ CurNode = CurNode->BST_Right
BSTree
60
NewNode 25 CurNode 65
55 19 40 NULL NULL
NULL NULL 10 NULL 30 44
NULL NULL NULL NULL NULL NULL
CurNode->Key < NewData // Theâm vaøo caây con beân phaûi
⇒ AddLeft = False
CurNode->BST_Right != NULL // Chuyeån sang caây con beân phaûi
⇒ CurNode = CurNode->BST_Right
Trang: 171
- 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
c u -tr a c k c u -tr a c k
BSTree
60
25 65
19 40 NULL NULL NewNode
CurNode
10 NULL 30 44 55
NULL NULL NULL NULL NULL NULL NULL NULL
CurNode->Key < NewData // Theâm vaøo caây con phaûi
⇒ AddLeft = False
CurNode->BST_Right == NULL
// Theâm NewNode vaøo thaønh nuùt goác caây con phaûi cuûa CurNode
// (AddLeft = False), thuaät toaùn keát thuùc.
⇒ CurNode->BST_Right = NewNode
Keát quaû sau khi theâm:
BSTree
60
25 65
19 40 NULL NULL
CurNode
10 NULL 30 44 NewNode
NULL NULL NULL NULL NULL 55
NULL NULL
- Caøi ñaët thuaät toaùn:
Haøm BST_Add_Node coù prototype:
BST_Type BST_Add_Node(BST_Type &BS_Tree, T NewData);
Trang: 172
nguon tai.lieu . vn
