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

স্লপ -1-এর লাইনগুলোর মাঝপথে যেসব নোড পড়ে সেগুলো বিবেচনা করতে হবে। বাইনারি ট্রির ডায়াগোনাল ট্রাভার্সাল হলো সেই লাইনগুলোর মাঝপথে থাকা সব নোড ট্রাভার্স ও প্রিন্ট করা।

প্রথমে স্ট্রাক্ট ডিফাইন করি যা ট্রি নোড রিপ্রেজেন্ট করবে যাতে ডেটা এবং এর বাম ও ডান চাইল্ড নোড থাকে। যদি এটি প্রথম নোড হয় তবে এটি রুট নোড হবে অন্যথায় চাইল্ড নোড।

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

পরবর্তীতে createNode(int data) ফাংশন তৈরি করি যা একটি int মান নেয় এবং সেটি নোডের ডেটা মেম্বরে অ্যাসাইন করে। ফাংশনটি তৈরি হওয়া struct Node-এর পয়েন্টার ফেরত দেয়। এছাড়া নতুন নোডের বাম ও ডান চাইল্ড নাল সেট করা হয়।

struct Node* newNode(int data){ 
    struct Node* node = new Node(); 
    node->data = data; 
    node->leftChild = node->rightChild = NULL; 
    return node; 
}

traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap) ফাংশন আমাদের রুট নোড, বর্তমান ডেপথ এবং একটি ম্যাপ নেয় যাতে int ভ্যালু কি এবং vector of int ভ্যালু থাকে। myMap কে রেফারেন্স হিসেবে এই ফাংশনে পাস করা হয়। ফাংশনটি চেক করে রুট নাল কিনা এবং যদি না হয় তবে রুট->ডেটা এলিমেন্টটি বর্তমান ডেপথে ভেক্টর ডেটা স্ট্রাকচারের পিছনে পুশ করে ইনঅর্ডার ট্রাভার্সাল ajal।

void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &m){ 
    if(root){ 
        m[depth].push_back(root->data);

তারপর রিকার্সিভ ইনঅর্ডার ট্রাভার্সাল করি ট্রি ট্র্যাক করা ডায়াগোনাল ডিস্ট্যান্স এবং যখন বাম চাইল্ড ট্রাভার্স করি তখন ডেপথে ১ যোগ করি। ডান চাইল্ড ট্রাভার্স করার সময় ডেপথে কিছু যোগ করা হয় না।

traverseDiagonal(root->leftChild, depth+1, myMap); 
traverseDiagonal(root->rightChild, depth, myMap);

পরবর্তীতে, মেইন ফাংশনে আমরা createNode(data) ফাংশন ব্যবহার করে ট্রি তৈরি করি।

Node *root = createNode(10); 
root->leftChild = createNode(5); 
root->rightChild = createNode(15); 
root->leftChild->leftChild = createNode(4); 
root->leftChild->rightChild = createNode(6); 
root->rightChild->rightChild = createNode(17); 
root->rightChild->rightChild->leftChild = createNode(16);

তারপর একটি ম্যাপ myMap ডিক্লেয়ার করি যাতে int কি এবং vector of int ভ্যালু থাকে। এই ম্যাপকে traverseDiagonal-এ রুট নোড এবং বর্তমান ডেপথের সাথে পাস করি।

map<int, vector<int>> myMap; 
traverseDiagonal(root, 0, myMap);

myMap মান দিয়ে ভরলে আমরা রেঞ্জ-বেসড ফর লুপ দিয়ে ইটারেট করি এবং ডায়াগোনাল ভ্যালুগুলো প্রিন্ট করি।

for(auto k: myMap){ 
    for(auto Nodes: k.second) 
        cout<<Nodes<<" "; 
    cout<<endl; 
}

উদাহরণ

বাইনারি ট্রির ডায়াগোনাল ট্রাভার্সাল বের করার ইমপ্লিমেন্টেশন:

#include <iostream> 
#include <map> 
#include <vector> 
using namespace std; 

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

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

void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap){ 
    if(root){ 
        m[depth].push_back(root->data); 
        traverseDiagonal(root->leftChild, depth+1, myMap); 
        traverseDiagonal(root->rightChild, depth, myMap); 
    } 
} 

int main(){ 
    Node *root = createNode(10); 
    root->leftChild = createNode(5); 
    root->rightChild = createNode(15); 
    root->leftChild->leftChild = createNode(4); 
    root->leftChild->rightChild = createNode(6); 
    root->rightChild->rightChild = createNode(17); 
    root->rightChild->rightChild->leftChild = createNode(16); 
    map<int, vector<int>> myMap; 
    traverseDiagonal(root, 0, myMap); 
    for(auto k: myMap){ 
        for(auto Nodes: k.second) 
            cout<<Nodes<<" "; 
        cout<<endl; 
    } 
}

আউটপুট

10 15 17 5 6 16 4