ให้ต้นไม้ไบนารี ตอนนี้ เราได้รับมอบหมายให้ค้นหาทรีย่อยที่ใหญ่ที่สุดที่มีจำนวนเท่ากับ 1 และ 0 ต้นไม้มีเพียง 0 และ 1
แนวทางในการหาแนวทางแก้ไข
ในแนวทางนี้ เราจะแทนที่โหนดทั้งหมดด้วยค่า 0 ถึง -1 การทำเช่นนี้จะทำให้โปรแกรมของเราง่ายขึ้น เนื่องจากเราต้องค้นหาทรีย่อยที่ใหญ่ที่สุดโดยมีผลรวมเท่ากับ 0
ตัวอย่าง
รหัส C++ สำหรับแนวทางข้างต้น
#include <iostream>
using namespace std;
int maxi = -1;
struct node { // structure of our tree node
int data;
struct node *right, *left;
};
struct node* newnode(int key){// To create a new node
struct node* temp = new node;
temp->data = key;
temp->right = NULL;
temp->left = NULL;
return temp;
}
void inorder(struct node* root){ // traversing the tree(not used)
if (root == NULL)
return;
inorder(root->left);
cout << root->data << endl;
inorder(root->right);
}
// Function to return the maximum size of
// the sub-tree having an equal number of 0's and 1's
int calculatingmax(struct node* root){
int a = 0, b = 0;
if (root == NULL)
return 0;
a = calculatingmax(root->right); // right subtree
a = a + 1; // including parent
b = calculatingmax(root->left); // left subtree
a = b + a; // number of nodes at current subtree
if (root->data == 0) // if the sum of whole subtree is 0
// If the total size exceeds
// the current max
if (a >= maxi)
maxi = a;
return a;
}
int calc_sum(struct node* root){ // updating the values at each node
if (root != NULL){
if (root->data == 0){
root->data = -1;
}
}
int a = 0, b = 0;
// If left child exists
if (root->left != NULL)
a = calc_sum(root->left);
// If right child exists
if (root->right != NULL)
b = calc_sum(root->right);
root->data += (a + b);
return root->data;
}
// Driver code
int main(){
struct node* root = newnode(1);
root->right = newnode(0);
root->right->right = newnode(1);
root->right->right->right = newnode(1);
root->left = newnode(0);
root->left->left = newnode(1);
root->left->left->left = newnode(1);
root->left->right = newnode(0);
root->left->right->left = newnode(1);
root->left->right->left->left = newnode(1);
root->left->right->right = newnode(0);
root->left->right->right->left = newnode(0);
root->left->right->right->left->left = newnode(1);
calc_sum(root);
calculatingmax(root);
// cout << "h";
cout << maxi;
return 0;
} ผลลัพธ์
6
คำอธิบายของโค้ดด้านบน
ในแนวทางข้างต้น เราอัปเดตโหนดทั้งหมดที่มีค่า 0 ถึง -1 แล้วตอนนี้เราลดปัญหาของเราเพื่อค้นหาทรีย่อยที่ใหญ่ที่สุดที่มีผลรวมเท่ากับ 0 ในขณะนี้ในขณะที่อัปเดตนี้ เรายังอัปเดตโหนดทั้งหมดด้วยค่าเต็ม ความสำคัญของทรีย่อยที่รูทที่โหนดนั้น และตอนนี้เราใช้ฟังก์ชันที่สองในการคำนวณและตรวจสอบทุกโหนดที่มีค่า 0 จากนั้นจึงหาจำนวนสูงสุดของโหนดที่มีอยู่ในทรีนั้น
บทสรุป
ในบทช่วยสอนนี้ เราแก้ปัญหาเพื่อค้นหาทรีย่อยที่ใหญ่ที่สุดที่มีจำนวนเท่ากับ 1 และ 0 นอกจากนี้เรายังได้เรียนรู้โปรแกรม C++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ (ปกติ) ซึ่งเราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่นๆ เช่น C, java, python และภาษาอื่นๆ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
