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

C++ प्रोग्राम: बाइनरी ट्री में पहला सबसे छोटा रूट-टू-लीफ पथ प्रिंट करना


दिए गए बाइनरी ट्री में प्रोग्राम को दिए गए कई पथों में से रूट से लीफ तक का सबसे छोटा पथ ढूंढना होगा।

चूंकि हम ट्री को बाएं से दाएं ट्रैवर्स करते हैं, इसलिए यदि रूट से लीफ तक कई सबसे छोटे पथ हैं तो प्रोग्राम ट्री के बाएं तरफ पहले ट्रैवर्स किए गए सबसे छोटे पथ को प्रिंट करेगा।

हम एक कतार (queue) का उपयोग कर सकते हैं जो लेवल ऑर्डर ट्रैवर्सल का उपयोग करके प्रत्येक लेवल को ट्रैवर्स करेगी और सबसे कम लेवल वाला पथ प्रिंट किया जाएगा क्योंकि यह रूट से लीफ तक का सबसे छोटा पथ होगा।

C++ प्रोग्राम: बाइनरी ट्री में पहला सबसे छोटा रूट-टू-लीफ पथ प्रिंट करना

उपरोक्त ट्री में, रूट से लीफ तक कई पथ हैं

10 -> 3 (यह सभी में सबसे छोटा पथ है) 10 -> 211 -> 100 10 -> 211 -> 146

उदाहरण

Input : 10 3 211 100 146 Output : 10 3

एल्गोरिदम

Step 1 -> create a structure of a node as    struct node       struct node *left, *right       int data    End Step 2 -> function to create a node    node* newnode(int data)    node *temp = new node    temp->data = data    temp->left = temp->right= NULL    return temp Step 3 -> create function for calculating path    void path(int data, unordered_map <int,int> prnt)       IF prnt[data] = data          Return       End       path(prnt[data], prnt)       print prnt[data] step 4 -> function for finding out the left path    void left(Node* root)    create STL queue<Node*> que    que.push(root)    int leaf = -1    Node* temp = NULL    Create STL unordered_map<int, int> prnt    prnt[root->data] = root->data    Loop While !que.empty()       temp = que.front()       que.pop()       IF !temp->left && !temp->right          leaf = temp->data          break       End       Else          IF temp->left             que.push(temp->left)             prnt[temp->left->data] = temp->data          End          IF temp->right             que.push(temp->right)             prnt[temp->right->data] = temp->data          End       End    End    path(leaf, prnt)    print leaf Step 5 -> In main()    Create tree using Node* root = newnode(90)    root->left = newnode(21)    call left(root) stop

उदाहरण

#include <bits/stdc++.h> using namespace std; // structure of a node struct Node {    struct Node *left,*right;    int data; }; //function to create a new node Node* newnode(int data){    Node* temp = new Node;    temp->data = data;    temp->left = NULL;    temp->right = NULL;    return temp; } //function to set a path void path(int data, unordered_map <int,int> prnt) {    if (prnt[data] == data)       return;    path(prnt[data], prnt);    cout << prnt[data] << " "; } //function for a leaf path void left(Node* root) {    queue<Node*> que;    que.push(root);    int leaf = -1;    Node* temp = NULL;    unordered_map<int, int> prnt;    prnt[root->data] = root->data;    while (!que.empty()){       temp = que.front();       que.pop();       if (!temp->left && !temp->right{          leaf = temp->data;          break;       } else {          if (temp->left){             que.push(temp->left);             prnt[temp->left->data] = temp->data;          }          if (temp->right){             que.push(temp->right);             prnt[temp->right->data] = temp->data;          }       }    }    path(leaf, prnt);    cout << leaf << " "; } int main(){    Node* root = newnode(90);    root->left = newnode(21);    root->right = newnode(32);    root->left->left = newnode(45);    root->right->left = newnode(52);    root->right->right = newnode(27);    root->left->left->left = newnode(109);    root->left->left->right = newnode(101);    root->right->right->left = newnode(78);    left(root);    return 0; }

आउटपुट

यदि हम उपरोक्त प्रोग्राम चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा

90 32 52

  1. C++ प्रोग्राम: ट्री के विषम लेवल पर नोड्स प्रिंट करना C++ प्रोग्राम: ट्री के विषम लेवल पर नोड्स प्रिंट करना

    दिए गए बाइनरी ट्री में, प्रोग्राम को ट्री के विषम लेवल पर नोड्स प्रिंट करने होंगे और बाइनरी ट्री के लेवल 1 से n तक शुरू होते हैं। चूंकि कुछ उल्लेख नहीं है, दो दृष्टिकोणों में से एक को लागू किया जा सकता है यानी रिकर्सन या इटरेशन। चूंकि हम एक रिकर्सिव दृष्टिकोण का उपयोग कर रहे हैं, प्रोग्राम एक फ़ंक्श

  1. C++ प्रोग्राम: बाइनरी ट्री में सभी नोड्स के लेवल प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री में सभी नोड्स के लेवल प्रिंट करना

    दिए गए बाइनरी ट्री में, कार्य 1 से n तक शुरू होने वाले प्रत्येक कुंजी से जुड़े लेवल को प्रिंट करना है जो एक नोड में संग्रहीत है। उपरोक्त ट्री में नोड्स हैं - 10 at level 1 3 and 211 at level 2 140, 162, 100 and 146 at level 3 दिए गए कुंजी के लिए प्रोग्राम को उस विशेष कुंजी का लेवल प्रिंट करना होगा।

  1. C++ प्रोग्राम: बाइनरी ट्री के प्रत्येक नोड में सेट बिट्स की संख्या प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री के प्रत्येक नोड में सेट बिट्स की संख्या प्रिंट करना

    दिए गए बाइनरी ट्री में, फ़ंक्शन नोड्स में संग्रहीत कुंजियों के बाइनरी मान उत्पन्न करेगा और फिर उस बाइनरी समतुल्य में सेट बिट्स (1) की संख्या लौटाएगा। उदाहरण बाइनरी ट्री जिसमें कुंजियां हैं: 10 3 211 140 162 100 और 146 कुंजी बाइनरी समतुल्य सेट बिट्स (आउटपुट) 10 1010 2 3 0011 2 211 1101001