在这个问题中，我们得到一棵二叉树，我们需要从特定节点执行 dfs，其中我们假设给定节点作为根并从中执行 dfs。
在上面的树中假设我们需要执行 DFS节点 F
在本教程中，我们将应用一些非正统的方法，以便大大降低我们的时间复杂度，因此我们也能够在更高的约束条件下运行此代码。
立即学习“C++免费学习笔记（深入）”；
方法 – 在这种方法中，我们不会简单地采用天真的方法，即我们简单地对每个节点应用 dfs，因为它不适用于更高的约束，因此我们尝试使用一些非正统的方法来避免获得 TLE。
#include using namespace std;#define N 100000// Adjacency list to store the// tree nodes connectionsvector v[N];unordered_map mape; // will be used for associating the node with it's indexvector a;void dfs(int nodesunder[], int child, int parent){ // function for dfs and precalculation our nodesunder a.push_back(child); // storing the dfs of our tree // nodesunder of child subtree nodesunder[child] = 1; for (auto it : v[child]) { // performing normal dfs if (it != parent) { // as we the child can climb up to //it's parent so we are trying to avoid that as it will become a cycle dfs(nodesunder, it, child); // recursive call nodesunder[child] += nodesunder[it]; // storing incrementing the nodesunder //by the number of nodes under it's children } }}// Function to print the DFS of subtree of nodevoid printDFS(int node, int nodesunder[]){ int ind = mape[node]; // index of our node in the dfs array cout << "The DFS of subtree " << node << ": "; // print the DFS of subtree for (int i = ind; i < ind + nodesunder[node]; i++){ // going through dfs array and then //printing all the nodes under our given node cout << a[i] << " "; } cout << endl;}void addEdgetoGraph(int x, int y){ // for maintaining adjacency list v[x].push_back(y); v[y].push_back(x);}void mark(){ // marking each node with it's index in dfs array int size = a.size(); // marks the index for (int i = 0; i < size; i++) { mape[a[i]] = i; }}int main(){ int n = 7; // add edges of a tree addEdgetoGraph(1, 2); addEdgetoGraph(1, 3); addEdgetoGraph(2, 4); addEdgetoGraph(2, 5); addEdgetoGraph(4, 6); addEdgetoGraph(4, 7); // array to store the nodes present under of subtree // of every node in a tree int nodesunder[n + 1]; dfs(nodesunder, 1, 0); // generating our nodesunder array mark(); // marking the indices in map // Query 1 printDFS(2, nodesunder); // Query 2 printDFS(4, nodesunder); return 0;}
输出
The DFS of subtree 2: 2 4 6 7 5The DFS of subtree 4: 4 6 7
理解代码
在这种方法中，我们预先计算 dfs 的顺序并将其存储在向量中，当我们预先计算 dfs 时，我们还计算从每个节点开始的每个子树下存在的节点，并且然后我们只需从 then 节点的起始索引遍历到其子树中存在的所有节点数。
结论
在本教程中，我们解决了一个问题来解决以下查询：树中子树的 DFS。我们还学习了针对此问题的C++程序以及解决此问题的完整方法（Normal）。
我们可以用其他语言（例如C、java、python等语言）编写相同的程序。希望这篇文章对您有所帮助。
以上就是在一棵树中，使用C++查询子树的深度优先搜索的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444979.html
微信扫一扫 
支付宝扫一扫 
