Tìm hiểu tầm quan trọng của cấu trúc dữ liệu và giải thụât trong một đề án tin học phần 8

Cài đặt thuật toán: Hàm BinT_Num_Node có prototype: int BinT_Num_Node(BinT_Type BTree); Hàm tính số nút của cây BTree theo thuật toán đệ quy
Nội dung trích xuất từ tài liệu:
Tìm hiểu tầm quan trọng của cấu trúc dữ liệu và giải thụât trong một đề án tin học phần 8 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät - Thuaät toaùn: B1: IF (BinTree = NULL) B1.1: NN = 0 B1.2: Thöïc hieän Bkt B2: NNL = NN(BinTree->BinT_Left) B3: NNR = NN(BinTree->BinT_Right) B4: NN = NNL + NNR + 1 Bkt: Keát thuùc Ví duï: Soá nuùt cuûa caây nhò phaân sau baèng 8. BinTree 40 36 55 12 18 45 21 NULL NULL NULL NULL NULL 8 NULL NULL 0 0 0 0 0 0 0 1(0+0+1) 1 (0+0+1) NULL NULL 1 (0+0+1) 3 (1+1+1) 0 0 1 (0+0+1) 2 (0+1+1) 4 (2+1+1) 8 (3+4+1) - Caøi ñaët thuaät toaùn: Haøm BinT_Num_Node coù prototype: int BinT_Num_Node(BinT_Type BTree); Haøm tính soá nuùt cuûa caây BTree theo thuaät toaùn ñeä quy. Haøm traû veà soá nuùt cuûa caây caàn tính. int BinT_Num_Node(BinT_Type BTree) { if (BTree == NULL) return (0); int NNL = BinT_Num_Node(BTree->BinT_Left); int NNR = BinT_Num_Node(BTree->BinT_Right); return (NNL + NNR + 1); }g. Huûy moät nuùt treân caây nhò phaân: Vieäc huûy moät nuùt trong caây coù theå laøm cho caây trôû thaønh röøng. Do vaäy trong thao taùc naøy neáu chuùng ta tieán haønh huûy moät nuùt laù thì khoâng coù ñieàu gì xaûy ra, song neáu huûy Trang: 162 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät nuùt khoâng phaûi laø nuùt laù thì chuùng ta phaûi tìm caùch chuyeån caùc nuùt goác caây con laø caùc nuùt con cuûa nuùt caàn huûy thaønh caùc nuùt goác caây con cuûa caùc nuùt khaùc roài môùi tieán haønh huûy nuùt naøy. - Tröôøng hôïp neáu nuùt caàn huûy chæ coù 01 nuùt goác caây con thì chuùng ta coù theå chuyeån nuùt goác caây con naøy thaønh nuùt goác caây con cuûa nuùt cha cuûa nuùt caàn huûy. - Tröôøng hôïp neáu nuùt caàn huûy coù 2 nuùt goác caây con thì chuùng ta phaûi chuyeån 02 nuùt goác caây con naøy thaønh nuùt goác caây con cuûa caùc nuùt khaùc vôùi nuùt caàn huûy. Vieäc choïn caùc nuùt ñeå laøm nhieäm vuï nuùt cha cuûa caùc nuùt goác caây con naøy tuøy vaøo töøng tröôøng hôïp cuï theå cuûa caây nhò phaân maø chuùng ta seõ löïa choïn cho phuø hôïp. Do vaäy, thao taùc huûy moät nuùt seõ ñöôïc trình baøy cuï theå trong caùc loaïi caây cuï theå ñöôïc trình baøy ôû caùc phaàn sau.5.2.3. Caây nhò phaân tìm kieám (Binary Searching Tree)A. Khaùi nieäm – Caáu truùc döõ lieäu:Caây nhò phaân tìm kieám laø caây nhò phaân coù thaønh phaàn khoùa cuûa moïi nuùt lôùn hôn thaønhphaàn khoùa cuûa taát caû caùc nuùt trong caây con traùi cuûa noù vaø nhoû hôn thaønh phaàn khoùacuûa taát caû caùc nuùt trong caây con phaûi cuûa noù.Ví duï: Hình aûnh sau laø hình aûnh cuûa moät caây nhò phaân tìm kieám BSTree 60 25 65 19 40 NULL NULL 10 NULL 30 44 NULL NULL NULL NULL 50 15 NULL NULL NULL NULLTöø khaùi nieäm naøy chuùng ta coù moät soá nhaän xeùt:- Caáu truùc döõ lieäu cuûa caây nhò phaân tìm kieám laø caáu truùc döõ lieäu ñeå bieåu dieãn caùc caây nhò phaân noùi chung.typedef struct BST_Node { T Key; BST_Node * BST_Left; // Vuøng lieân keát quaûn lyù ñòa chæ nuùt goác caây con traùi BST_Node * BST_Right; // Vuøng lieân keát quaûn lyù ñòa chæ nuùt goác caây con phaûi BST_OneNode; } Trang: 163 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaättypedef BST_OneNode * BST_Type;Ñeå quaûn lyù caùc caây nhò phaân tìm kieám chuùng ta caàn quaûn lyù ñòa chæ nuùt goá ...