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

C++ में ट्री में दिए गए उपट्री के DFS ट्रैवर्सल में K-वां नोड ज्ञात करें


इस समस्या में, हमें आकार N का एक ट्री, ट्री का एक नोड V और k दिया गया है। हमारा कार्य ट्री में दिए गए उपट्री के DFS ट्रैवर्सल में K-वां नोड ज्ञात करना है।

हमें शीर्ष V से शुरू होने वाले ट्री के DFS ट्रैवर्सल में k-वां नोड ढूंढना है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट :

C++ में ट्री में दिए गए उपट्री के DFS ट्रैवर्सल में K-वां नोड ज्ञात करें

V = 2, k = 3

आउटपुट : 4

व्याख्या −

श्रृंखला है {1, 2, 3, 5, 6, 7} 4वां तत्व 5 है।

समाधान दृष्टिकोण

समस्या का एक सरल समाधान नोड V के DFS ट्रैवर्सल को ढूंढना और इससे k-वां मान प्रिंट करना है।

इसके लिए, हम ट्री का DFS ट्रैवर्सल करते हैं और इसे एक वेक्टर में संग्रहीत करते हैं। इस वेक्टर में, हम Vstart और Vend के मान ढूंढेंगे जो ट्री के DFS ट्रैवर्सल की शुरुआत और अंत को चिह्नित करते हैं। फिर इस रेंज में k-वां मान ढूंढें और यदि संभव हो तो प्रिंट करें।

उदाहरण

हमारे समाधान के कार्य को दर्शाने वाला प्रोग्राम

#include <bits/stdc++.h> using namespace std; #define N 100005 int n; vector<int> tree[N]; int currentIdx; vector<int> startIdx,endIdx; vector<int> dfsTraversalVector; void insertEdge(int u, int v){    tree[u].push_back(v);    tree[v].push_back(u); } void findDfsTraversal(int ch, int par){    dfsTraversalVector[currentIdx] = ch;    startIdx[ch] = currentIdx++;    for (auto c : tree[ch]) {       if (c != par)          findDfsTraversal(c, ch);    }    endIdx[ch] = currentIdx - 1; } int findKNodeDfsV(int v, int k){    k = k + (startIdx[v] - 1);    if (k <= endIdx[v])       return dfsTraversalVector[k];    return -1; } int main(){    n = 9;    insertEdge(5, 8);    insertEdge(5, 2);    insertEdge(5, 10);    insertEdge(5, 3);    insertEdge(2, 6);    insertEdge(2, 1);    insertEdge(3, 9);    insertEdge(6, 1);    insertEdge(9, 7);    startIdx.resize(n);    endIdx.resize(n);    dfsTraversalVector.resize(n);    findDfsTraversal(5, 0);    int v = 2,    k = 4;    cout<<k<<"-वां नोड DFS ट्रैवर्सल में नोड "<<v<<" का है "<<findKNodeDfsV(v, k);    return 0; }

आउटपुट

4-वां नोड DFS ट्रैवर्सल में नोड 2 का है 1

  1. C++ में बाइनरी ट्री में निकटतम लीफ ढूंढें C++ में बाइनरी ट्री में निकटतम लीफ ढूंढें

    मान लीजिए, एक बाइनरी ट्री दिया गया है। इसमें अलग-अलग लेवल पर लीफ नोड्स हैं। एक और पॉइंटर दिया गया है, जो एक नोड को इंगित कर रहा है। हमें इंगित नोड से निकटतम लीफ नोड की दूरी ढूंढनी है। ट्री को नीचे जैसा मानें - यहां लीफ नोड्स 2, -2 और 6 हैं। यदि पॉइंटर नोड -5 पर इंगित कर रहा है, तो -5 से निकटतम नोड

  1. बाइनरी ट्री में रूट से दिए गए नोड तक की दूरी खोजें C++ में बाइनरी ट्री में रूट से दिए गए नोड तक की दूरी खोजें C++ में

    मान लीजिए हमारे पास कुछ नोड्स के साथ एक बाइनरी ट्री है। हमें रूट और दूसरे नोड u के बीच की दूरी खोजनी है। मान लीजिए ट्री नीचे जैसा है: अब (रूट, 6) के बीच की दूरी = 2, पथ की लंबाई 2 है, (रूट, 8) के बीच की दूरी = 3 आदि। इस समस्या को हल करने के लिए, हम नोड को बाएं और दाएं सबट्री में खोजने के लिए एक पुन

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

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