C++ में बाइनरी ट्री का विकर्ण योग (Diagonal Sum)

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

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

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

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

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

अगला, diagonal_sum(Node *root, int depth, map<int, int> &diagonalSum) रूट नोड, वर्तमान गहराई और रेफरेंस द्वारा diagonalSum मैप लेता है। यदि रूट NULL नहीं है तो हम वर्तमान रूट डेटा को diagonalSum मैप में वर्तमान गहराई सूचकांक पर जोड़ते हैं ताकि तत्वों का योग प्राप्त हो सके। हम फिर ट्री पर रिकर्सिव इनऑर्डर ट्रैवर्सल करते हैं और जब भी हम बाएं चाइल्ड पर जाते हैं तो गहराई में 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 है और sumMap को diagonal_sum भेजा जाता है जहां sumMap कुंजी-मान जोड़े से भर जाता है। अगला हम sumMap मैप पर पुनरावृति करने के लिए अपना इटरेटर it बनाते हैं।

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;

अंत में हम इटरेटर 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; 
}

आउटपुट

उपरोक्त कोड निम्नलिखित आउटपुट देगा:

9 19 4 2