intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Dgdsfg Hkuyou | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST
Báo xấu
91
lượt xem 4
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo tài 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', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

  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 { 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
  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 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
  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 // 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
  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 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
  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 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
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

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.

 

Đồng bộ tài khoản
14=>2