ঢাল -1 লাইনের মধ্যবর্তী নোডগুলি বিবেচনা করা। বাইনারি ট্রির তির্যক ট্রাভার্সাল হবে এই লাইনগুলির মধ্যে উপস্থিত সমস্ত নোডগুলিকে অতিক্রম করা এবং মুদ্রণ করা৷
আসুন প্রথমে স্ট্রাকটটি সংজ্ঞায়িত করি যা একটি ট্রি নোডকে প্রতিনিধিত্ব করবে যেখানে ডেটা এবং এর বাম এবং ডান নোড চাইল্ড রয়েছে। যদি এটি তৈরি করা প্রথম নোড হয় তবে এটি একটি রুট নোড অন্যথায় একটি চাইল্ড নোড।
struct Node {
int data;
struct Node *leftChild, *rightChild;
}; এরপর আমরা আমাদের createNode(int data) ফাংশন তৈরি করি যা একটি int মান নেয় এবং নোডের ডাটা সদস্যকে বরাদ্দ করি। ফাংশন তৈরি করা স্ট্রাকট নোডে পয়েন্টার ফিরিয়ে দেয়। এছাড়াও, নতুন তৈরি নোডের বাম এবং ডান চাইল্ড নাল সেট করা হয়েছে৷
৷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
void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &m){
if(root){
m[depth].push_back(root->data); তারপরে আমরা তির্যক দূরত্ব ট্র্যাক করে গাছের একটি পুনরাবৃত্ত ইনঅর্ডার ট্রাভার্সাল করি এবং যখনই আমরা গাছের বাম শিশুটি অতিক্রম করি তখন গভীরতায় 1 যোগ করি। যখন আমরা গাছের সঠিক বাচ্চাটি অতিক্রম করি তখন আমরা গভীরতার সাথে কিছু যোগ করি না।
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 কী হিসাবে এবং মান হিসাবে int-এর ভেক্টর রয়েছে। এই মানচিত্রটি তারপরে রুট নোড এবং বর্তমান গভীরতার সাথে ট্রাভার্সডায়াগন্যালে পাস করা হয়।
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
