Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में बाइनरी ट्री का विकर्ण ट्रैवर्सल (Diagonal Traversal)


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

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

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

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

struct Node* newNode(int data){ 
    struct Node* node = new Node(); 
    node->data = data; 
    node->leftChild = node->rightChild = NULL; 
    return node; 
}

traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap) फंक्शन हमारा रूट नोड, वर्तमान गहराई और एक मैप लेता है जिसमें int मान कुंजी के रूप में और int का वेक्टर मान के रूप में होता है। हम myMap को इस फंक्शन में रेफरेंस द्वारा पास करते हैं। फंक्शन फिर जांचता है कि रूट null है या नहीं और यदि नहीं है तो हम इनऑर्डर ट्रैवर्सल करते हुए वर्तमान गहराई पर अपने वेक्टर डेटा स्ट्रक्चर के पीछे रूट->डेटा तत्व को पुश करते हैं।

void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &m){ 
    if(root){ 
        m[depth].push_back(root->data);

हम फिर ट्री का रिकर्सिव इनऑर्डर ट्रैवर्सल करते हैं विकर्ण दूरी को ट्रैक करते हुए और जब भी हम ट्री के बाएं चाइल्ड को पार करते हैं तो गहराई में 1 जोड़ते हैं। जब हम ट्री के दाएं चाइल्ड को पार करते हैं तो गहराई में कुछ नहीं जोड़ते।

traverseDiagonal(root->leftChild, depth+1, myMap); 
traverseDiagonal(root->rightChild, depth, myMap);

अगला, हमारे मुख्य फंक्शन में हम createNode(data) फंक्शन का उपयोग करके ट्री बनाते हैं।

Node *root = createNode(10); 
root->leftChild = createNode(5); 
root->rightChild = createNode(15); 
root->leftChild->leftChild = createNode(4); 
root->leftChild->rightChild = createNode(6); 
root->rightChild->rightChild = createNode(17); 
root->rightChild->rightChild->leftChild = createNode(16);

हम फिर एक मैप myMap घोषित करते हैं जिसमें int कुंजी के रूप में और int का वेक्टर मान के रूप में होता है। यह मैप फिर रूट नोड और वर्तमान गहराई के साथ traverseDiagonal को पास किया जाता है।

map<int, vector<int>> myMap; 
traverseDiagonal(root, 0, myMap);

मैप myMap मानों से भर जाने के बाद हम रेंज-आधारित फॉर लूप का उपयोग करके इस पर पुनरावृति करते हैं और उन विकर्ण मानों को प्रिंट करते हैं।

for(auto k: myMap){ 
    for(auto Nodes: k.second) 
        cout<<Nodes<<" "; 
    cout<<endl; 
}

उदाहरण

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

#include <iostream> 
#include <map> 
#include <vector> 
using namespace std; 

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

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

void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap){ 
    if(root){ 
        myMap[depth].push_back(root->data); 
        traverseDiagonal(root->leftChild, depth+1, myMap); 
        traverseDiagonal(root->rightChild, depth, myMap); 
    } 
} 

int main(){ 
    Node *root = createNode(10); 
    root->leftChild = createNode(5); 
    root->rightChild = createNode(15); 
    root->leftChild->leftChild = createNode(4); 
    root->leftChild->rightChild = createNode(6); 
    root->rightChild->rightChild = createNode(17); 
    root->rightChild->rightChild->leftChild = createNode(16); 
    map<int, vector<int>> myMap; 
    traverseDiagonal(root, 0, myMap); 
    for(auto k: myMap){ 
        for(auto Nodes: k.second) 
            cout<<Nodes<<" "; 
        cout<<endl; 
    } 
}

आउटपुट

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

10 15 17 
5 6 16 
4

  1. बाइनरी ट्री के वर्टिकल ऑर्डर ट्रैवर्सल में kवां नोड खोजें C++ में बाइनरी ट्री के वर्टिकल ऑर्डर ट्रैवर्सल में kवां नोड खोजें C++ में

    मान लीजिए हमारे पास एक बाइनरी ट्री और एक मान K है। कार्य वर्टिकल ऑर्डर ट्रैवर्सल में Kवें नोड को प्रिंट करना है। यदि ऐसा कोई नोड मौजूद नहीं है, तो -1 वापस करें। तो यदि ट्री नीचे जैसा है - वर्टिकल ऑर्डर ट्रैवर्सल इस तरह है - 4 2 1 5 6 3 8 7 9 तो यदि K = 3, तो परिणाम 1 होगा। दृष्टिकोण सरल है। हम वर्ट

  1. बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में

    मान लीजिए हमारे पास एक बाइनरी ट्री है। कार्य वर्टिकल ऑर्डर ट्रैवर्सल में सभी नोड्स के योग के अधिकतम को प्रिंट करना है। तो यदि ट्री नीचे जैसा है - वर्टिकल ऑर्डर ट्रैवर्सल इस तरह है - 4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9 यहां अधिकतम 12 है। दृष्टिकोण सरल है। हम वर्टिकल ऑर्डर ट्रैवर्सल करेंगे, फिर योग खोज

  1. C++ में बाइनरी ट्री का एंटी-क्लॉकवाइज स्पाइरल ट्रैवर्सल C++ में बाइनरी ट्री का एंटी-क्लॉकवाइज स्पाइरल ट्रैवर्सल

    बाइनरी ट्री का एंटी-क्लॉकवाइज स्पाइरल ट्रैवर्सल एक ट्री के तत्वों को इस तरह से पार करना है कि यदि पार किया जाए तो वे एक स्पाइरल बनाते हैं लेकिन रिवर्स ऑर्डर में। निम्नलिखित आकृति दिखाती है कि बाइनरी ट्री का एंटी-क्लॉकवाइज स्पाइरल ट्रैवर्सल कैसे होता है। बाइनरी ट्री के स्पाइरल ट्रैवर्सल के लिए परिभ