二维vector树求树根
时间: 2024-01-22 11:16:29 浏览: 27
在C++中,可以使用二维vector来表示树的结构。树的根节点是指没有父节点的节点,也就是说根节点没有入边。
下面是一个示例代码,用于求解二维vector表示的树的根节点:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int findRoot(vector<vector<int>>& tree) {
vector<int> inDegree(tree.size(), 0); // 记录每个节点的入度
// 统计每个节点的入度
for (int i = 0; i < tree.size(); i++) {
for (int j = 0; j < tree[i].size(); j++) {
inDegree[tree[i][j]]++;
}
}
// 找到入度为0的节点,即为根节点
for (int i = 0; i < inDegree.size(); i++) {
if (inDegree[i] == 0) {
return i;
}
}
return -1; // 没有找到根节点
}
int main() {
// 构建一个二维vector表示的树
vector<vector<int>> tree = {{1, 2}, {3}, {4, 5}, {}, {}, {}};
int root = findRoot(tree);
if (root != -1) {
cout << "根节点是:" << root << endl;
} else {
cout << "没有找到根节点" << endl;
}
return 0;
}
```
在上面的代码中,我们首先定义了一个函数`findRoot`,该函数接受一个二维vector表示的树作为参数。然后,我们创建了一个大小为树节点数量的一维vector`inDegree`,用于记录每个节点的入度。
接下来,我们遍历二维vector`tree`,统计每个节点的入度。具体做法是,对于每个节点的子节点,将子节点的入度加1。
最后,我们再次遍历一维vector`inDegree`,找到入度为0的节点,即为根节点。
在示例代码中,我们构建了一个二维vector表示的树,并调用`findRoot`函数来求解根节点。如果找到了根节点,则输出根节点的值;如果没有找到根节点,则输出提示信息。
希望能帮助到你!如果有任何疑问,请随时提问。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)