- 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 p7
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
{ DelNode = DelNode->BST_Left;
c u -tr a c k c u -tr a c k
OnTheLeft = 1;
}
else // (DelNode->Key < DelData)
{ DelNode = DelNode->BST_Right;
OnTheLeft = 0;
}
}
if (DelNode == NULL) // Khoâng coù nuùt ñeå huûy
return (0);
if (PrDelNode == NULL) // DelNode laø nuùt goác
{ if (DelNode->BST_Left == NULL && DelNode->BST_Right == NULL)
BS_Tree = NULL;
else
if (DelNode->BST_Left == NULL) // DelNode coù 1 caây con phaûi
{ BS_Tree = BS_Tree->BST_Right;
DelNode->BST_Right = NULL;
}
else
if (DelNode->BST_Right == NULL) // DelNode coù 1 caây con traùi
{ BS_Tree = BS_Tree->BST_Left;
DelNode->BST_Left = NULL;
}
else // DelNode coù hai caây con
{ BST_Type MRNode = DelNode->BST_Left;
while (MRNode->BST_Right != NULL)
MRNode = MRNode->BST_Right;
MRNode->BST_Right = DelNode->BST_Right;
DelNode->BST_Right = NULL;
BS_Tree = BS_Tree->BST_Left;
DelNode->BST_Left = NULL;
}
}
else // DelNode laø nuùt trung gian
{ if (DelNode->BST_Left == NULL && DelNode->BST_Right == NULL)
if (OnTheLeft == 1)
PrDelNode->BST_Left = NULL;
else
PrDelNode->BST_Right = NULL;
else
if (DelNode->BST_Left == NULL) // DelNode coù 1 caây con phaûi
{ if (OnTheLeft == 1)
PrDelNode->BST_Left = DelNode->BST_Right;
else
PrDelNode->BST_Right = DelNode->BST_Right;
DelNode->BST_Right = NULL;
}
else
Trang: 183
- 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
if (DelNode->BST_Right == NULL) // DelNode coù 1 caây con traùi
c u -tr a c k c u -tr a c k
{ if (OnTheLeft == 1)
PrDelNode->BST_Left = DelNode->BST_Left;
else
PrDelNode->BST_Right = DelNode->BST_Left;
DelNode->BST_Left = NULL;
}
else // DelNode coù hai caây con
{ BST_Type MRNode = DelNode->BST_Left;
while (MRNode->BST_Right != NULL)
MRNode = MRNode->BST_Right;
MRNode->BST_Right = DelNode->BST_Right;
DelNode->BST_Right = NULL;
if (OnTheLeft == 1)
PrDelNode->BST_Left = DelNode->BST_Left;
else
PrDelNode->BST_Right = DelNode->BST_Left;
DelNode->BST_Left = NULL;
}
}
delete DelNode;
return (1);
}
- Thuaät toaùn huûy 1 nuùt trong caây nhò phaân tìm kieám baèng phöông phaùp huûy phaàn töû
theá maïng laø phaàn töû traùi nhaát trong caây con phaûi cuûa nuùt caàn huûy (neáu nuùt caàn
huûy coù ñuû 02 caây con):
// Tìm nuùt caàn huûy vaø nuùt cha cuûa nuùt caàn huûy
B1: DelNode = BSTree
B2: PrDelNode = NULL
B3: IF (DelNode = NULL)
Thöïc hieän Bkt
B4: IF (DelNode->Key = DelData)
Thöïc hieän B8
B5: IF (DelNode->Key > DelData) // Chuyeån sang caây con traùi
B5.1: PrDelNode = DelNode
B5.2: DelNode = DelNode->BST_Left
B5.3: OnTheLeft = True
B5.4: Thöïc hieän B7
B6: IF (DelNode->Key < DelData) // Chuyeån sang caây con phaûi
B6.1: PrDelNode = DelNode
B6.2: DelNode = DelNode->BST_Right
B6.3: OnTheLeft = False
B6.4: Thöïc hieän B7
B7: Laëp laïi B3
// Chuyeån caùc moái quan heä cuûa DelNode cho caùc nuùt khaùc
B8: IF (PrDelNode = NULL) // DelNode laø nuùt goác
Trang: 184
- 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
// Neáu DelNode laø nuùt laù
c u -tr a c k c u -tr a c k
B8.1: If (DelNode->BST_Left = NULL) and (DelNode->BST_Right = NULL)
B8.1.1: BSTree = NULL
B8.1.2: Thöïc hieän B11
// Neáu DelNode coù moät caây con phaûi
B8.2: If (DelNode->BST_Left = NULL) and (DelNode->BST_Right != NULL)
B8.2.1: BSTree = BSTree->BST_Right
B8.2.2: DelNode->BST_Right = NULL
B8.2.3: Thöïc hieän B11
// Neáu DelNode coù moät caây con traùi
B8.3: If (DelNode->BST_Left != NULL) and (DelNode->BST_Right = NULL)
B8.3.1: BSTree = BSTree->BST_Left
B8.3.2: DelNode->BST_Left = NULL
B8.3.3: Thöïc hieän B11
B9: ELSE // DelNode khoâng phaûi laø nuùt goác
// Neáu DelNode laø nuùt laù
B9.1: If (DelNode->BST_Left = NULL) and (DelNode->BST_Right = NULL)
// DelNode laø caây con traùi cuûa PrDelNode
B9.1.1: if (OnTheLeft = True)
PrDelNode->BST_Left = NULL
B9.1.2: else // DelNode laø caây con phaûi cuûa PrDelNode
PrDelNode->BST_Right = NULL
B9.1.3: Thöïc hieän B11
// Neáu DelNode coù moät caây con phaûi
B9.2: If (DelNode->BST_Left = NULL) and (DelNode->BST_Right != NULL)
B9.2.1: if (OnTheLeft = True)
PrDelNode->BST_Left = DelNode->BST_Right
B9.2.2: else
PrDelNode->BST_Right = DelNode->BST_Right
B9.2.3: DelNode->BST_Right = NULL
B9.2.4: Thöïc hieän B11
// Neáu DelNode coù moät caây con traùi
B9.3: If (DelNode->BST_Left != NULL) and (DelNode->BST_Right = NULL)
B9.3.1: if (OnTheLeft = True)
PrDelNode->BST_Left = DelNode->BST_Left
B9.3.2: else
PrDelNode->BST_Right = DelNode->BST_Left
B9.3.3: DelNode->BST_Left = NULL
B9.3.4: Thöïc hieän B11
// Neáu DelNode coù hai caây con
B10: If (DelNode->BST_Left != NULL) and (DelNode->BST_Right != NULL)
// Tìm nuùt traùi nhaát trong caây con phaûi cuûa DelNode vaø nuùt cha cuûa noù
B10.1: MLNode = DelNode->BST_Right
B10.2: PrMLNode = DelNode
Trang: 185
- 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
B10.3: if (MLNode->BST_Left = NULL)
c u -tr a c k c u -tr a c k
Thöïc hieän B10.7
B10.4: PrMLNode = MLNode
B10.5: MLNode = MLNode->BST_Left
B10.6: Laëp laïi B10.3
// Cheùp döõ lieäu töø MLNode veà DelNode
B10.7: DelNode->Key = MLNode->Key
// Chuyeån caây con phaûi cuûa MLNode veà caây con traùi cuûa PrMLNode
B10.8: if (PrMLNode = DelNode) // MLNode laø nuùt phaûi cuûa PrMLNode
PrMLNode->BST_Right = MLNode->BST_Right
B10.9: else // MLNode laø nuùt traùi cuûa PrMLNode
PrMLNode->BST_Left = MLNode->BST_Right
B10.10: MLNode->BST_Right = NULL
// Chuyeån vai troø cuûa MLNode cho DelNode
B10.11: DelNode = MLNode
B10.12: Thöïc hieän B11
// Huûy DelNode
B11: delete DelNode
Bkt: Keát thuùc
- Caøi ñaët thuaät toaùn:
Haøm BST_Delete_Node_SB coù prototype:
int BST_Delete_Node_SB(BST_Type &BS_Tree, T DelData);
Haøm thöïc hieän vieäc huûy nuùt coù thaønh phaàn Key laø DelData treân caây nhò phaân tìm
kieám BS_Tree baèng phöông phaùp huûy phaàn töû theá maïng laø phaàn töû traùi nhaát trong
caây con phaûi cuûa nuùt caàn huûy (neáu nuùt caàn huûy coù hai caây con). Haøm traû veà giaù
trò 1 neáu vieäc huûy thaønh coâng (coù nuùt ñeå huûy), trong tröôøng hôïp ngöôïc laïi haøm traû
veà giaù trò 0 (khoâng toàn taïi nuùt coù Key laø DelData hoaëc caây roãng).
int BST_Delete_Node_SB(BST_Type &BS_Tree, T DelData)
{ BST_Type DelNode = BS_Tree;
BST_Type PrDelNode = NULL;
int OnTheLeft = 0;
while (DelNode != NULL)
{ if (DelNode->Key == DelData)
break;
PrDelNode = DelNode;
if (DelNode->Key > DelData)
{ DelNode = DelNode->BST_Left;
OnTheLeft = 1;
}
else // (DelNode->Key < DelData)
{ DelNode = DelNode->BST_Right;
OnTheLeft = 0;
}
}
Trang: 186
- 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
if (DelNode == NULL) // Khoâng coù nuùt ñeå huûy
c u -tr a c k c u -tr a c k
return (0);
if (PrDelNode == NULL) // DelNode laø nuùt goác
{ if (DelNode->BST_Left == NULL && DelNode->BST_Right == NULL)
BS_Tree = NULL;
else
if (DelNode->BST_Left == NULL) // DelNode coù 1 caây con phaûi
{ BS_Tree = BS_Tree->BST_Right;
DelNode->BST_Right = NULL;
}
else
if (DelNode->BST_Right == NULL) // DelNode coù 1 caây con traùi
{ BS_Tree = BS_Tree->BST_Left;
DelNode->BST_Left = NULL;
}
}
else // DelNode laø nuùt trung gian
{ if (DelNode->BST_Left == NULL && DelNode->BST_Right == NULL)
if (OnTheLeft == 1)
PrDelNode->BST_Left = NULL;
else
PrDelNode->BST_Right = NULL;
else
if (DelNode->BST_Left == NULL) // DelNode coù 1 caây con phaûi
{ if (OnTheLeft == 1)
PrDelNode->BST_Left = DelNode->BST_Right;
else
PrDelNode->BST_Right = DelNode->BST_Right;
DelNode->BST_Right = NULL;
}
else
if (DelNode->BST_Right == NULL) // DelNode coù 1 caây con traùi
{ if (OnTheLeft == 1)
PrDelNode->BST_Left = DelNode->BST_Left;
else
PrDelNode->BST_Right = DelNode->BST_Left;
DelNode->BST_Left = NULL;
}
}
// DelNode coù hai caây con
if (DelNode->BST_Left != NULL && DelNode->BST_Right != NULL)
{ BST_Type MLNode = DelNode->BST_Right;
BST_Type PrMLNode = DelNode;
while (MLNode->BST_Left != NULL)
{ PrMLNode = MLNode;
MLNode = MLNode->BST_Left;
}
DelNode->Key = MLNode->Key;
Trang: 187
nguon tai.lieu . vn