একটি গাছ দেওয়া হয়েছে, এবং আমাদের প্রদত্ত k-এর চেয়ে কম দৈর্ঘ্যের পথের পাতার নোডটি সরাতে হবে, উদাহরণস্বরূপ।
ইনপুট -
K = 4.
আউটপুট -
ব্যাখ্যা
The paths were : 1. A -> B -> C -> E length = 4 2. A -> B -> C -> F length = 4 3. A -> B -> D length = 3 4. A -> G -> H length = 3 5. A -> B -> I length = 3 Now as you can see paths 3, 4, 5 have length of 3 which is less than given k so we remove the leaf nodes of these paths i.e. D, H, I. Now for path 4 and 5 when H and I are removed we notice that now G is also a leaf node with path length 2 so we again remove node G and here our program ends.
আমরা পোস্ট-অর্ডার বিন্যাসে গাছটি অতিক্রম করব; তারপর, আমরা একটি পুনরাবৃত্ত ফাংশন তৈরি করি যা আমাদের পাতার নোডগুলিকে সরিয়ে দেয় যদি তাদের পথের দৈর্ঘ্য K-এর চেয়ে কম হয়।
সমাধান খোঁজার পদ্ধতি
এই পদ্ধতিতে, আমরা এখন পোস্ট-অর্ডার ট্রাভার্সালে অতিক্রম করি; আমরা পুনরাবৃত্তভাবে লিফ নোডগুলিকে অপসারণ করার চেষ্টা করি যেগুলির পাথের দৈর্ঘ্য k-এর চেয়ে কম এবং এভাবে চালিয়ে যান৷
উদাহরণ
উপরের পদ্ধতির জন্য C++ কোড
#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure of our node
char data;
Node *left, *right;
};
Node *newNode(int data){ // inserting new node
Node *node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
Node *trimmer(Node *root, int len, int k){
if (!root) // if root == NULL then we return
return NULL;
root -> left = trimmer(root -> left, len + 1, k); // traversing the left phase
root -> right = trimmer(root -> right, len + 1, k); // traversing the right phase
if (!root -> left && !root -> right && len < k){
delete root;
return NULL;
}
return root;
}
Node *trim(Node *root, int k){
return trimmer(root, 1, k);
}
void printInorder(Node *root){
if (root){
printInorder(root->left);
cout << root->data << " ";
printInorder(root->right);
}
}
int main(){
int k = 4;
Node *root = newNode('A');
root->left = newNode('B');
root->right = newNode('G');
root->left->left = newNode('C');
root->left->right = newNode('D');
root->left->left->left = newNode('E');
root->left->left->right = newNode('F');
root->right->left = newNode('H');
root->right->right = newNode('I');
printInorder(root);
cout << "\n";
root = trim(root, k);
printInorder(root);
return 0;
} আউটপুট
E C F B D A H G I E C F B A
উপরের কোডের ব্যাখ্যা
এই কোডে, আমরা একটি পুনরাবৃত্ত ফাংশন ব্যবহার করছি যা আমাদের গাছকে অতিক্রম করছে এবং বাম এবং ডান উপবৃক্ষের পরিসংখ্যান রাখছে। এখন আমরা একটি লিফ নোডে পৌঁছেছি; আমরা সেই নোড পর্যন্ত পথের দৈর্ঘ্য পরীক্ষা করি। যদি পথের দৈর্ঘ্য কম হয়, তাহলে আমরা এই নোডটি মুছে ফেলি, এবং তারপরে আমরা NULL ফেরত দিই; অন্যথায়, কোড চলতে থাকে।
উপসংহার
এই টিউটোরিয়ালে, আমরা রিকারশন ব্যবহার করে
