C++ এ একটি বাইনারি গাছের তির্যক সমষ্টি?

ঢাল -1 লাইনের মধ্যবর্তী নোডগুলি বিবেচনা করা। বাইনারি গাছের তির্যক যোগফল এই রেফারেন্সের লাইনের মধ্যে উপস্থিত সমস্ত নোড ডেটার যোগফল দ্বারা গণনা করা হবে৷

আসুন প্রথমে স্ট্রাকটটি সংজ্ঞায়িত করি যা একটি ট্রি নোডকে প্রতিনিধিত্ব করবে যেখানে ডেটা এবং এর বাম এবং ডান নোড চাইল্ড রয়েছে। যদি এটি তৈরি করা প্রথম নোড হয় তবে এটি একটি রুট নোড অন্যথায় একটি চাইল্ড নোড।

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

এরপরে আমরা আমাদের createNode(int data) ফাংশন তৈরি করি যা একটি int মান নেয় এবং নতুন নোড তৈরি করার পরে নোডের ডেটা মেম্বারকে বরাদ্দ করি। ফাংশনটি তৈরি করা নোডে পয়েন্টার ফিরিয়ে দেয়।

Node * createNode(int data){
   Node * node = new Node;
   node->data = data;
   return node;
}

এরপরে, diagonal_sum(Node *root, int depth, map &diagonalSum) রেফারেন্স দ্বারা রুট নোড, বর্তমান গভীরতা এবং diagonalSum মানচিত্র নেয়। যদি রুটটি NULL না হয় তবে আমরা উপাদানগুলির যোগফল পেতে diagonalSum মানচিত্রে বর্তমান গভীরতার সূচকে বর্তমান রুট ডেটা যোগ করি। তারপরে আমরা গাছে একটি রিকার্সিভ ইনঅর্ডার ট্রাভার্সাল করি এবং যখনই আমরা ট্রি-এ যাই তখন গভীরতায় 1 যোগ করি। বাম সন্তান।

void diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum){
   if(root){
      diagonalSum[depth]+=root->data;
      diagonal_sum(root->leftChild, depth+1, diagonalSum);
      diagonal_sum(root->rightChild, depth, diagonalSum);
   }
}

আমাদের প্রধান ফাংশনের ভিতরে আমরা createNode(data) পদ্ধতি ব্যবহার করে একটি ট্রি তৈরি করি এবং একটি মানচিত্র SumMap তৈরি করি। রুট নোড , বর্তমান গভীরতা 1 এবং sumMap diagonal_sum-এ পাঠানো হয় যেখানে sumMap কী-মান জোড়া দিয়ে পূর্ণ হয়। পরবর্তীতে আমরা sumMap মানচিত্রের উপর পুনরাবৃত্তি করার জন্য আমাদের পুনরাবৃত্তিকারী এটি তৈরি করি।

int main(){
   Node *root = createNode(1);
   root->rightChild = createNode(3);
   root->rightChild->leftChild = createNode(4);
   root->rightChild->leftChild->leftChild = createNode(12);
   root->rightChild->leftChild->rightChild = createNode(7);
   root->leftChild = createNode(2);
   root->leftChild->leftChild = createNode(9);
   root->leftChild->rightChild = createNode(6);
   root->leftChild->leftChild->rightChild = createNode(10);
   root->leftChild->rightChild->leftChild = createNode(11);
   root->rightChild->rightChild = createNode(5);
   map<int,int> sumMap;
   diagonal_sum(root, 1, sumMap);
   map<int,int>::iterator it;

অবশেষে আমরা আমাদের সামম্যাপে এটিকে আমাদের ফর লুপের ভিতরে ইটারেটর ব্যবহার করে পুনরাবৃত্তি করি এবং তির্যক যোগফল প্রিন্ট করি।

for(it=sumMap.begin(); it!=sumMap.end();++it){
   int value = it->second;
   cout<<value<<"\t";
}

উদাহরণ

একটি বাইনারি গাছের তির্যক যোগফল খুঁজে বের করার জন্য আমরা নিম্নলিখিত বাস্তবায়ন দেখি।

#include<iostream>
#include<map>
using namespace std;
struct Node{
   int data;
   struct Node* leftChild, *rightChild;
};
Node * createNode(int data){
   Node * node = new Node;
   node->data = data;
   return node;
}
void diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum){
   if(root){
      diagonalSum[depth]+=root->data;
      diagonal_sum(root->leftChild, depth+1, diagonalSum);
      diagonal_sum(root->rightChild, depth, diagonalSum);
   }
}
int main(){
   Node *root = createNode(1);
   root->rightChild = createNode(3);
   root->rightChild->leftChild = createNode(4);
   root->rightChild->leftChild->leftChild = createNode(12);
   root->rightChild->leftChild->rightChild = createNode(7);
   root->leftChild = createNode(2);
   root->leftChild->leftChild = createNode(9);
   root->leftChild->rightChild = createNode(6);
   root->leftChild->leftChild->rightChild = createNode(10);
   root->leftChild->rightChild->leftChild = createNode(11);
   root->rightChild->rightChild = createNode(5);
   map<int,int> sumMap;
   diagonal_sum(root, 1, sumMap);
   map<int,int>::iterator it;
   for(it=sumMap.begin(); it!=sumMap.end();++it){
      int value = it->second;
      cout<<value<<"\t";
   }
   return 0;
}

আউটপুট

উপরের কোডটি নিম্নলিখিত আউটপুট −

91942