सी ++ में एक बाइनरी ट्री का विकर्ण योग?

ढलान -1 की रेखाओं के बीच से गुजरने वाले नोड्स पर विचार करना। बाइनरी ट्री के विकर्ण योग की गणना उन सभी नोड्स डेटा के योग से की जाएगी जो संदर्भ की इन पंक्तियों के बीच मौजूद हैं।

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

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

इसके बाद हम अपना createNode(int data) फंक्शन बनाते हैं जो एक इंट वैल्यू लेता है और नया नोड बनाने के बाद इसे नोड के डेटा मेंबर को असाइन करता है। फ़ंक्शन पॉइंटर को बनाए गए नोड पर लौटाता है।

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

इसके बाद, विकर्ण_सम (नोड *रूट, इंट डेप्थ, मैप<इंट, इंट> और डायगोनलसम) संदर्भ द्वारा रूट नोड, करंट डेप्थ और डायगोनलसम मैप लेता है। यदि रूट न्यूल नहीं है, तो हम तत्वों का योग प्राप्त करने के लिए विकर्णसम मानचित्र में वर्तमान गहराई सूचकांक में वर्तमान रूट डेटा जोड़ते हैं। हम तब पेड़ पर एक पुनरावर्ती इनऑर्डर ट्रैवर्सल करते हैं और जब भी हम आगे बढ़ते हैं तो गहराई में 1 जोड़ते हैं। बाएं बच्चे।

void diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum){
   if(root){
      diagonalSum[depth]+=root->data;
      diagonal_sum(root->leftChild, depth+1, diagonalSum);
      diagonal_sum(root->rightChild, depth, diagonalSum);
   }
}

हमारे मुख्य कार्य के अंदर हम createNode(data) विधि का उपयोग करके एक ट्री बनाते हैं और एक नक्शा SumMap भी बनाते हैं। रूट नोड , वर्तमान गहराई जो 1 है और सममैप को विकर्ण_सम पर भेजा जाता है जहां समपाइप की-वैल्यू पेयर से भरा होता है। इसके बाद हम अपना पुनरावर्तक इसे सममैप मानचित्र पर पुनरावृत्त करने के लिए बनाते हैं।

int main(){
   Node *root = createNode(1);
   root->rightChild = createNode(3);
   root->rightChild->leftChild = createNode(4);
   root->rightChild->leftChild->leftChild = createNode(12);
   root->rightChild->leftChild->rightChild = createNode(7);
   root->leftChild = createNode(2);
   root->leftChild->leftChild = createNode(9);
   root->leftChild->rightChild = createNode(6);
   root->leftChild->leftChild->rightChild = createNode(10);
   root->leftChild->rightChild->leftChild = createNode(11);
   root->rightChild->rightChild = createNode(5);
   map<int,int> sumMap;
   diagonal_sum(root, 1, sumMap);
   map<int,int>::iterator it;

अंत में हम अपने लूप के लिए इटरेटर का उपयोग करके अपने SumMap पर पुनरावृति करते हैं और विकर्ण योगों को प्रिंट करते हैं।

for(it=sumMap.begin(); it!=sumMap.end();++it){
   int value = it->second;
   cout<<value<<"\t";
}

उदाहरण

आइए हम एक बाइनरी ट्री के विकर्ण योग को खोजने के लिए निम्नलिखित कार्यान्वयन देखें।

#include<iostream>
#include<map>
using namespace std;
struct Node{
   int data;
   struct Node* leftChild, *rightChild;
};
Node * createNode(int data){
   Node * node = new Node;
   node->data = data;
   return node;
}
void diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum){
   if(root){
      diagonalSum[depth]+=root->data;
      diagonal_sum(root->leftChild, depth+1, diagonalSum);
      diagonal_sum(root->rightChild, depth, diagonalSum);
   }
}
int main(){
   Node *root = createNode(1);
   root->rightChild = createNode(3);
   root->rightChild->leftChild = createNode(4);
   root->rightChild->leftChild->leftChild = createNode(12);
   root->rightChild->leftChild->rightChild = createNode(7);
   root->leftChild = createNode(2);
   root->leftChild->leftChild = createNode(9);
   root->leftChild->rightChild = createNode(6);
   root->leftChild->leftChild->rightChild = createNode(10);
   root->leftChild->rightChild->leftChild = createNode(11);
   root->rightChild->rightChild = createNode(5);
   map<int,int> sumMap;
   diagonal_sum(root, 1, sumMap);
   map<int,int>::iterator it;
   for(it=sumMap.begin(); it!=sumMap.end();++it){
      int value = it->second;
      cout<<value<<"\t";
   }
   return 0;
}

आउटपुट

उपरोक्त कोड निम्न आउटपुट उत्पन्न करेगा -