आइए पहले उस स्ट्रक्ट को परिभाषित करें जो एक ट्री नोड को दर्शाता है जिसमें int key और इसके बाएं और दाएं चाइल्ड नोड होते हैं। यदि यह बनाया जाने वाला पहला नोड है तो यह रूट नोड है अन्यथा चाइल्ड नोड।
struct Node {
int data;
struct Node *leftChild, *rightChild;
};
इसके बाद हम createNode(int key) फंक्शन बनाते हैं जो एक int key मान लेता है और इसे नोड के key सदस्य को असाइन करता है। फंक्शन बने हुए स्ट्रक्ट Node का पॉइंटर वापस करता है। साथ ही, नव निर्मित नोड के बाएं और दाएं चाइल्ड को null पर सेट किया जाता है।
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) currentNode और currentLevel लेता है। currentLevel का डिफ़ॉल्ट मान 0 है यदि कोई मान पास नहीं किया जाता। यदि currentNode null है तो फंक्शन 0 वापस करता है।
int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
if (currentNode == NULL)
return 0;
प्रत्येक रिकर्सन स्तर पर currentLevel को 1 से बढ़ाया जाता है जब तक आधार स्थिति पूरी नहीं हो जाती। हम फिर जांचते हैं कि क्या currentNode एक विषम लीफ नोड है। बाएं और दाएं चाइल्ड को तब तक पार किया जाता है जब तक हमें हमारे सबसे गहरे विषम स्तर के लीफ नोड की गहराई नहीं मिल जाती। बाएं चाइल्ड की गहराई और दाएं चाइल्ड की गहराई का अधिकतम मुख्य फंक्शन को परिणाम प्रिंट करने के लिए वापस किया जाता है।
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
