আসুন আমরা বিবেচনা করি যে আমাদের কাছে একটি বাইনারি গাছের মূল নোড আছে; কাজটি হল প্রতিটি নোডের টিল্টের যোগফল খুঁজে বের করা এবং ফেরত দেওয়া।
কাত একটি বাইনারি ট্রি বাইনারি ট্রি তৈরি করা ছাড়া আর কিছুই নয় বাম সাবট্রিতে চাইল্ড নোড এবং প্রতিটি লেভেলে ডান সাবট্রিতে নিখুঁত পার্থক্য খুঁজে বের করার মাধ্যমে। কিছু নির্দিষ্ট স্তরে, যে নোডগুলিতে কোনও চাইল্ড নোড নেই, আমরা কেবল সেই নোডটিকে শূন্য দিয়ে প্রতিস্থাপন করে কাত করি।
উদাহরণ
ইনপুট
আউটপুট:15
ব্যাখ্যা: প্রদত্ত বাইনারি গাছের প্রতিটি স্তরে কাত খোঁজা,
নোড 3 =0
এর কাতনোড 5 =0
এর কাতনোড 7 =0
এর কাতনোড 2 =abs(3-5)=2
এর কাতনোড 9 এর কাত =abs(0-7)=7
নোড 4 এর কাত =abs((3+5+2)- (9+7))=6
সমস্ত নোডের কাত হওয়ার যোগফল =2+7+6=15
এই সমস্যা সমাধানের পদ্ধতি
এই বিশেষ সমস্যা সমাধানের সহজ পদ্ধতি হল পোস্ট অর্ডার ব্রেডথ ফার্স্ট সার্চ ট্রাভার্সাল ব্যবহার করা।
বাইনারি ট্রিটি অতিক্রম করার সময়, আমরা এর বাম সাবট্রি এবং তারপর ডান সাবট্রির সমস্ত নোডের যোগফল খুঁজে বের করার চেষ্টা করব। একবার যোগফল পাওয়া গেলে, আমরা তার বাম যোগফল এবং উপবৃক্ষের ডান যোগফলের পরম পার্থক্য গণনা করে সমস্ত নোডের কাত খুঁজে পাব।
- একটি বাইনারি ট্রি নিন, যেটি হবে ইনপুট।
- একটি পূর্ণসংখ্যা ফাংশন sumNodes(treenode*node) গাছের রুট নোড নেয় এবং বাম সাবট্রি এবং ডান সাবট্রির যোগফল প্রদান করে।
- একটি পূর্ণসংখ্যা ফাংশন findTilt(treenode*root) রুট নোডকে ইনপুট প্যারামিটার হিসেবে নেয় এবং সমস্ত নোডের টিল্টের যোগফল প্রদান করে।
উদাহরণ
#include<iostream>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
int sumNodes(treenode * root, int & sum) {
if (root == NULL) return 0;
int lsum = sumNodes(root -> left, sum);
int rsum = sumNodes(root -> right, sum);
sum += abs(lsum - rsum);
return lsum + rsum + root -> data;
}
int findTilt(treenode * root) {
int sum = 0;
if (root == NULL) {
return 0;
}
sumNodes(root, sum);
return sum;
}
int main() {
struct treenode * root = NULL;
root = createNode(4);
root -> left = createNode(2);
root -> right = createNode(9);
root -> left -> right = createNode(5);
root -> left -> left = createNode(3);
root -> right -> right = createNode(7);
cout << findTilt(root) << endl;
return 0;
} উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,
আউটপুট
15
প্রদত্ত বাইনারি ট্রিতে, গাছের প্রতিটি স্তরে সমস্ত নোডের কাত হওয়ার যোগফল হল 15৷
