सी++ में बाइनरी ट्री में सबसे गहरे विषम स्तर के नोड की गहराई?

आइए पहले उस संरचना को परिभाषित करें जो एक ट्री नोड का प्रतिनिधित्व करेगी जिसमें int कुंजी और उसके बाएँ और दाएँ नोड बच्चे शामिल हैं। यदि यह बनाया जाने वाला पहला नोड है तो यह एक रूट नोड है अन्यथा एक चाइल्ड नोड है।

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

इसके बाद हम अपना createNode(int key) फंक्शन बनाते हैं जो एक इंट की वैल्यू लेता है और इसे नोड के प्रमुख सदस्य को असाइन करता है। फ़ंक्शन पॉइंटर को बनाए गए स्ट्रक्चर नोड पर लौटाता है। साथ ही, नव निर्मित नोड के बाएँ और दाएँ बच्चे को शून्य पर सेट किया गया है।

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);
}

सबसे गहराOddLvlDepth(नोड *currentNode, int currentLevel=0) currentNode और currentLevel लेता है। currentLevel का डिफ़ॉल्ट मान 0 है, यदि कोई मान पास नहीं किया गया है। यदि currentNode शून्य है तो फ़ंक्शन 0.

int deepestOddLvlDepth(Node *currentNode, int currentLevel=0){
   if ( currentNode == NULL)
      return 0;

जब तक आधार शर्त पूरी नहीं हो जाती, तब तक प्रत्येक रिकर्सन स्तर पर वर्तमान स्तर को 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