সি++-এ বাইনারি ট্রির ডায়াগোনাল যোগফল

স্লপ -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<int, int> &diagonalSum) রুট নোড, বর্তমান ডেপথ এবং রেফারেন্স হিসেবে diagonalSum ম্যাপ নেয়। যদি রুট NULL না হয় তবে বর্তমান রুট ডেটা বর্তমান ডেপথ ইন্ডেক্সে diagonalSum ম্যাপে যোগ করি যাতে এলিমেন্টগুলোর যোগফল পাওয়া যায়। তারপর রিকার্সিভ ইনঅর্ডার ট্রাভার্সাল করি ট্রিতে এবং যখন বাম চাইল্ডে যাই তখন ডেপথে ১ যোগ করি।

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 তৈরি করি। রুট নোড, বর্তমান ডেপথ যেটি ১ এবং sumMap diagonal_sum-এ পাঠানো হয় যেখানে sumMap কি-ভ্যালু পেয়ার দিয়ে ভরা হয়। পরবর্তে আমরা আমাদের ইটেরেটর it তৈরি করি 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;

শেষে আমরা ইটেরেটর it ব্যবহার করে ফর লুপে SumMap-এ ইটারেট করি এবং ডায়াগোনাল যোগফলগুলো প্রিন্ট করি।

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