Giáo trình phân tích quy trình ứng dụng thuật toán có thành phần dữ liệu newdata p6
Thêm vào BST
Báo xấulượt xem 4
download
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
Theo phương pháp này chúng ta sẽ không hủy nút có địa chỉ DelNode mà chúng ta sẽ hủy nút có địa chỉ của phần tử thế mạng là nút phải nhất trong cây con trái của DelNode (MRNode), hoặc là nút trái nhất trong cây con phải của DelNode.Hàm thực hiện việc thêm vào cây nhị phân tìm kiếm BS_Tree một nút có thành phần Key là NewData. Hàm trả về con trỏ trỏ tới địa chỉ của nút mới thêm nếu việc thêm thành công, trong trường hợp ngược lại hàm trả về con trỏ NULL. BST_Type BST_Add_Node(BST_Type...
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Giáo trình phân tích quy trình ứng dụng thuật toán có thành phần dữ liệu newdata p6
- 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 Tieán haønh caùc böôùc ñeå huûy DelNode: B3: PrDelNode->BST_Left = DelNode->BST_Left B4: DelNode->BST_Left = NULL PrDelNode BSTree DelNode 60 MRNode 25 65 19 NULL NULL 40 NULL NULL 10 30 44 NULL NULL NULL NULL NULL NULL Keát quaû sau khi huûy: PrDelNode BSTree MRNode 60 19 65 10 40 NULL NULL NULL NULL 30 44 NULL NULL NULL NULL - Söû duïng phaàn töû theá maïng (standby): Theo phöông phaùp naøy chuùng ta seõ khoâng huûy nuùt coù ñòa chæ DelNode maø chuùng ta seõ huûy nuùt coù ñòa chæ cuûa phaàn töû theá maïng laø nuùt phaûi nhaát trong caây con traùi cuûa DelNode (MRNode), hoaëc laø nuùt traùi nhaát trong caây con phaûi cuûa DelNode (MLNode). Sau khi chuyeån toaøn boä noäi dung döõ lieäu cuûa nuùt theá maïng cho DelNode (DelNode Key = MRNode->Key hoaëc DelNode->Key = MLNode->Key) thì chuùng ta seõ huûy nuùt theá maïng nhö ñoái vôùi tröôøng hôïp c1) vaø c2) ôû treân. Ví duï: Giaû söû caàn huûy nuùt coù Key = 25 (DelData = 25). Chuùng ta seõ choïn phaàn töû theá maïng MLNode laø nuùt traùi nhaát trong caây con phaûi cuûa DelNode (traùi nhaát trong DelNode->BST_Right) ñeå huûy, Trang: 178
- 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 DelNode 60 25 PrMLNode 65 19 MLNode 40 NULL NULL 10 NULL 30 44 NULL NULL NULL NULL NULL NULL Chuyeån döõ lieäu trong MLNode veà cho DelNode: DelNode->Key = MLNode->Key BSTree DelNode 60 30 PrMLNode 65 19 MLNode 40 NULL NULL 10 NULL 30 44 NULL NULL NULL NULL NULL NULL Tieán haønh huûy MLNode (huûy nuùt laù): PrMLNode->BST_Left = NULL BSTree DelNode 60 30 PrMLNode 65 19 MLNode 40 NULL NULL 10 NULL 30 NULL 44 NULL NULL NULL NULL NULL NULL Trang: 179
- 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 Keát quaû sau khi huûy: c u -tr a c k c u -tr a c k BSTree DelNode 60 30 PrMLNode 65 19 40 NULL NULL 10 NULL NULL 44 NULL NULL NULL NULL - 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 chuyeån caây con phaûi cuûa nuùt caàn huûy veà thaønh caây con phaûi cuûa caây con coù nuùt goác laø nuùt phaûi nhaát trong caây con traù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 // 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 B10 // 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 Trang: 180
- 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 B8.2.2: DelNode->BST_Right = NULL c u -tr a c k c u -tr a c k B8.2.3: Thöïc hieän B10 // 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 B10 // Neáu DelNode coù hai caây con B8.4: If (DelNode->BST_Left != NULL) and (DelNode->BST_Right != NULL) // Tìm nuùt phaûi nhaát trong caây con traùi cuûa DelNode B8.4.1: MRNode = DelNode->BST_Left B8.4.2: if (MRNode->BST_Right = NULL) Thöïc hieän B8.4.5 B8.4.3: MRNode = MRNode->BST_Right B8.4.4: Laëp laïi B8.4.2 // Chuyeån caây con phaûi cuûa DelNode veà caây con phaûi cuûa MRNode B8.4.5: MRNode->BST_Right = DelNode->BST_Right B8.4.6: DelNode->BST_Right = NULL // Chuyeån caây con traùi coøn laïi cuûa DelNode veà cho BSTree B8.4.7: BSTree = BSTree->BST_Left B8.4.8: DelNode->BST_Left = NULL B8.4.9: Thöïc hieän B10 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 B10 // 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 B10 // 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 Trang: 181
- 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 B9.3.2: else c u -tr a c k c u -tr a c k PrDelNode->BST_Right = DelNode->BST_Left B9.3.3: DelNode->BST_Left = NULL B9.3.4: Thöïc hieän B10 // Neáu DelNode coù hai caây con B9.4: If (DelNode->BST_Left != NULL) and (DelNode->BST_Right != NULL) // Tìm nuùt phaûi nhaát trong caây con traùi cuûa DelNode B9.4.1: MRNode = DelNode->BST_Left B9.4.2: if (MRNode->BST_Right = NULL) Thöïc hieän B9.4.5 B9.4.3: MRNode = MRNode->BST_Right B9.4.4: Laëp laïi B9.4.2 // Chuyeån caây con phaûi DelNode veà thaønh caây con phaûi MRNode B9.4.5: MRNode->BST_Right = DelNode->BST_Right B9.4.6: DelNode->BST_Right = NULL // Chuyeån caây con traùi coøn laïi cuûa DelNode veà cho PrDelNode B9.4.7: if (OnTheLeft = True) PrDelNode->BST_Left = DelNode->BST_Left B9.4.8: else PrDelNode->BST_Right = DelNode->BST_Left B9.4.9: DelNode->BST_Left = NULL B9.4.10: Thöïc hieän B10 // Huûy DelNode B10: delete DelNode Bkt: Keát thuùc - Caøi ñaët thuaät toaùn: Haøm BST_Delete_Node_TRS coù prototype: int BST_Delete_Node_TRS(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 chuyeån caây con phaûi cuûa nuùt caàn huûy veà thaønh caây con phaûi cuûa caây coù nuùt goác laø nuùt phaûi nhaát trong caây con traù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_TRS(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) Trang: 182
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Giáo trình phân tích quy trình ghost phân vùng hệ thống thành tập tin khi sử dụng partition magic p7
5 p | 
49
| 
5
-
Giáo trình phân tích quy trình ghost phân vùng hệ thống thành tập tin khi sử dụng partition magic p3
5 p | 71
| 5
-
Giáo trình phân tích quy trình ghost phân vùng hệ thống thành tập tin khi sử dụng partition magic p2
5 p | 79
| 5
-
Giáo trình phân tích quy trình cung cấp dịch vụ của các nhà phân phối internet ISP p2
5 p | 87
| 4
-
Giáo trình phân tích quy trình cung cấp dịch vụ của các nhà phân phối internet ISP p1
5 p | 63
| 4
-
Giáo trình phân tích quy trình ghost phân vùng hệ thống thành tập tin khi sử dụng partition magic p6
5 p | 58
| 4
-
Giáo trình phân tích quy trình ghost phân vùng hệ thống thành tập tin khi sử dụng partition magic p5
5 p | 63
| 4
-
Giáo trình phân tích quy trình ghost phân vùng hệ thống thành tập tin khi sử dụng partition magic p1
5 p | 71
| 4
-
Giáo trình phân tích quy trình tạo partition mới trên ổ đĩa bằng phần mềm partition magic p9
5 p | 72
| 4
-
Giáo trình phân tích quy trình tạo partition mới trên ổ đĩa bằng phần mềm partition magic p8
5 p | 75
| 4
-
Giáo trình phân tích quy trình tạo partition mới trên ổ đĩa bằng phần mềm partition magic p3
5 p | 68
| 4
-
Giáo trình phân tích quy trình tạo partition mới trên ổ đĩa bằng phần mềm partition magic p4
5 p | 73
| 4
-
Giáo trình phân tích quy trình tạo partition mới trên ổ đĩa bằng phần mềm partition magic p10
5 p | 65
| 3
-
Giáo trình phân tích quy trình ghost phân vùng hệ thống thành tập tin khi sử dụng partition magic p9
5 p | 66
| 3
-
Giáo trình phân tích quy trình tạo partition mới trên ổ đĩa bằng phần mềm partition magic p5
5 p | 79
| 3
-
Giáo trình phân tích quy trình tạo partition mới trên ổ đĩa bằng phần mềm partition magic p6
5 p | 87
| 3
-
Giáo trình phân tích quy trình tạo partition mới trên ổ đĩa bằng phần mềm partition magic p7
5 p | 76
| 3
-
Giáo trình phân tích quy trình tạo partition mới trên ổ đĩa bằng phần mềm partition magic p1
5 p | 90
| 3
Chịu trách nhiệm nội dung:
Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA
LIÊN HỆ
Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM
Hotline: 093 303 0098
Email: support@tailieu.vn
Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.
