1. Trang Chủ
  2. Cơ sở dữ liệu
  3. 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 p6

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 p6

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.Tiến hành các bước để hủy DelNode: B3: PrDelNode-BST_Left = DelNode-BST_Left B4: DelNode-BST_Left = NULL 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

Thể loại Tài liệu miễn phí Cơ sở dữ liệu

Số trang 5

Ngày tạo 8/29/2018 9:27:10 PM +00:00

Loại tệp PDF

Kích thước

Tên tệp

Tải Giáo trình hướng dẫn dùng thuật toán thêm một nút ... (.pdf)

Xem mẫu

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
nguon tai.lieu . vn
Tin học văn phòng Đồ họa - Thiết kế - Flash Quản trị Web Cơ sở dữ liệu Quản trị mạng Kỹ thuật lập trình Hệ điều hành Phần cứng An ninh - Bảo mật Chứng chỉ quốc tế Thủ thuật máy tính Điện - Điện tử Kinh tế học Hoá học Xã hội học Môi trường