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
GiáoinT_Type hướng dẫn dùngBTree) toán thêm một nút
B trình BinT_Initialize (BinT_Type & thuật
o
o
.c .c
.d o .d o
c u -tr a c k c u -tr a c k
{ BTree = NULL;
vào bên trái nhất của cây nhị phân
return (BTree);
}
b. Taïo môùi moät nuùt:
Thao taùc naøy hoaøn toaøn töông töï nhö ñoái vôùi thao taùc taïo môùi moät nuùt trong danh
saùch lieân keát ñoâi. Giaû söû chuùng ta caàn taïo môùi moät nuùt coù thaønh phaàn döõ lieäu laø
NewData.
- Thuaät toaùn:
B1: BTNode = new BinT_OneNode
B2: IF (BTNode = NULL)
Thöïc hieän Bkt
B3: BTNode->BinT_Left = NULL
B4: BTNode->BinT_Right = NULL
B5: BTNode->Key = NewData
Bkt: Keát thuùc
- Caøi ñaët thuaät toaùn:
Haøm BinT_Create_Node coù prototype:
BinT_Type BinT_Create_Node(T NewData);
Haøm taïo môùi moät nuùt coù thaønh phaàn döõ lieäu laø NewData, haøm traû veà con troû troû
tôùi ñòa chæ cuûa nuùt môùi taïo. Neáu khoâng ñuû boä nhôù ñeå taïo, haøm traû veà con troû
NULL.
BinT_Type BinT_Create_Node(T NewData)
{ BinT_Type BTnode = new BinT_OneNode;
if (BTnode != NULL)
{ BTnode->BinT_Left = NULL;
BTnode->BinT_Right = NULL;
BTnode->Key = NewData;
}
return (BTnode);
}
- Minh hoïa thuaät toaùn:
Giaû söû chuùng ta caàn taïo nuùt coù thaønh phaàn döõ lieäu laø 30: NewData = 30
BTnode = new BinT_OneNode
BTnode
BTnode->BinT_Left = NULL
BTnode->BinT_Right = NULL
Trang: 153
- 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
BTnode->Key = NewData
c u -tr a c k c u -tr a c k
BTnode
30
NULL NULL
c. Theâm moät nuùt vaøo trong caây nhò phaân:
Giaû söû chuùng ta caàn theâm moät nuùt coù giaù trò thaønh phaàn döõ lieäu laø NewData vaøo
trong caây nhò phaân. Vieäc theâm coù theå dieãn ra ôû caây con traùi hoaëc caây con phaûi cuûa
caây nhò phaân. Do vaäy, ôû ñaây chuùng ta trình baøy 2 thao taùc theâm rieâng bieät nhau:
- Thuaät toaùn theâm 1 nuùt vaøo beân traùi nhaát cuûa caây:
B1: NewNode = BinT_Create_Node (NewData)
B2: IF (NewNode = NULL)
Thöïc hieän Bkt
B3: IF (BinTree = NULL) // Caây roãng
B3.1: BinTree = NewNode
B3.2: Thöïc hieän Bkt
B4: Lnode = BinTree
B5: IF (Lnode->BinT_Left = NULL) // Caây con traùi roãng
B5.1: Lnode->BinT_Left = NewNode
B5.2: Thöïc hieän Bkt
B6: Lnode = Lnode->BinT_Left // Ñi theo nhaùnh caây con traùi
B7: Laëp laïi B5
Bkt: Keát thuùc
- Minh hoïa thuaät toaùn:
Giaû söû chuùng ta caàn theâm nuùt coù thaønh phaàn döõ lieäu laø 17 vaøo beân traùi nhaát cuûa
caây nhò phaân: NewData = 17
NewNode BinTree
17 20
NULL NULL Lnode 25 45
19 16 NULL NULL
NULL NULL 30 21
NULL NULL NULL NULL
Trang: 154
- 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
B5.1: Lnode->BinT_Left = NewNode
c u -tr a c k c u -tr a c k
NewNode BinTree
17 20
NULL NULL Lnode 25 45
19 16 NULL NULL
NULL 30 21
NULL NULL NULL NULL
Keát quaû sau khi theâm:
BinTree
20
Lnode 25 45
NewNode 19 16 NULL NULL
17 NULL 30 21
NULL NULL NULL NULL NULL NULL
- Caøi ñaët thuaät toaùn:
Haøm BinT_Add_Left coù prototype:
BinT_Type BinT_Add_Left(BinT_Type &BT_Tree, T NewData);
Haøm thöïc hieän vieäc theâm vaøo beân traùi nhaát trong caây nhò phaân BT_Tree moät nuùt
coù thaønh phaàn döõ lieäu laø NewData, haøm traû veà con troû troû tôùi ñòa chæ cuûa nuùt môùi
theâm neáu vieäc theâm thaønh coâng, ngöôïc laïi neáu khoâng ñuû boä nhôù, haøm traû veà con
troû NULL.
BinT_Type BinT_Add_Left(BinT_Type &BT_Tree, T NewData)
{ BinT_Type NewNode = BinT_Create_Node(NewData);
if (NewNode == NULL)
return (NewNode);
if (BT_Tree == NULL)
Trang: 155
- 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
BT_Tree = NewNode;
c u -tr a c k c u -tr a c k
else
{ BinT_Type Lnode = BT_Tree;
while (Lnode->BinT_Left != NULL)
Lnode = Lnode->BinT_Left;
Lnode->BinT_Left = NewNode;
}
return (NewNode);
}
- Thuaät toaùn theâm 1 nuùt vaøo beân phaûi nhaát cuûa caây nhò phaân:
B1: NewNode = BinT_Create_Node (NewData)
B2: IF (NewNode = NULL)
Thöïc hieän Bkt
B3: IF (BinTree = NULL) // Caây roãng
B3.1: BinTree = NewNode
B3.2: Thöïc hieän Bkt
B4: Rnode = BinTree
B5: IF (Rnode->BinT_Right = NULL) // Caây con phaûi roãng
B5.1: Rnode->BinT_Right = NewNode
B5.2: Thöïc hieän Bkt
B6: Rnode = Rnode->BinT_Right // Ñi theo nhaùnh caây con phaûi
B7: Laëp laïi B5
Bkt: Keát thuùc
- Minh hoïa thuaät toaùn:
Giaû söû chuùng ta caàn theâm nuùt coù thaønh phaàn döõ lieäu laø 21 vaøo beân phaûi nhaát cuûa
caây nhò phaân: NewData = 21
BinTree NewNode
40 Rnode 21
36 55 NULL NULL
12 18 45 NULL
NULL NULL NULL NULL 10 8
NULL NULL 11 5
NULL NULL NULL NULL
Trang: 156
- 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
B5.1: Rnode->BinT_Right = NewNode
c u -tr a c k c u -tr a c k
BinTree NewNode
40 Rnode 21
36 55 NULL NULL
12 18 45 NULL
NULL NULL NULL NULL 10 8
NULL NULL 11 5
NULL NULL NULL NULL
Keát quaû sau khi theâm:
BinTree
40 Rnode
36 55 NewNode
12 18 45 21
NULL NULL NULL NULL 10 8 NULL NULL
NULL NULL 11 5
NULL NULL NULL NULL
- Caøi ñaët thuaät toaùn:
Haøm BinT_Add_Right coù prototype:
BinT_Type BinT_Add_Right(BinT_Type &BT_Tree, T NewData);
Haøm thöïc hieän vieäc theâm vaøo beân phaûi nhaát trong caây nhò phaân BT_Tree moät nuùt
coù thaønh phaàn döõ lieäu laø NewData, haøm traû veà con troû troû tôùi ñòa chæ cuûa nuùt môùi
theâm neáu vieäc theâm thaønh coâng, ngöôïc laïi neáu khoâng ñuû boä nhôù, haøm traû veà con
troû NULL.
BinT_Type BinT_Add_Right(BinT_Type &BT_Tree, T NewData)
Trang: 157
nguon tai.lieu . vn
