資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在C++中查詢樹的子樹的DFS遍歷中的第K個節點
在這個問題中，我們得到一個大小為N的樹，樹的一個節點V和k。我們的任務是查詢樹的給定子樹的DFS遍歷中的第K個節點。
我們需要找到從頂點V開始的樹的DFS遍歷中的第k個節點。
讓我們舉個例子來理解這個問題：
輸入
V = 2, k = 3
輸出：4
解釋 -
The series is {1, 2, 3, 5, 6, 7}
The 4th element is 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<<"-th node in DFS traversal of node "<<v<<" is "<<findKNodeDfsV(v, k);
return 0;
}輸出
4-th node in DFS traversal of node 2 is 1
更新於：2022年1月28日
118 次瀏覽
廣告