Tìm hiểu tầm quan trọng của cấu trúc dữ liệu trong giải thuật phần 9 pdf

Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät

Trang: 185

// Neáu DelNode laø nuùt laù

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

Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät

Trang: 186

B10.3: if (MLNode->BST_Left = NULL)

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;

}

}