আসুন প্রথমে struct সংজ্ঞায়িত করি যা একটি ট্রি নোডকে প্রতিনিধিত্ব করবে যাতে int কী এবং এর বাম এবং ডান নোড চাইল্ড রয়েছে। যদি এটি তৈরি করা প্রথম নোড হয় তবে এটি একটি রুট নোড অন্যথায় একটি চাইল্ড নোড।
struct Node {
int data;
struct Node *leftChild, *rightChild;
}; এর পরে আমরা আমাদের createNode(int কী) ফাংশন তৈরি করি যা একটি int কী মান নেয় এবং এটি নোডের মূল সদস্যকে বরাদ্দ করি। ফাংশন তৈরি করা স্ট্রাকট নোডে পয়েন্টার ফিরিয়ে দেয়। এছাড়াও, নতুন তৈরি নোডের বাম এবং ডান চাইল্ড নাল সেট করা হয়েছে৷
৷Node* createNode(int data){
Node* node = new Node;
node->data = data;
node->leftChild = node->rightChild = NULL;
return node;
} এরপরে আমাদের isLeaf(Node *currentNode) ফাংশন রয়েছে যা একটি নোড নেয় এবং এটির কোনো সন্তান আছে কি না তা পরীক্ষা করে। নোডটি লিফ নোড বা না হলে এটি সত্য বা মিথ্যা ভিত্তিক ফেরত দেয়৷
bool isLeaf(Node *currentNode){
return (currentNode->leftChild == NULL &&
currentNode->rightChild == NULL);
} deepestOddLvlDepth(Node *currentNode, int currentLevel=0) কারেন্ট নোড এবং বর্তমান লেভেল নেয়। বর্তমান লেভেলের ডিফল্ট মান 0 থাকে যদি এতে কোনো মান পাস না হয়। যদি বর্তমান নোডটি শূন্য হয় তবে ফাংশনটি 0 প্রদান করে।
int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
if ( currentNode == NULL)
return 0; ভিত্তি শর্ত পূরণ না হওয়া পর্যন্ত বর্তমান স্তর প্রতিটি পুনরাবৃত্তি স্তরে 1 দ্বারা বৃদ্ধি করা হয়। আমরা তারপর কারেন্টনোডটি একটি বিজোড় পাতার নোড কিনা তা পরীক্ষা করি। তারপরে বাম এবং ডানচাইল্ডকে অতিক্রম করা হয় যতক্ষণ না আমরা আমাদের গভীরতম বিজোড় স্তরের পাতার নোডের গভীরতা খুঁজে পাই। ফলাফল প্রিন্ট করার জন্য লেফটচাইল্ডডেপথ এবং রাইটচাইল্ড ডেপথের সর্বোচ্চ মূল ফাংশনে ফিরিয়ে দেওয়া হয়।
int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
if ( currentNode == NULL)
return 0;
currentLevel ++;
if ( currentLevel % 2 != 0 && isLeaf(currentNode))
return currentLevel;
int leftChildLevel = deepestOddLvlDepth(currentNode->leftChild,currentLevel);
int rightChildLevel = deepestOddLvlDepth(currentNode->rightChild,currentLevel);
return max(leftChildLevel,rightChildLevel);
} উদাহরণ
বাইনারি ট্রিতে গভীরতম বিজোড় স্তরের নোডের গভীরতা খুঁজে পেতে আমরা নিম্নলিখিত বাস্তবায়নটি দেখি৷
#include<iostream>
using namespace std;
struct Node{
int key;
struct Node *leftChild, *rightChild;
};
Node* createNode(int key){
Node* node = new Node;
node->key = key;
node->leftChild = node->rightChild = NULL;
return node;
}
bool isLeaf(Node *currentNode){
return (currentNode->leftChild == NULL &&
currentNode->rightChild == NULL);
}
int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
if ( currentNode == NULL)
return 0;
currentLevel ++;
if ( currentLevel % 2 != 0 && isLeaf(currentNode))
return currentLevel;
int leftChildLevel = deepestOddLvlDepth(currentNode->leftChild,currentLevel);
int rightChildLevel = deepestOddLvlDepth(currentNode->rightChild,currentLevel);
return max(leftChildLevel,rightChildLevel);
}
int main(){
Node *root = createNode(15);
root->leftChild = createNode(33);
root->rightChild = createNode(18);
root->rightChild->leftChild = createNode(19);
root->rightChild->rightChild = createNode(20);
root->rightChild->rightChild->leftChild = createNode(28);
root->rightChild->rightChild->rightChild = createNode(29);
cout << "The depth of the deepest odd level leaf node is: "<<deepestOddLvlDepth(root) << endl;
return 0;
} আউটপুট
উপরের কোডটি নিম্নলিখিত আউটপুট তৈরি করবে।
The depth of the deepest odd level leaf node is: 3
